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 một 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
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~10~ | ~1 \leq |A| \leq 12~ tại mọi thời điểm |
2 | ~30~ | Không có truy vấn loại ~1~ và ~2~ |
3 | ~60~ | Không có ràng buộc gì thêm |
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)~
Bình luận