F. Орехус и занимательный xor
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Орехуса есть два массива $$$a$$$ и $$$b$$$ из $$$n$$$ чисел каждый. Он нашёл их так давно, что никто уже не знает, когда они у него появились.

Орехус часто меняет числа в массивах. Кроме того, после каждого изменения ему интересно, насколько похожи массивы $$$a$$$ и $$$b$$$.

Сходство массивов — это минимальное количество операций, которые нужно применить к массивам (каждую операцию можно применять как к первому массиву, так и ко второму), чтобы сделать их равными. Если это сделать невозможно, сходство равно $$$-1$$$.

За одну операцию можно выбрать подмассив длины $$$k$$$ ($$$k$$$ фиксированно), и заменить каждый элемент $$$a_i$$$, принадлежащий подмассиву, на $$$a_i \oplus x$$$ ($$$x$$$ можно выбрать), где $$$\oplus$$$ обозначает операциюпобитового исключающего ИЛИ.

Орехус уже посчитал сходства массивов после каждого изменения. Сможете ли вы?

Обратите внимание, что вам нужно только посчитать эти значения, то есть вам не нужно применять операции.

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$k$$$ и $$$q$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$, $$$0 \le q \le 2 \cdot 10^5$$$) — длина массивов, длина подотрезка, изменяемого при применении операции и число запросов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{14}$$$) — элементы массива $$$a$$$.

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i < 2^{14}$$$) — элементы массива $$$b$$$.

Каждая из следующих $$$q$$$ строк соответствует запросу и содержит строку $$$s$$$ и два целых числа $$$p$$$ и $$$v$$$ ($$$1 \le p \le n$$$, $$$0 \le v < 2^{14}$$$) — название массива («a» или «b» без кавычек), к которому применяется изменение, индекс изменяемого элемента и его новое значение.

Выходные данные

В первой строке выведите сходство массивов $$$a$$$ и $$$b$$$ до применения изменений.

В $$$i$$$-й из следующих $$$q$$$ строк выведите сходство массивов $$$a$$$ и $$$b$$$ после применения первых $$$i$$$ изменений.

Примеры
Входные данные
3 3 1
0 4 2
1 2 3
b 2 5
Выходные данные
-1
1
Входные данные
3 2 2
1 3 2
0 0 0
a 1 0
b 1 1
Выходные данные
2
-1
2
Примечание

В первом примере невозможно с $$$k=3$$$ сделать $$$[0, 4, 2]$$$ и $$$[1, 2, 3]$$$ равными. После модификации можно к первому массиву (его длина равна $$$k$$$) применить операцию с $$$x=1$$$, и он станет равным второму.

Во втором примере, чтобы сделать массивы равными до изменений, можно применить операции с $$$x=1$$$ на подотрезке $$$[1, 2]$$$ к $$$a$$$ и с $$$x=2$$$ к $$$b$$$ на подотрезке $$$[2, 3]$$$.

После всех запросов массивы станут равными $$$[0, 3, 2]$$$ и $$$[1, 0, 0]$$$. Те же операции делают их равными $$$[1, 2, 2]$$$.