ในอาณาจักร JOI มีถนนที่ยาวเพียงพออยู่ $1$ สายที่ทอดตัวในแนวทิศตะวันออก-ตะวันตก พระราชวังของอาณาจักร JOI ตั้งอยู่ริมถนน และตำแหน่งริมถนนในอาณาจักร JOI จะแทนด้วยจำนวนเต็ม $A$ เมื่อ $A = 0$ จะแทนตำแหน่งของพระราชวัง เมื่อ $A > 0$ จะแทนตำแหน่งที่ห่างจากพระราชวังไปทางทิศตะวันออก $A$ เมตร เมื่อ $A < 0$ จะแทนตำแหน่งที่ห่างจากพระราชวังไปทางทิศตะวันตก $-A$ เมตร

ริมถนนของอาณาจักร JOI มีบ้านอยู่ $N$ หลัง โดยบ้านแต่ละหลังมีหมายเลขกำกับตั้งแต่ $1$ ถึง $N$ เรียงตามลำดับจากทิศตะวันตกไปทิศตะวันออก ในอาณาจักร JOI มีพลเมือง $N$ คน โดยมีหมายเลขกำกับตั้งแต่ $1$ ถึง $N$ พลเมืองคนที่ $i$ อาศัยอยู่ในบ้านหลังที่ $i$ ตำแหน่งของบ้านหลังที่ $i$ แทนด้วยจำนวนเต็มคู่ที่ไม่ใช่ $0$ คือ $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$ เป็นจำนวนคู่ที่ไม่ใช่ $0$, $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