Дано целое число \(k\) и доска \(2^k \times 2^k\), в клетках которой записаны числа, клетка \((i, j)\) изначально содержит число \(a_{ij}\). Доска считается тором, то есть, клетка справа от \((i, 2^k)\) это \((i, 1)\), а клетка вниз от \((2^k, i)\) это \((1, i)\). Также дана клетчатая фигурка \(F\), состоящая из \(t\) клеток, где \(t\) нечетное. \(F\) не обязана быть связной.
Мы можем выполнять следующую операцию: положить \(F\) на доску (разрешены только параллельные переносы, повороты и симметрии запрещены). Теперь выберите произвольное неотрицательное число \(p\). После этого, для каждой клетки \((i, j)\), покрытой \(F\), замените \(a_{ij}\) на \(a_{ij}\oplus p\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Более формально, пусть \(F\) задана клетками \((x_1, y_1), (x_2, y_2), \dots, (x_t, y_t)\). Тогда вы можете проделать следующую операцию: выбрать любые \(x, y\) с \(1\le x, y \le 2^k\), любое неотрицательное число \(p\), и для каждого \(i\) от \(1\) до \(n\) заменить число в клетке \((((x + x_i - 1)\bmod 2^k) + 1, ((y + y_i - 1)\bmod 2^k) + 1)\) на \(a_{((x + x_i - 1)\bmod 2^k) + 1, ((y + y_i - 1)\bmod 2^k) + 1}\oplus p\).
Мы хотим сделать все числа равными \(0\). Можем ли мы этого достичь? Если да, то найдите наименьшее возможное число операций, с помощью которых этого можно добиться.
Выходные данные
Если невозможно сделать все числа на доске равными \(0\) с этими операциями, выведите \(-1\).
Иначе, выведите единственное число — минимальное количество операций, необходимых, чтобы это сделать. Можно показать, что если возможно сделать все числа равными \(0\), это можно сделать за не более чем \(10^{18}\) операций.