Phép toán thao tác bit 3

Cho một số nguyên không âm \(a = 0\). Thực hiện \(q\) truy vấn thuộc một trong các loại sau:

• 1 x: Gán \(a\) bằng \(a \text{ XOR } x\).

• 2: Tắt bit bật quan trọng nhất của \(a\). Nếu \(a\) bằng \(0\), bỏ qua truy vấn này.

• 3: Đếm số lượng bit bật của \(a\).

Bit bật quan trọng nhất là bit bật nằm ngoài cùng bên trái. Ví dụ với số \(36\) có biểu diễn nhị phân là \((100100)_2\), bit bật quan trọng nhất là bit thứ \(5\), sau khi tắt bit này ta sẽ có giá trị \((100)_2\), biểu diễn thập phân là \(4\).

Input

• Dòng đầu tiên gồm một số nguyên \(q\) (\(1 \le q \le 3 \times 10^5\)).

• \(q\) dòng tiếp theo, mỗi dòng gồm một truy vấn theo định dạng trên (\(0 \le x < 2^{30}\)).

Output

In ra đáp án là một số nguyên cho mỗi truy vấn loại \(3\).

Example

Input:

5
2
1 5
3
2
3

Output:

2
1

Note

Ban đầu \(a = 0\).

Truy vấn loại \(2\) đầu tiên: \(a = 0\) nên bỏ qua.

Truy vấn 1 5: \(a = 0 \text{ XOR } 5 = 5 = (101)_2\).

Truy vấn loại \(3\): \(a = 5 = (101)_2\) có \(2\) bit bật, in ra \(2\).

Truy vấn loại \(2\): tắt bit bật quan trọng nhất của \(a = (101)_2\), thu được \(a = (001)_2 = 1\).

Truy vấn loại \(3\): \(a = 1 = (001)_2\) có \(1\) bit bật, in ra \(1\).