Xenia và các phép toán bit (Xenia and Bit Operations)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có dãy gồm $2^n$ số nguyên không âm. Từ dãy hiện tại, ở tầng đầu tiên ghép từng cặp kề nhau bằng phép OR bit; tầng tiếp theo ghép bằng XOR bit; sau đó tiếp tục luân phiên OR và XOR cho đến khi chỉ còn một giá trị $v$. Có $m$ lần cập nhật một phần tử. Sau mỗi lần cập nhật, hãy in giá trị $v$ mới.

Input

• Dòng đầu chứa $n$ và $m$.
• Dòng thứ hai chứa $2^n$ số $a_1,a_2,\ldots,a_{2^n}$ với $0 \le a_i<2^{30}$.
• Mỗi trong $m$ dòng tiếp theo chứa $p$ và $b$, nghĩa là gán $a_p=b$, với $1 \le p \le 2^n$ và $0 \le b<2^{30}$.

Output

Sau mỗi lần cập nhật, in giá trị $v$ của toàn dãy trên một dòng.

Subtask

• Subtask 1 — 20%: $1 \le n \le 10$, $1 \le m \le 1000$.
• Subtask 2 — 30%: $1 \le n \le 15$, $1 \le m \le 50000$.
• Subtask 3 — 50%: $1 \le n \le 17$, $1 \le m \le 10^5$.

Ví dụ

Input

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

Output

1
3
3
3

Giải thích

Với $n=2$, tầng sát dãy dùng OR và tầng gốc dùng XOR. Sau cập nhật đầu tiên, dãy là $4,6,3,5$: hai giá trị trung gian là $4\,|\,6=6$ và $3\,|\,5=7$, nên $v=6\,\hat{}\,7=1$. Các cập nhật sau lần lượt cho các giá trị $3,3,3$.