W Królestwie JOI znajduje się $1$ wystarczająco długa droga biegnąca ze wschodu na zachód. Pałac królewski Królestwa JOI leży przy tej drodze, a położenie wzdłuż drogi w Królestwie JOI jest reprezentowane przez liczbę całkowitą $A$. Gdy $A = 0$, oznacza to położenie pałacu królewskiego. Gdy $A > 0$, oznacza to położenie o $A$ metrów na wschód od pałacu królewskiego. Gdy $A < 0$, oznacza to położenie o $-A$ metrów na zachód od pałacu królewskiego.

Wzdłuż drogi w Królestwie JOI stoi $N$ domów, ponumerowanych kolejno od zachodu na wschód od $1$ do $N$. W Królestwie JOI mieszka $N$ obywateli, ponumerowanych od $1$ do $N$. W domu $i$ mieszka obywatel $i$. Położenie domu $i$ jest reprezentowane przez różną od $0$ parzystą liczbę całkowitą $A_i$. Wszystkie liczby $A_1, \dots, A_N$ są parami różne.

W Królestwie JOI w ostatnich latach problemem stał się brak ruchu wśród obywateli. Zaniepokojony zdrowiem obywateli Król Królestwa JOI wydał wszystkim obywatelom rozkaz udania się na spacer. Gdy Król wydaje rozkaz, wszyscy obywatele jednocześnie zaczynają iść na wschód albo na zachód. To, w którym kierunku każdy obywatel zaczyna iść, jest z góry określone dla każdego obywatela. Wszyscy obywatele podczas marszu poruszają się z prędkością $1$ metra na $1$ sekundę.

Wszyscy obywatele Królestwa JOI uwielbiają pogawędki. Jeśli podczas spaceru spotkają innego obywatela, zatrzymują się w tym miejscu i zaczynają rozmawiać. To samo dzieje się, gdy spotkają obywatela, który już się zatrzymał. Obywatel, który raz się zatrzymał, nigdy więcej nie wznawia marszu.

W Królestwie JOI jest $Q$ ważnych osobistości. Król Królestwa JOI chciałby znać położenie tych $Q$ ważnych osobistości po upływie $T$ sekund od wydania rozkazu. Napisz program wyznaczający położenie $Q$ ważnych osobistości po upływie $T$ sekund od wydania rozkazu.

Wejście

Wejście składa się z $1 + N + Q$ wierszy.

W $1$. wierszu zapisane są $3$ liczby całkowite $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$) oddzielone spacjami. Oznacza to, że w Królestwie JOI jest $N$ domów, a Król chce znać położenie $Q$ ważnych osobistości po upływie $T$ sekund od wydania rozkazu.

W $i$-tym wierszu spośród kolejnych $N$ wierszy zapisane są $2$ liczby całkowite $A_i, D_i$ ($-10^{18} \le A_i \le 10^{18}$, $A_i$ jest różną od $0$ liczbą parzystą, $1 \le D_i \le 2$) oddzielone spacją. $A_i$ to liczba parzysta oznaczająca położenie domu $i$. Dla każdego $i$ ($1 \le i \le N - 1$) zachodzi $A_i < A_{i+1}$. $D_i$ oznacza kierunek, w którym obywatel $i$ zaczyna iść po wydaniu rozkazu. Gdy $D_i = 1$, obywatel $i$ zaczyna iść na wschód. Gdy $D_i = 2$, obywatel $i$ zaczyna iść na zachód.

W $i$-tym wierszu spośród kolejnych $Q$ wierszy zapisana jest liczba całkowita $X_i$ ($1 \le X_i \le N$). Oznacza to, że $i$-ta ważna osobistość mieszka w domu $X_i$. Dla każdego $i$ ($1 \le i \le Q - 1$) zachodzi $X_i < X_{i+1}$.

Spośród $5$ podanych zestawów danych wejściowych, w wejściu $1$ spełnione są warunki $N \le 100, T \le 10000$. Ponadto w wejściu $2$ spełniony jest warunek $N \le 5000$. Z kolei w wejściu $3$ istnieje pewna liczba całkowita $M$ ($1 \le M \le N - 1$) taka, że dla wszystkich $i$ ($1 \le i \le M$) zachodzi $D_i = 1$, a dla wszystkich $j$ ($M + 1 \le j \le N$) zachodzi $D_j = 2$. Ponadto w wejściach $1, 2, 3$ wartość bezwzględna liczb całkowitych podanych na wejściu nie przekracza $1000000000 (= 10^9)$. Zwróć uwagę, że w wejściach $4, 5$ podane liczby całkowite mogą nie mieścić się w zakresie $32$-bitowego typu całkowitego ze znakiem.

Wyjście

Wyjście składa się z $Q$ wierszy.

W $i$-tym wierszu ($1 \le i \le Q$) wypisz liczbę całkowitą oznaczającą położenie $i$-tej ważnej osobistości po upływie $T$ sekund od wydania rozkazu przez Króla. Warunki zadania gwarantują, że wartość ta jest liczbą całkowitą.

Przykład

Wejście 1

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

Wyjście 1

-6
-6
15

Wejście 2

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

Wyjście 2

-82
-16
-13
-13
0