Xor on Figures
Contest: Good Bye 2019
Difficulty rating: 3500
Tags: constructive algorithms, fft, math

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.

Input format:
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} < 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.

Output format:
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.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

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

Example input:
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

Example output:
3

Editorial:
Let's fix first cell of fiqure  — $$$(x_1, y_1)$$$. Then if figure is lied in a such way, that first cell will be cell $$$(p,q)$$$ of the original board, other figure cells will be in the cells $$$(a + x_i - x_1, b + y_i - y_1)$$$ of the original board. Let's name such shifts $$$(x_i - x_1, y_i - y_1)$$$ as $$$(c_i, d_i)$$$. Then let's compute value $$$f[p, q] = \oplus a_{p - c_i, q - d_i}$$$ for $$$i = 1 \ldots t$$$(all additions are done modulo $$$2^k$$$).
$$$\textbf{Lemma 1}$$$
If all numbers $$$f[p, q] = 0$$$, then all numbers in original array are zero too.
It will be proved in the end.
So our aim is to get zero array $$$f$$$.
$$$\textbf{Lemma 2}$$$
Assume, that we use operation in a such way that, that first figure cell is in $$$(p, q)$$$. Then values of $$$f$$$ will change in a such way:
For all $$$p', q'$$$ of the form $$$p + 2\cdot c_i, q + 2\cdot d_i$$$ $$$f[p', q']$$$ values will xor with $$$x$$$, for other it will not change.
Consider cell $$$(p', q')$$$. Then $$$f'[p', q'] = f[p', q'] \oplus (x \oplus x \ldots \oplus x)$$$, where we xor with $$$x$$$ for all pair $$$i, j$$$ such that $$$(p' - c_i, q' - d_i) = (p + c_j, q + d_j)$$$. Note, that if pair $$$i, j$$$ is suitable, then pair $$$j, i$$$ is suitable too. So, because $$$x \oplus x = 0$$$, we can only have non-xored pairs $$$i, i$$$ in the end, but then $$$p', q'$$$ looks like $$$p + 2\cdot c_i, q + 2\cdot d_i$$$ for some $$$i$$$.
We get that task for array $$$a$$$ is equivalent for task with array $$$f$$$ with figure scaled two times. Note that in this case, if we xor on some figure we change only cells with one parity of coordinates, so we can solve this task independently for $$$4$$$ boards of size $$$2^(k-1)$$$ (also, some cells of figure can map to the same one, then we should not use them).
It's only left to show that if $$$f$$$ is zero, then $$$a$$$ is also zero.It's sufficient to show that for any values of $$$f$$$ we can get zero array(follow from linear algebra, both facts are equivalent to fact that $$$f$$$ is non-degenerate transform). But this statement can be easily proved using induction on $$$k$$$, because if we get all zeroes for problem with $$$k - 1$$$, then they will be zeroes in array $$$f$$$ too. In the end we get $$$k=0$$$ and figure with one cell(because $$$t$$$ is odd). We can get zero in one operation.
Also, from non-degenerativity it follow that answer is unique(if we xor on each figure at most once).