We Need More Data Structures!

Limits: 3 sec., 512 MiB

Asli has two arrays \(a\) and \(b\) of exactly \(n\) integers each. She would like to know an array \(c\) such that \(c_k\) = \(\sum_{gcd(i, j) = k} a_i \cdot b_j\) for all \(1 \le k \le n\) (here \(gcd(i, j)\) stands for the greatest positive integer which divides both \(i\) and \(j\)).

But Kerem thinks that this task is very easy and, more importantly, does not involve any data structure. What a terrible problem! Thus, he wants Asli to answer the following query \(q\) times: how would array \(c\) look like if we change some element in array \(a\)? As the resulting array can be quite large, Kerem asks Asli to report only bitwise XOR of elements of array \(c\) instead.

More formally, Kerem asks Asli \(q\) queries, on the \(i^{th}\) of them: first, assign \(a_{pos_i}\) = \(val_i\), then update array \(c\) and report \(c_1 \oplus c_2 \oplus c_3 \oplus ... \oplus c_n\).

Can you help Asli to answer Kerem’s queries?

Input

The first line contains two integers \(n\) and \(q\) — the number of elements in the arrays and the number of queries respectively. In the second and the third lines you are given the elements of arrays \(a\) and \(b\), respectively. Each of the remaining \(q\) lines contains two integers \(pos_i\) and \(val_i\).

Output

For each of \(q\) queries you need to output answer to this query in one line.

Constraints

\(1 \le n, q \le 300000\),

\(1 \le pos_{i} \le n\),

\(0 \le a_{i}, b_{i}, val_{i} \le 10000\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 3 1 2 5 2 3 1 4 1 1 3 2 1 4 3	64 91 66

Notes

At the beginning, Asli has arrays \(a = [1, 2, 5, 2]\) and \(b = [3, 1, 4, 1]\).

After the first query array \(a\) will become equal to \([3, 2, 5, 2]\). Let’s calculate array \(c\).

\(c_1 = a_1 \cdot b_1 + a_1 \cdot b_2 + a_1 \cdot b_3 + a_1 \cdot b_4 + a_2 \cdot b_1 + a_2 \cdot b_3 + a_3 \cdot b_1 + a_3 \cdot b_2 + a_3 \cdot b_4 + a_4 \cdot b_1 + a_4 \cdot b_3 = 3 \cdot 3 + 3 \cdot 1 + 3 \cdot 4 + 3 \cdot 1 + 2 \cdot 3 + 2 \cdot 4 + 5 \cdot 3 + 5 \cdot 1 + 5 \cdot 1 + 2 \cdot 3 + 2 \cdot 4 = 80\)

\(c_2 = a_2 \cdot b_2 + a_2 \cdot b_4 + a_4 \cdot b_2 = 2 \cdot 1 + 2 \cdot 1 + 2 \cdot 1 = 6\)

\(c_3 = a_3 \cdot b_3 = 5 \cdot 4 = 20\)

\(c_4 = a_4 \cdot b_4 = 2 \cdot 1 = 2\)

So \(c = [80, 6, 20, 2]\), and the answer to this query is equal to \(80 \oplus 6 \oplus 20 \oplus 2 = 64\).

After the second query array \(a\) will become equal to \([3, 1, 5, 2]\). Then \(c = [73, 4, 20, 2]\), and the answer to this query is equal to \(73 \oplus 4 \oplus 20 \oplus 2 = 91\).

After the third query array \(a\) will become equal to \([3, 1, 5, 3]\). Then \(c = [80, 5, 20, 3]\), and the answer to this query is equal to \(80 \oplus 5 \oplus 20 \oplus 3 = 66\).