Cho dãy ~A~ có ~N~ phần tử không âm. Định nghĩa ~f(x, A)~ (với ~x~ là một số nguyên dương ~\leq |A|~) là ~AND~ lớn nhất của mọi dãy con của ~A~ có độ dài ~x~.

Dãy con của A có thể được tạo ra bằng cách xóa đi một vài (có thể là không) phần tử từ dãy ban đầu, các phần tử còn lại phải đảm bảo tính thứ tự ban đầu của nó. Ví dụ, với dãy ~[5, 1, 3, 4]~ thì các dãy con có thể là ~[3], [5, 4], [5, 1, 4]~, nhưng dãy ~[3, 1]~ thì không.

Có ~M~ truy vấn trên dãy ~A~, mỗi truy vấn thuộc 1 trong 3 loại:

• ~1 \space v:~ Chèn giá trị ~v~ vào cuối dãy ~A~.

• ~2 \space v:~ Xóa phần tử mang giá trị ~v~ ra khỏi ~A~, dữ liệu đảm bảo luôn tồn tại ~v~ trong dãy trước khi xóa.

• ~3 \space x~: Tính ~f(x, A)~.

Input

• Dòng đầu gồm 3 số nguyên ~N, M, k~ ~(1 \leq N, M \leq 75000, 1 \leq k \leq 18)~.

• Dòng tiếp theo gồm ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(0 \leq a_i < 2^k \space)~ là các phần tử ban đầu của dãy ~A~.

• Mỗi dòng trong ~M~ dòng tiếp theo chứa 1 trong 3 truy vấn ~1 \space v~, ~2 \space v~, hoặc ~3 \space x~ ~(0 \leq v < 2 ^ k, 1 \leq x \leq |A|~).

Output

• Với mỗi truy vấn loại ~3~, in ra một số nguyên duy nhất là kết quả của ~f(x, A)~ trên một dòng.

Scoring

Sample Input 1

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

Sample Output 1

6
4
6
5

Notes

Những dãy con mang lại kết quả tối ưu là ~(6, 7); (6, 7, 5); (6, 7, 7); (7, 5)~