Hợp rồi lại tan, tan rồi lại hợp, có khi chưa kịp hợp mà đã tan từ lúc nào không hay. Cho dãy ~a~ là một hoán vị của dãy ~\{1,2,...,n\}~, một đoạn con liên tiếp gồm các phần tử ~a_l, a_{l+1},...,a_r~ được kí hiệu là ~a[l..r]~.

Lần lượt thực hiện ~q~ thao tác, mỗi thao tác thuộc một trong hai dạng:

• 1 ~p~: in ra ~a_p~

• 2 ~p~: thực hiện ~a:=Merge(a[1..p], a[p+1..n])~

Hàm merge sử dụng bên trên được mô tả dưới đây:

func Merge(dãy a, dãy b):
     khởi tạo dãy c rỗng
     while (a và b không rỗng)
          if (a[0] > b[0])
               thêm b[0] vào cuối c
               xoá b[0] khỏi b
          else
               thêm a[0] vào cuối c
               xoá a[0] khỏi a
     while (a không rỗng)
          thêm a[0] vào cuối c
          xoá a[0] khỏi a
     while (b không rỗng)
          thêm b[0] vào cuối c
          xoá b[0] khỏi b
     return c

Yêu cầu: Với mỗi thao tác loại 1, hãy in ra giá trị của phần tử tương ứng trong truy vấn.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n, q~ (~1\le n,q \le 2\times 10^5~) là số phần tử của dãy và số truy vấn.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,...,a_n~ (~a_i\le n, a_i \neq a_j~ với ~i\neq j~).

~q~ dòng tiếp, mỗi dòng nhập vào hai số nguyên ~v, p~ (~v\in \{1, 2\}, 1\le p \le n~) mô tả một thao tác.

Output

In ra trên nhiều dòng, mỗi dòng in ra một số là đáp án cho thao tác loại 1 tương ứng trong đầu vào

Scoring

Có ~50\%~ số điểm của bài ứng với ~n,q \le 5000~

Còn lại không có điều kiện gì thêm

Sample Input 1

5 6
1 5 4 3 2
1 3
2 4
2 3
1 1
1 2
2 5

Sample Output 1

4
1
2