Нам потрібно більше структур даних!

Обмеження: 3 сек., 512 МіБ

Аслі має два масиви \(a\) й \(b\), кожен містить \(n\) цілих чисел. Вона б хотіла знати масив \(c\) такий, що \(c_k = \sum_{\gcd(i, j)=k} a_i \cdot b_j\) для всіх \(1 \le k \le n\) (тут \(\gcd(i, j)\) позначає найбільший спільний дільник чисел \(i\) та \(j\)).

Проте Керем думає, що це завдання дуже легке й, що важливіше, не потребує жодної структури даних. Що за жахлива задача!

Тому він хоче спитати в Аслі \(q\) разів, яким буде масив \(c\), якщо змінити якийсь елемент у масиві \(a\). Оскільки результат може бути досить великим, Керем просить Аслі сказати тільки XOR елементів масиву \(c\).

Формальніше, Керем дає Аслі \(q\) запитів. На \(i\)-ому з них спершу присвоюється \(a_{p_i} = v_i\), тоді оновлюється масив \(c\). Відповіддю на запит є \(c_1 \mbox { XOR } c_2 \mbox { XOR } \dots \mbox { XOR } c_n\).

Можете допомогти Аслі відповісти на Керемові запити?

Вхідні дані

Перший рядок містить два цілих числа \(n\) і \(q\) — кількість елементів у масивах і кількість запитів відповідно.

У другому й третьому рядках задано по \(n\) цілих чисел — елементи масивів \(a\) й \(b\) відповідно.

Кожен із наступних \(q\) рядків містить два цілих числа \(p_i\) та \(v_i\) — індекс елемента, який треба змінити, та його нове значення.

Вихідні дані

У \(q\) рядках виведіть по цілому числу — відповіді на запити.

Обмеження

\(1 \le n, q \le 3 \cdot 10^5\),

\(1 \le p_i \le n\),

\(1 \le a_i, b_i, v_i \le 10^4\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 3 1 2 5 2 3 1 4 1 1 3 2 1 4 3	64 91 66

Примітки

На початку Аслі має масиви \(a=[1, 2, 5, 2]\) й \(b=[3, 1, 4, 1]\). Після першого запиту масив \(a\) стане \([3, 2, 5, 2]\). Порахуймо масив \(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\).

Тож \(c=[80, 6, 20, 2]\), і відповідь на цей запит дорівнює \(80 \mbox{ XOR } 6 \mbox{ XOR } 20 \mbox{ XOR } 2 = 64\).

Після другого запиту масив \(a\) стане \([3, 1, 5, 2]\). Тоді \(c=[73, 4, 20, 2]\), і відповідь на цей запит дорівнює \(73 \mbox{ XOR } 4 \mbox{ XOR } 20 \mbox{ XOR } 2 = 91\).

Після другого запиту масив \(a\) стане \([3, 1, 5, 3]\). Тоді \(c = [80, 5, 20, 3]\), і відповідь на цей запит дорівнює \(80 \mbox{ XOR } 5 \mbox{ XOR } 20 \mbox{ XOR } 3 = 66\).