O. Not JOI again
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an $$$n \times n$$$ grid where each cell has a label of $$$0$$$ or $$$1$$$. You are given $$$q$$$ operations, each specifying a cell whose label is flipped (from $$$0$$$ to $$$1$$$, or from $$$1$$$ to $$$0$$$). After each operation, determine whether it is possible to travel from cell $$$(1, 1)$$$ to cell $$$(n, n)$$$ by only traversing cells labeled $$$1$$$, moving between adjacent cells.

This problem must be solved online. Each query is given as a cell $$$(x, y)$$$, but the true cell is determined using the previous $$$\mathrm{num}$$$ answers. Specifically, you are given $$$\mathrm{num}$$$ pairs $$$(u_i, v_i)$$$ for $$$i = 0, 1, \ldots, 2^{\mathrm{num}} - 1$$$. Let $$$\mathrm{val}$$$ be the integer formed by writing the previous $$$\mathrm{num}$$$ answers in order from oldest to most recent as a binary string, where $$$\text{YES} = 1$$$ and $$$\text{NO} = 0$$$, and interpreting it as a binary number with the oldest answer as the most significant bit and the most recent answer as the least significant bit. Any answer that does not yet exist is treated as $$$\text{NO}$$$. Then the true cell is: $$$$$$x' = \begin{cases} x + u_{\mathrm{val}} - n & \text{if } x + u_{\mathrm{val}} \gt n \\ x + u_{\mathrm{val}} & \text{otherwise} \end{cases}$$$$$$ $$$$$$y' = \begin{cases} y + v_{\mathrm{val}} - n & \text{if } y + v_{\mathrm{val}} \gt n \\ y + v_{\mathrm{val}} & \text{otherwise} \end{cases}$$$$$$

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$).

The next $$$n$$$ lines each consist of a length $$$n$$$ binary string, representing the initial state of the $$$n \times n$$$ grid.

The next line contains two integers $$$q$$$ and $$$\mathrm{num}$$$ ($$$1 \le q \le 2000$$$, $$$1 \le \mathrm{num} \le 15$$$).

The next $$$2^{\mathrm{num}}$$$ lines each contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$0 \le u_i, v_i \lt n$$$).

The next $$$q$$$ lines each contain two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$), denoting the cell to flip.

—

Tests are numbered from $$$1-20$$$ and each test is worth $$$5$$$ points.

Tests $$$1-2$$$ satisfy $$$n, q \le 500$$$.

Tests $$$3-8$$$ satisfy $$$\mathrm{num} = 1$$$ and $$$u_0, u_1, v_0, v_1 = 0$$$. That is, you can solve the problem offline.

Tests $$$9-20$$$ satisfy no additional constraints.

Output

Output $$$q$$$ lines, where the $$$i$$$-th line contains "YES" or "NO" indicating whether cell $$$(1,1)$$$ can reach cell $$$(n,n)$$$ after the $$$i$$$-th operation.

Examples
Input
3
101
010
111
3 1
0 2
1 1
3 2
1 3
2 2
Output
NO
YES
NO
Input
5
01010
11111
11011
10100
11011
5 1
0 0
0 0
1 1
5 3
5 4
4 5
2 2
Output
NO
YES
NO
YES
NO
Note

For the first sample, the points that are actually operated after the online constraint are $$$(3,1), (1,2), (3,3)$$$

—

Problem Idea: willy108

Problem Preparation: gg_gong

Occurrences: Advanced K