في مملكة JOI يوجد طريق $1$ طويل بما يكفي يمتد من الشرق إلى الغرب. يقع القصر الملكي لمملكة JOI على طول الطريق، ويُعبَّر عن الموقع على طول الطريق في مملكة JOI بعدد صحيح $A$. عندما يكون $A = 0$، فإنه يمثل موقع القصر الملكي. عندما يكون $A > 0$، فإنه يمثل الموقع الذي يبعد $A$ متراً شرق القصر الملكي. عندما يكون $A < 0$، فإنه يمثل الموقع الذي يبعد $-A$ متراً غرب القصر الملكي.

يوجد $N$ منزلاً على طول الطريق في مملكة JOI، والمنازل مرقمة من $1$ إلى $N$ بالترتيب من الغرب إلى الشرق. يوجد $N$ مواطناً في مملكة JOI، مرقمين من $1$ إلى $N$. يسكن المواطن $i$ في المنزل $i$. يُعبَّر عن موقع المنزل $i$ بعدد زوجي غير صفري $A_i$. جميع الأعداد $A_1, \dots, A_N$ مختلفة.

في مملكة JOI، أصبحت قلة الحركة لدى المواطنين مشكلة في السنوات الأخيرة. ولأن ملك مملكة JOI قلق بشأن صحة المواطنين، فقد أصدر أمراً لجميع المواطنين بالخروج في نزهة سيراً على الأقدام. بمجرد أن يصدر الملك الأمر، يبدأ جميع المواطنين في نفس اللحظة بالمشي إما باتجاه الشرق أو باتجاه الغرب. الاتجاه الذي يبدأ كل مواطن المشي فيه محدد مسبقاً لكل مواطن. يمشي جميع المواطنين بسرعة $1$ متر لكل $1$ ثانية.

جميع مواطني مملكة JOI يحبون الدردشة كثيراً. إذا التقى مواطن بمواطن آخر أثناء النزهة، فإنهما يتوقفان في ذلك المكان ويبدآن في الحديث. وينطبق الأمر نفسه إذا التقى بمواطن قد توقف بالفعل. المواطن الذي يتوقف مرة واحدة لا يعود إلى المشي مرة أخرى أبداً.

يوجد $Q$ من الشخصيات المهمة في مملكة JOI. يريد ملك مملكة 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$) مفصولة بمسافات. يشير هذا إلى وجود $N$ منزلاً في مملكة JOI، وأن الملك يريد معرفة مواقع الشخصيات المهمة الـ $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$) بحيث يتحقق $D_i = 1$ لكل $i$ ($1 \le i \le M$) ويتحقق $D_j = 2$ لكل $j$ ($M + 1 \le j \le N$). علاوة على ذلك، في المدخلات $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