У Орехуса есть два массива \(a\) и \(b\) из \(n\) чисел каждый. Он нашёл их так давно, что никто уже не знает, когда они у него появились.
Орехус часто меняет числа в массивах. Кроме того, после каждого изменения ему интересно, насколько похожи массивы \(a\) и \(b\).
Сходство массивов — это минимальное количество операций, которые нужно применить к массивам (каждую операцию можно применять как к первому массиву, так и ко второму), чтобы сделать их равными. Если это сделать невозможно, сходство равно \(-1\).
За одну операцию можно выбрать подмассив длины \(k\) (\(k\) фиксированно), и заменить каждый элемент \(a_i\), принадлежащий подмассиву, на \(a_i \oplus x\) (\(x\) можно выбрать), где \(\oplus\) обозначает операциюпобитового исключающего ИЛИ.
Орехус уже посчитал сходства массивов после каждого изменения. Сможете ли вы?
Обратите внимание, что вам нужно только посчитать эти значения, то есть вам не нужно применять операции.
Выходные данные
В первой строке выведите сходство массивов \(a\) и \(b\) до применения изменений.
В \(i\)-й из следующих \(q\) строк выведите сходство массивов \(a\) и \(b\) после применения первых \(i\) изменений.
Примечание
В первом примере невозможно с \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 1
0 4 2
1 2 3
b 2 5
|
-1
1
|
|
2
|
3 2 2
1 3 2
0 0 0
a 1 0
b 1 1
|
2
-1
2
|