Phép Gộp Xen Kẽ

Cho một dãy gồm đúng $2^n$ số nguyên không âm. Ta rút gọn dãy theo nhiều tầng:

• ở tầng đầu tiên, thay từng cặp kề nhau bằng phép OR bit;
• ở tầng kế tiếp, thay từng cặp kết quả bằng phép XOR bit;
• tiếp tục xen kẽ OR, XOR, OR, XOR, ... cho đến khi chỉ còn một số.

Có $m$ phép cập nhật. Sau mỗi lần thay một phần tử, hãy in số duy nhất nhận được khi rút gọn toàn bộ dãy theo quy tắc trên.

Input

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $2^n$ số nguyên của dãy, theo thứ tự từ trái sang phải.
• Mỗi dòng trong $m$ dòng tiếp theo chứa $p$ $b$, nghĩa là gán phần tử thứ $p$ bằng $b$.

Output

• Sau mỗi cập nhật, in ra một dòng chứa kết quả rút gọn của toàn dãy.

Constraints

• $1\le n\le 17$.
• $1\le m\le 10^5$.
• $0\le a_i,b<2^{30}$.
• $1\le p\le 2^n$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 11,m\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

2 3
1 6 3 5
1 4
3 4
4 2

1
3
0