В королевстве JOI есть $1$ достаточно длинная дорога, идущая с востока на запад. Вдоль дороги расположен королевский дворец королевства JOI, а положение точки вдоль дороги в королевстве JOI задается целым числом $A$. Значение $A = 0$ соответствует положению королевского дворца. Если $A > 0$, это положение в $A$ метрах к востоку от королевского дворца. Если $A < 0$, это положение в $-A$ метрах к западу от королевского дворца.

Вдоль дороги в королевстве JOI расположены $N$ домов, пронумерованных с запада на восток от $1$ до $N$. В королевстве JOI живут $N$ граждан, пронумерованных от $1$ до $N$. В доме $i$ живет гражданин $i$. Положение дома $i$ задается ненулевым четным числом $A_i$. Все числа $A_1, \dots, A_N$ различны.

В последние годы в королевстве JOI проблемой стала нехватка физической активности у граждан. Обеспокоенный здоровьем граждан, король королевства JOI издал указ, предписывающий всем гражданам выйти на прогулку. Как только король издает указ, все граждане одновременно начинают идти либо на восток, либо на запад. В каком направлении начинает идти каждый гражданин, определено заранее для каждого из них. Во время ходьбы все граждане движутся со скоростью $1$ метр за $1$ секунду.

Все граждане королевства JOI очень любят поболтать. Если во время прогулки гражданин встречает другого гражданина, они останавливаются на этом месте и начинают светскую беседу. То же самое происходит, если гражданин встречает другого гражданина, который уже остановился. Остановившись однажды, гражданин больше никогда не возобновляет движение.

В королевстве JOI есть $Q$ важных персон. Король королевства JOI хочет знать положение этих $Q$ важных персон через $T$ секунд после издания указа. Напишите программу, которая определит положение $Q$ важных персон через $T$ секунд после издания указа.

Входные данные

Входные данные состоят из $1 + N + Q$ строк.

В $1$-й строке через пробел записаны $3$ целых числа $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$). Это означает, что в королевстве JOI есть $N$ домов и король хочет знать положение $Q$ важных персон через $T$ секунд после издания указа.

В $i$-й строке из следующих $N$ строк через пробел записаны $2$ целых числа $A_i, D_i$ ($-10^{18} \le A_i \le 10^{18}$, $A_i$ — ненулевое четное число, $1 \le D_i \le 2$). $A_i$ — четное число, обозначающее положение дома $i$. Для всех $i$ ($1 \le i \le N - 1$) выполняется $A_i < A_{i+1}$. $D_i$ обозначает направление, в котором гражданин $i$ начинает идти после издания указа. При $D_i = 1$ гражданин $i$ начинает идти на восток. При $D_i = 2$ гражданин $i$ начинает идти на запад.

В $i$-й строке из следующих $Q$ строк записано целое число $X_i$ ($1 \le X_i \le N$). Это означает, что $i$-я важная персона живет в доме $X_i$. Для всех $i$ ($1 \le i \le Q - 1$) выполняется $X_i < X_{i+1}$.

Из $5$ предложенных наборов входных данных во входных данных $1$ выполняются условия $N \le 100, T \le 10000$. Во входных данных $2$ выполняется $N \le 5000$. Во входных данных $3$ существует такое целое число $M$ ($1 \le M \le N - 1$), что для всех $i$ ($1 \le i \le M$) выполняется $D_i = 1$, а для всех $j$ ($M + 1 \le j \le N$) выполняется $D_j = 2$. Кроме того, во входных данных $1, 2, 3$ модули целых чисел, данных во входных данных, не превосходят $1000000000 (= 10^9)$. Обратите внимание, что во входных данных $4, 5$ входные числа могут не помещаться в диапазон $32$-битного знакового целого типа.

Выходные данные

Выходные данные состоят из $Q$ строк.

В $i$-й строке ($1 \le i \le Q$) выведите целое число, обозначающее положение $i$-й важной персоны через $T$ секунд после издания указа королем. Условиями задачи гарантируется, что это значение является целым числом.

Примеры

Входные данные 1

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

Выходные данные 1

-6
-6
15

Входные данные 2

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

Выходные данные 2

-82
-16
-13
-13
0