给定一个整数 $$$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$$$。之后,对于 $$$F$$$ 覆盖的每个单元格 $$$(i, j)$$$,将 $$$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$$$,并对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$ 替换单元格中的数字 $$$(((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$$$。我们能实现吗?如果可以的话,找到可以做到这一点的最少操作数。
输入
第一行包含一个整数 $$$k$$$ ($$$1 \le k \le 9$$$)。
接下来的 $$$2^k$$$ 行中的第 $$$i$$$ 包含 $$$2^k$$$ 整数 $$$a_{i1}, a_{i2}, \dots, a_{i2^k}$$$ ($$$0 \le a_{ij} < 2^{60}$$$) — 第 $$$i$$$ 中的初始值网格的行。
下一行包含一个整数 $$$t$$$ ($$$1\le t \le \min(99, 4^k)$$$, $$$t$$$ 是奇数) — 图形的单元格数量。
接下来的 $$$t$$$ 行的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le 2^k$$$),描述图中第 $$$i$$$ 个单元格的位置。
保证所有单元格都不同,但不保证图形是相连的。
输出
如果通过这些操作无法使网格中的所有数字都等于$$$0$$$,则输出$$$-1$$$。
否则,输出一个整数 - 执行此操作所需的最少操作数。可以证明,如果可以使所有数字等于 $$$0$$$,则可以在少于 $$$10^{18}$$$ 操作中完成此操作。
示例
输入 #1
2 5 5 5 5 2 6 2 3 0 0 2 0 0 0 0 0 5 1 1 1 2 1 3 1 4 2 4
输出 #1
3
注意
示例图及操作如上所示: