มีพัสดุ $n$ ชิ้น หมายเลขตั้งแต่ $1$ ถึง $n$ เพิ่งมาถึงคลังสินค้า พัสดุเหล่านั้นมาถึงในลำดับ $a_1, \dots, a_n$ และเราต้องการเรียงลำดับพัสดุให้อยู่ในลำดับ $1, 2, \dots, n$

เครื่องคัดแยกในคลังสินค้าทำงานเป็นรอบ ๆ (phases) แต่ละรอบจะรับแถวของพัสดุ $a_1, \dots, a_n$ และดำเนินการดังนี้: ขั้นแรก นำพัสดุชิ้นแรก $a_1$ ใส่ลงในแถวใหม่ จากนั้นสำหรับพัสดุแต่ละชิ้น $a_i$ เมื่อ $i = 2, \dots, n$ หาก $a_i$ มีค่ามากกว่าพัสดุชิ้นสุดท้าย (ขวาสุด) ในแถวใหม่ เครื่องจะวางพัสดุนั้นไว้ที่ท้ายแถว มิฉะนั้น เครื่องจะวางพัสดุนั้นไว้ที่หน้าสุดของแถว

หากแถวใหม่ยังไม่ได้เรียงลำดับอย่างถูกต้อง แถวใหม่นี้จะถูกใช้เป็นข้อมูลนำเข้าสำหรับรอบถัดไปของเครื่องคัดแยก

จงเขียนโปรแกรมเพื่อช่วยทดสอบว่าเครื่องทำงานตามที่ตั้งใจไว้หรือไม่ โดยตอบคำถามในรูปแบบ "พัสดุชิ้นใดอยู่ที่ตำแหน่งที่ $b$ หลังจากผ่านไป $t$ รอบ"

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มสองจำนวนคือ $n$ และ $q$ ($1 \le n, q \le 5 \cdot 10^5$) แทนจำนวนพัสดุและจำนวนคำถามตามลำดับ

บรรทัดที่สองประกอบด้วยลำดับของจำนวนเต็ม $n$ จำนวน คือ $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$) ซึ่งแทนลำดับเริ่มต้นของพัสดุ

อีก $q$ บรรทัดถัดไปประกอบด้วยคำถาม โดยบรรทัดที่ $i$ มีจำนวนเต็มสองจำนวนคือ $t_i$ และ $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$) แทนคำถามข้อที่ $i$

ข้อมูลส่งออก

แสดงผลทั้งหมด $q$ บรรทัดพอดี บรรทัดที่ $i$ ต้องแสดงคำตอบของคำถามข้อที่ $i$

หากเครื่องทำงานน้อยกว่า $t_i$ รอบ ให้พิมพ์ $-1$ มิฉะนั้น ให้พิมพ์หมายเลขพัสดุที่อยู่ในตำแหน่งที่ $b_i$ นับจากทางซ้าย หลังจากที่เครื่องทำงานไปแล้ว $t_i$ รอบ

ตัวอย่าง

ข้อมูลนำเข้า 1

5 4
2 1 3 5 4
1 1
3 2
4 1
0 4

ข้อมูลส่งออก 1

4
2
-1
5

หมายเหตุ 1

เครื่องจะทำงานทั้งหมดสามรอบ:

$$2\ 1\ 3\ 5\ 4 \to 4\ 1\ 2\ 3\ 5 \to 3\ 2\ 1\ 4\ 5 \to 1\ 2\ 3\ 4\ 5$$

ข้อมูลนำเข้า 2

1 1
1
1 1

ข้อมูลส่งออก 2

-1