CF1270I.Xor on Figures

There is given an integer $k$ and a grid $2^k \times 2^k$ with some numbers written in its cells, cell $(i, j)$ initially contains number $a_{ij}$. Grid is considered to be a torus, that is, the cell to the right of $(i, 2^k)$ is $(i, 1)$, the cell below the $(2^k, i)$ is $(1, i)$ There is also given a lattice figure $F$, consisting of $t$ cells, where $t$ is odd. $F$ doesn't have to be connected.

We can perform the following operation: place $F$ at some position on the grid. (Only translations are allowed, rotations and reflections are prohibited). Now choose any nonnegative integer $p$. After that, for each cell $(i, j)$, covered by $F$, replace $a_{ij}$ by $a_{ij}\oplus p$, where $\oplus$ denotes the bitwise XOR operation.

More formally, let $F$ be given by cells $(x_1, y_1), (x_2, y_2), \dots, (x_t, y_t)$. Then you can do the following operation: choose any $x, y$ with $1\le x, y \le 2^k$, any nonnegative integer $p$, and for every $i$ from $1$ to $n$ replace number in the cell $(((x + x_i - 1)\bmod 2^k) + 1, ((y + y_i - 1)\bmod 2^k) + 1)$ with $a_{((x + x_i - 1)\bmod 2^k) + 1, ((y + y_i - 1)\bmod 2^k) + 1}\oplus p$.

Our goal is to make all the numbers equal to $0$. Can we achieve it? If we can, find the smallest number of operations in which it is possible to do this.

给定一个整数 $k$ 和一个 $2^k \times 2^k$ 的网格，其中某些格子中写有数字；初始时，格子 $(i, j)$ 中的数字为 $a_{ij}$。该网格被视为环面（torus），即：$(i, 2^k)$ 右侧的格子为 $(i, 1)$，$(2^k, i)$ 下方的格子为 $(1, i)$。此外，还给定一个由 $t$ 个格子组成的格点图形 $F$，其中 $t$ 为奇数；$F$ 不必连通。

我们可以执行如下操作：将 $F$ 放置在网格上的某个位置（仅允许平移，禁止旋转与反射）。随后任选一个非负整数 $p$；接着，对 $F$ 所覆盖的每个格子 $(i, j)$，将其中的数 $a_{ij}$ 替换为 $a_{ij}\oplus p$，其中 $\oplus$ 表示按位异或运算（bitwise XOR）。

更形式化地，设 $F$ 由格子 $(x_1, y_1), (x_2, y_2), \dots, (x_t, y_t)$ 组成。则可执行如下操作：任选满足 $1\le x, y \le 2^k$ 的整数 $x, y$，任选非负整数 $p$，并对每个 $i = 1, 2, \dots, t$，将格子

$$(((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}$$

替换为

$$a_{((x + x_i - 1)\bmod 2^k) + 1,\; ((y + y_i - 1)\bmod 2^k) + 1}\oplus p.$$

我们的目标是使网格中所有数字均变为 $0$。能否实现这一目标？若能，请找出达成目标所需的最少操作次数。

The first line contains a single integer $k$ ($1 \le k \le 9$).

The $i$-th of the next $2^k$ lines contains $2^k$ integers $a_{i1}, a_{i2}, \dots, a_{i2^k}$ ($0 \le a_{ij} \lt 2^{60}$) — initial values in the $i$-th row of the grid.

The next line contains a single integer $t$ ($1\le t \le \min(99, 4^k)$, $t$ is odd) — number of cells of figure.

$i$-th of next $t$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le 2^k$), describing the position of the $i$-th cell of the figure.

It is guaranteed that all cells are different, but it is not guaranteed that the figure is connected.

第一行包含一个整数 $k$（$1 \le k \le 9$）。

接下来的 $2^k$ 行中，第 $i$ 行包含 $2^k$ 个整数 $a_{i1}, a_{i2}, \dots, a_{i2^k}$（$0 \le a_{ij} \lt 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$ 个格子的位置。

保证所有格子互不相同，但不保证该图形是连通的。

If it is impossible to make all numbers in the grid equal to $0$ with these operations, output $-1$.

Otherwise, output a single integer — the minimal number of operations needed to do this. It can be shown that if it is possible to make all numbers equal $0$, it is possible to do so in less than $10^{18}$ operations.

如果无法通过这些操作使网格中的所有数字都变为 $0$，则输出 $-1$。

否则，输出一个整数——完成此目标所需的最少操作次数。可以证明：如果能够将所有数字变为 $0$，那么一定能在少于 $10^{18}$ 次操作内完成。

The figure and the operations for the example are shown above:

上图展示了示例中的图形及对应操作：