CF1083F.The Fair Nut and Amusing Xor

The Fair Nut has two arrays $a$ and $b$, consisting of $n$ numbers. He found them so long ago that no one knows when they came to him.

The Fair Nut often changes numbers in his arrays. He also is interested in how similar $a$ and $b$ are after every modification.

Let's denote similarity of two arrays as the minimum number of operations to apply to make arrays equal (every operation can be applied for both arrays). If it is impossible, similarity will be equal $-1$.

Per one operation you can choose a subarray with length $k$ ($k$ is fixed), and change every element $a_i$, which belongs to the chosen subarray, to $a_i \oplus x$ ($x$ can be chosen), where $\oplus$ denotes the bitwise XOR operation.

Nut has already calculated the similarity of the arrays after every modification. Can you do it?

Note that you just need to calculate those values, that is you do not need to apply any operations.

公平坚果有两组数组 $a$ 和 $b$，每组均包含 $n$ 个数字。这两组数组早已存在，以至于无人知晓它们何时来到他手中。

公平坚果经常修改其数组中的数字。同时，他也关心每次修改后数组 $a$ 与 $b$ 的相似程度。

我们定义两个数组的相似度为：使这两个数组相等所需执行的最少操作次数（每次操作可同时作用于两个数组）。若无法使两数组相等，则相似度定义为 $-1$。

每次操作中，你可以选择一个长度为 $k$ 的子数组（$k$ 是固定的），并将该子数组中每个元素 $a_i$ 替换为 $a_i \oplus x$（其中 $x$ 可任选），此处 $\oplus$ 表示按位异或运算。

公平坚果已对每次修改后的数组计算出了相似度。你也能做到吗？

注意：你只需计算这些相似度的值，即无需实际执行任何操作。

The first line contains three numbers $n$, $k$ and $q$ ($1 \le k \le n \le 2 \cdot 10^5$, $0 \le q \le 2 \cdot 10^5$) — the length of the arrays, the length of the subarrays, to which the operations are applied, and the number of queries.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \lt 2^{14}$) — elements of array $a$.

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \le b_i \lt 2^{14}$) — elements of array $b$.

Each of the next $q$ lines describes query and contains string $s$ and two integers $p$ and $v$ ($1 \le p \le n$, $0 \le v \lt 2^{14}$) — array, which this query changes («a» or «b» without quotes), index of changing element and its new value.

第一行包含三个整数 $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 \lt 2^{14}$）——数组 $a$ 的元素。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$0 \le b_i \lt 2^{14}$）——数组 $b$ 的元素。

接下来的 $q$ 行每行描述一个查询，包含一个字符串 $s$ 和两个整数 $p$、$v$（$1 \le p \le n$，$0 \le v \lt 2^{14}$）——分别表示本次查询所修改的数组（为 «a» 或 «b»，不带引号）、待修改元素的下标以及其新值。

On the first line print initial similarity of arrays $a$ and $b$.

On the $i$-th of following $q$ lines print similarity of $a$ and $b$ after applying first $i$ modifications.

在第一行输出数组 $a$ 和 $b$ 的初始相似度。

在接下来的 $q$ 行中，第 $i$ 行输出对 $a$ 和 $b$ 执行前 $i$ 次修改后的相似度。

In the first sample making arrays $[0, 4, 2]$ and $[1, 2, 3]$ is impossible with $k=3$. After the modification, you can apply the operation with $x=1$ to the whole first array (its length is equal to $k$), and it will be equal to the second array.

In order to make arrays equal in the second sample before changes, you can apply operations with $x=1$ on subarray $[1, 2]$ of $a$ and with $x=2$ on subarray $[2, 3]$ of $b$.

After all queries arrays will be equal $[0, 3, 2]$ and $[1, 0, 0]$. The same operations make them equal $[1, 2, 2]$.

在第一个样例中，当 $k=3$ 时，无法通过操作将数组 $[0, 4, 2]$ 和 $[1, 2, 3]$ 变为相等。修改后，你可以对第一个数组（其长度等于 $k$）整体应用 $x=1$ 的操作，使其变为第二个数组。

在第二个样例中，为使修改前的两个数组相等，你可以在 $a$ 的子数组 $[1, 2]$ 上应用 $x=1$ 的操作，并在 $b$ 的子数组 $[2, 3]$ 上应用 $x=2$ 的操作。

所有查询执行完毕后，两个数组将分别为 $[0, 3, 2]$ 和 $[1, 0, 0]$。同样的操作可使它们均变为 $[1, 2, 2]$。