Cho một số nguyên không âm \(a=0\) (32-bit). 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\) \(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\).
• \(4\): Trừ đi bit cuối cùng và in kết quả. (10 -> 8)
• \(5\): Bỏ tất cả và giữ lại 1 bit cuối. (10 -> 2)
• \(6\) \(x\): in ra giá trị nếu xoay vòng bit về phải \(x\) lần (10 dịch phải -> 5 hoặc 11 dịch 1 bit thành 2147483653)
• \(7\) \(x\): in ra giá trị nếu xoay vòng bit về trái \(x\) lần (10 dịch trái -> 20)

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\)

Lưu ý: truy vấn 6 và 7 không gán lại vào biến a

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên \(q\).
• \(q\) dòng tiếp theo, mỗi dòng gồm một truy vấn theo định dạng trên.

Dữ liệu ra

• In ra đáp án là một số nguyên cho mỗi truy vấn loại \(3,4,5,6,7\)

Điều kiện

• \(1 \le q \le 3 \times 10^5\)
• \(0 \le x \lt 2^{30}\)

Input 1

5
2
1 5
3
2
3

Output 1

2
1

Input 2

12
1 616284779
5
2
6 485275370
3
4
6 241372541
5
4
7 761562749
7 671334949
3

Output 2

1
0
0
0
0
0
0
0
0
0