Giải bài trực tuyến

Cho dãy A gồm N số nguyên không âm. Ta lần lượt thực hiện Q thao tác trên tập hợp này:

• XOR x: Với mọi i, A_i = A_i xor x
• FIND k: Tìm số lớn thứ k trong dãy A.

Yêu cầu: Thực hiện các truy vấn trên.

Input

Dòng đầu tiên ghi 2 số N và Q.

Dòng thứ hai ghi N số là giá trị ban đầu của dãy A.

Tiếp theo là Q dòng, mỗi dòng ghi 1 trong 2 loại truy vấn.

Output

Với mỗi truy vấn loại FIND, in ra kết quả tìm được.

Giới hạn

Subtask 1 (25%)

• N, Q ≤ 5000
• 0 ≤ A_i ≤ 10⁹
• 0 ≤ x ≤ 10⁹.

Các subtask 2, 3 và 4 tiếp theo đều có

• N ≤ 10⁵
• Q ≤ 10⁵
• 0 ≤ A_i ≤ 10⁹

Subtask 2 (40%)

• 0 ≤ x ≤ 100

Subtask 3 (10%):

• 0 ≤ x ≤ 10⁹
• x luôn có dạng 2^k

Subtask 4 (25%):

• 0 ≤ x ≤ 10⁹

Ví dụ

Input:
4 9
1 2 3 4
FIND 1
FIND 2
FIND 3
FIND 4
XOR 6
FIND 1
FIND 2
FIND 3
FIND 4

Output:
4
3
2
1
7
5
4
2

Giải thích

Trước truy vấn XOR 6, dãy số là 1 2 3 4.

Sau truy vấn XOR 6, dãy số là 7 4 5 2.