Fair Nut 有两个数组 $$$a$$$ 和 $$$b$$$,由 $$$n$$$ 数字组成。他很久以前就发现了它们,以至于没有人知道它们是什么时候找到他的。
公平坚果经常改变他的数组中的数字。他还对每次修改后 $$$a$$$ 和 $$$b$$$ 的相似程度感兴趣。
让我们将两个数组的相似性表示为使数组相等所应用的最小操作数(每个操作都可以应用于两个数组)。如果不可能,相似度将等于$$$-1$$$。
每一次操作可以选择一个长度为 $$$k$$$ 的子数组($$$k$$$ 是固定的),并将属于所选子数组的每个元素 $$$a_i$$$ 更改为 $$$a_i \oplus x$$$ ($$$x$$$ 可以选择),其中 $$$\oplus$$$ 表示按位异或运算。
Nut已经计算了每次修改后数组的相似度。你能做到吗?
请注意,您只需要计算这些值,即不需要应用任何操作。
输入
第一行包含三个数字 $$$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$$$ 行的第 $$$i$$$ 行上打印 $$$a$$$ 和 $$$b$$$ 的相似性。
示例
输入 #1
3 3 1 0 4 2 1 2 3 b 2 5
输出 #1
-1 1
输入 #2
3 2 2 1 3 2 0 0 0 a 1 0 b 1 1
输出 #2
2 -1 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]$$$。