Im Königreich JOI gibt es $1$ ausreichend lange Straße, die von Ost nach West verläuft. Der Königspalast des Königreichs JOI liegt an dieser Straße, und eine Position entlang der Straße im Königreich JOI wird durch eine ganze Zahl $A$ dargestellt. Wenn $A = 0$ ist, stellt dies die Position des Königspalastes dar. Wenn $A > 0$ ist, stellt dies die Position $A$ Meter östlich vom Königspalast dar. Wenn $A < 0$ ist, stellt dies die Position $-A$ Meter westlich vom Königspalast dar.

Entlang der Straße im Königreich JOI stehen $N$ Häuser, die von West nach Ost der Reihe nach von $1$ bis $N$ nummeriert sind. Im Königreich JOI leben $N$ Bürger, die von $1$ bis $N$ nummeriert sind. In Haus $i$ wohnt Bürger $i$. Die Position von Haus $i$ wird durch eine von $0$ verschiedene gerade Zahl $A_i$ dargestellt. Alle $A_1, \dots, A_N$ sind paarweise verschieden.

Im Königreich JOI ist in den letzten Jahren der Bewegungsmangel der Bürger zu einem Problem geworden. Da sich der König des Königreichs JOI Sorgen um die Gesundheit der Bürger machte, erteilte er allen Bürgern den Befehl, einen Spaziergang zu machen. Sobald der König den Befehl erteilt, beginnen alle Bürger gleichzeitig entweder nach Osten oder nach Westen zu gehen. In welche Richtung jeder Bürger losgeht, ist für jeden Bürger festgelegt. Alle Bürger gehen beim Gehen mit einer Geschwindigkeit von $1$ Meter pro $1$ Sekunde.

Alle Bürger des Königreichs JOI plaudern für ihr Leben gern. Wenn sie während des Spaziergangs einem anderen Bürger begegnen, bleiben sie an Ort und Stelle stehen und beginnen ein Schwätzchen. Dasselbe gilt, wenn sie einem Bürger begegnen, der bereits stehen geblieben ist. Ein Bürger, der einmal stehen geblieben ist, setzt seinen Weg nicht wieder fort.

Im Königreich JOI gibt es $Q$ wichtige Personen. Der König des Königreichs JOI möchte die Positionen der $Q$ wichtigen Personen $T$ Sekunden nach Erteilung des Befehls kennen. Schreibe ein Programm, das die Positionen der $Q$ wichtigen Personen $T$ Sekunden nach Erteilung des Befehls bestimmt.

Eingabe

Die Eingabe besteht aus $1 + N + Q$ Zeilen.

In der $1$. Zeile stehen $3$ ganze Zahlen $N, T, Q$ ($1 \le N \le 100000 (= 10^5), 0 \le T \le 10^{18}, 1 \le Q \le 1000, 1 \le Q \le N$), getrennt durch Leerzeichen. Dies bedeutet, dass es im Königreich JOI $N$ Häuser gibt und der König die Positionen der $Q$ wichtigen Personen $T$ Sekunden nach Erteilung des Befehls wissen möchte.

In der $i$-ten Zeile der folgenden $N$ Zeilen stehen $2$ ganze Zahlen $A_i, D_i$ ($-10^{18} \le A_i \le 10^{18}$, $A_i$ ist eine von $0$ verschiedene gerade Zahl, $1 \le D_i \le 2$), getrennt durch ein Leerzeichen. $A_i$ ist eine gerade Zahl, welche die Position von Haus $i$ angibt. Für alle $i$ ($1 \le i \le N - 1$) gilt $A_i < A_{i+1}$. $D_i$ gibt die Richtung an, in die Bürger $i$ nach Erteilung des Befehls losgeht. Wenn $D_i = 1$ ist, geht Bürger $i$ nach Osten los. Wenn $D_i = 2$ ist, geht Bürger $i$ nach Westen los.

In der $i$-ten Zeile der folgenden $Q$ Zeilen steht eine ganze Zahl $X_i$ ($1 \le X_i \le N$). Dies bedeutet, dass die $i$-te wichtige Person in Haus $X_i$ wohnt. Für alle $i$ ($1 \le i \le Q - 1$) gilt $X_i < X_{i+1}$.

Von den $5$ gegebenen Eingabedatensätzen erfüllt Eingabe $1$ die Bedingungen $N \le 100, T \le 10000$. Außerdem erfüllt Eingabe $2$ die Bedingung $N \le 5000$. In Eingabe $3$ gibt es eine ganze Zahl $M$ ($1 \le M \le N - 1$), sodass für alle $i$ ($1 \le i \le M$) $D_i = 1$ und für alle $j$ ($M + 1 \le j \le N$) $D_j = 2$ gilt. Zudem überschreitet in den Eingaben $1, 2, 3$ der Absolutbetrag der in der Eingabe gegebenen ganzen Zahlen nicht $1000000000 (= 10^9)$. Beachte, dass in den Eingaben $4, 5$ die gegebenen ganzen Zahlen möglicherweise nicht in den Wertebereich einer vorzeichenbehafteten $32$-Bit-Ganzzahl passen.

Ausgabe

Die Ausgabe besteht aus $Q$ Zeilen.

Gib in der $i$-ten Zeile ($1 \le i \le Q$) eine ganze Zahl aus, welche die Position der $i$-ten wichtigen Person $T$ Sekunden nach Erteilung des Befehls durch den König angibt. Durch die Bedingungen in der Aufgabenstellung ist garantiert, dass dieser Wert eine ganze Zahl ist.

Beispiele

Eingabe 1

5 5 3
-8 1
-4 2
-2 2
4 2
10 1
1
3
5

Ausgabe 1

-6
-6
15

Eingabe 2

7 18 5
-100 1
-56 2
-34 1
-30 1
-22 1
-4 2
18 2
1
3
4
5
7

Ausgabe 2

-82
-16
-13
-13
0