Cho một dãy ~n~ số nguyên, ban đầu tất cả các phần tử có giá trị bằng ~0~ hoặc ~1~. Cho ~q~ truy vấn gồm 3 loại như sau:

• ~1~: Đảo toàn bộ giá trị của các phần tử trong dãy từ ~0~ thành ~1~, từ ~1~ thành ~0~ (Ví dụ: Dãy ~0 1 0 0 1~ sẽ bị đổi thành ~1 0 1 1 0~).
• ~2~: Lật ngược lại toàn bộ vị trí các phần tử trong dãy (Ví dụ: Dãy ~0 1 0 0 1~ sẽ bị đổi thành ~1 0 0 1 0~).
• ~3~ ~x~: Đưa ra giá trị của phần tử thứ ~x~ tại thời điểm đó.

Yêu cầu

Cho ~n~ và ~q~ truy vấn. Với mỗi truy vấn loại ~3~, in ra giá trị của phần tử tương ứng.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n~, ~q~ ~(1≤n,q≤10^6)~ cách nhau một dấu cách.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(0≤a_i≤1)~ cách nhau một dấu cách.
• ~q~ dòng sau, mỗi dòng là một truy vấn có dạng ~1~, ~2~ hoặc ~3~.

Output

Gồm nhiều dòng, mỗi dòng chứa một số nguyên tương ứng với kết quả của các truy vấn dạng ~3~.

Sample Input

5 5
1 0 0 1 0
3 2
1
3 5
2
3 4

Sample Output

0
1
1

Giải thích

Ban đầu dãy có 5 phần tử là ~[1, 0, 0, 1, 0]~.

Truy vấn đầu tiên yêu cầu đưa ra giá trị ~a_2~, kết quả là ~0~.

Truy vấn thứ hai thực hiện đảo giá trị dãy, dãy trở thành ~[0, 1, 1, 0, 1]~.

Truy vấn thứ ba yêu cầu đưa ra giá trị ~a_5~, kết quả là ~1~.

Truy vấn thứ tư thực hiện lật ngược dãy, dãy trở thành ~[1, 0, 1, 1, 0]~.

Truy vấn thứ năm yêu cầu đưa ra giá trị ~a_4~, kết quả là ~1~.

Subtask

• Có 50% số test ứng với 50% số điểm có ~1≤n,q≤10^3~;
• 50% số test còn lại tương ứng với 50% số điểm không có giới hạn gì thêm.