J. Square Flip Queries
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an $$$n \times n$$$ grid of bits (each cell is either 0 or 1). Initially, the grid is filled with 0.

The grid is placed on a torus: row and column indices are taken modulo $$$n$$$. Formally, for any integer $$$x$$$ define $$$ wrap(x) = ((x-1) \bmod n) + 1. $$$

You may apply the following operation any number of times:

  • choose a size $$$s \in \{2, k\}$$$ and a top-left cell $$$(i, j)$$$ ($$$1 \le i,j \le n$$$),
  • for all $$$0 \le a,b \lt s$$$, flip the cell $$$ (\,wrap(i+a),\; wrap(j+b)\,) $$$ (i.e. 0 becomes 1, 1 becomes 0).

You are given $$$q$$$ target grids. For each target grid, determine whether it can be obtained from the all-zero grid using the operations above.

Input

The first line contains three integers $$$n$$$, $$$k$$$, $$$q$$$: $$$ 3 \le n \le 2000,\quad 3 \le k \le n,\quad k \text{ is odd},\quad 1 \le q \le 2000. $$$ Additionally, it is guaranteed that $$$ q \cdot n^2 \le 2 \cdot 10^7. $$$ Then follow $$$q$$$ grids. Each grid is given by $$$n$$$ lines, each containing a string of length $$$n$$$ consisting only of characters 0 and 1.

Output

Print $$$q$$$ lines. For each grid, print YES if it is reachable from the all-zero grid, otherwise print NO.

Example
Input
3 3 3
000
000
000
111
111
111
100
000
000
Output
YES
YES
NO