Description

On a road, positions are represented by integers $A$.

When $A=0$, there is a royal palace. If $A>0$, it means $A$ meters to the east of the palace; if $A<0$, it means $-A$ meters to the west of the palace.

Along the road, there are $N$ houses labeled $1 \sim N$ from west to east. Each house has exactly one person. Houses exist only at even integer points.

The king believes that the citizens’ fitness is declining and orders everyone to go out for a stroll. Every citizen can walk $1$ meter per second. Each citizen walks either east or west; these directions are known to you. All citizens start their stroll simultaneously when the order is issued.

However, the citizens are very talkative. If two people meet during the stroll, they stop and talk. If a walking person reaches a point that coincides with someone who has already stopped, they will also stop and talk. Once they stop, they will chat endlessly and forget about the stroll.

Now $T$ seconds have passed since the order was issued. There are $Q$ important persons of interest, and the king wants to know their positions. Can you help him?

Input Format

The first line contains $3$ integers $N, T, Q$.

The next $N$ lines each contain two integers $A_i, R_i$. $A_i$ is the home coordinate. If $R_i$ is $1$, the person walks east; if it is $2$, the person walks west. It is guaranteed that the $A_i$ are in strictly increasing order and no two people share the same initial position.

The next $Q$ lines each contain one integer: the index of a person of interest (indexed $1$ to $N$ from west to east).

Output Format

Output $Q$ lines. Each line contains one integer, the coordinate of that person.

6 6 4
-10 1
-6 2
-4 1
2 1
6 2
18 2
2
3
4
6

-8
2
4
12

Hint

$20\%$ of the testdata: $N \le 100$, $T \le 10000$.

Another $20\%$ of the testdata: $N \le 5000$.

Another $20\%$ of the testdata: starting from the westernmost, some consecutive citizens all walk east, and the remaining citizens all walk west.

$100\%$ of the testdata: $A_i$ are even, $|A_i| \le 10^{18}$, $|T| \le 10^{18}$, $1 \le Q \le N \le 100000$.

Translated by ChatGPT 5