У королівстві 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