Xenia and Bit Operations

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

A sequence contains $2^n$ non-negative integers. On the first reduction level, adjacent pairs are combined with bitwise OR; on the next level they are combined with bitwise XOR; OR and XOR then alternate until one value $v$ remains. After each of $m$ point updates, print the new $v$.

Input

• The first line contains $n$ and $m$.
• The second line contains $2^n$ values $a_1,a_2,\ldots,a_{2^n}$ with $0 \le a_i<2^{30}$.
• Each of the next $m$ lines contains $p$ and $b$, meaning $a_p=b$, with $1 \le p \le 2^n$ and $0 \le b<2^{30}$.

Output

After each update, print the current value $v$ on its own line.

Subtasks

• 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$.

Examples

Input

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

Output

1
3
3
3

Explanation

For $n=2$, the level directly above the array uses OR and the root level uses XOR. After the first update, the array is $4,6,3,5$: the intermediate values are $4\,|\,6=6$ and $3\,|\,5=7$, hence $v=6\,\hat{}\,7=1$. The later updates produce $3,3,3$.