Description

In a school, a teacher wants to arrange $N$ students in a line. The students are numbered $1 \sim N$. The teacher proceeds as follows:

1. First, student $1$ is placed in the queue. At this moment, the queue contains only that student.

2. Students $2 \sim N$ join the queue one by one. For student numbered $i$, the teacher specifies that student $i$ stands to the left or right of some student among $1 \sim (i - 1)$ (i.e., a student who has already joined the queue).

3. Remove $M$ students from the queue; the relative order of the remaining students does not change.

After all students have been arranged according to the above rules, the teacher wants to know the IDs of all students from left to right.

Input Format

The first line contains an integer $N$, the number of students.

Lines $2 \sim N$: line $i$ contains two integers $k, p$, where $k$ is a positive integer less than $i$, and $p$ is $0$ or $1$. If $p$ is $0$, insert student $i$ to the left of student $k$; if $p$ is $1$, insert student $i$ to the right of student $k$.

Line $N + 1$ contains an integer $M$, the number of students to remove.

The next $M$ lines each contain a positive integer $x$, meaning student $x$ is removed from the queue. If student $x$ is already not in the queue, ignore this instruction.

Output Format

One line containing at most $N$ space-separated integers, the IDs of the students from left to right.

4
1 0
2 1
1 0
2
3
3

2 4 1

Hint

[Sample Explanation]

Insert student $2$ to the left of student $1$. The queue is now:

2 1

Insert student $3$ to the right of student $2$. The queue is now:

2 3 1

Insert student $4$ to the left of student $1$. The queue is now:

2 3 4 1

Remove student $3$. The queue is now:

2 4 1

Student $3$ is no longer in the queue, so ignore the last instruction.

Final queue:

2 4 1

Constraints

• For $20\%$ of the testdata, $1 \leq N \leq 10$.
• For $40\%$ of the testdata, $1 \leq N \leq 1000$.
• For $100\%$ of the testdata, $1 < M \leq N \leq 10^5$.

Translated by ChatGPT 5