C. Desk Arrangement
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

LexMACS needs your help! There have been rumors of an in-person LIT, causing a multitude of desks to be purchased. Their arrangement on an $$$n$$$ by $$$m$$$ tile floor, where each tile is either fully below a desk or empty, can be shown through a binary grid, where a $$$1$$$ denotes the presence of a desk and a $$$0$$$ denotes the absence of a desk. The floor has walls on its edges, meaning that both competitors and proctors cannot go off the floor.

However, preemptive measures against cheaters have been placed. The room's proctor will initially teleport to an empty tile, and move to other adjacent, empty tiles as much as they want. A proctor is able to check a competitor and their desk for cheating if they are able to stand directly adjacent to the desk.

Help the proctor determine if a certain location for initial teleportation is effective for stopping cheaters, that is, whether the proctor can check each desk!

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 100)$$$, representing the number of test cases.

The first line of each test cases contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 10^5)$$$, the number of rows and columns of tiles in the room respectively.

The next $$$n$$$ lines of the test case each contain a string of length $$$m$$$, where $$$1$$$ denotes the presence of a desk at that tile and $$$0$$$ denotes its absence. It is guaranteed that there would be at least one desk in the room.

The next line of the test case contains $$$q$$$ $$$(1 \leq q \leq 10^5)$$$, the number of teleportation locations you will be given.

Each of the next $$$q$$$ lines of the test case contain $$$r$$$ and $$$c$$$ $$$(1 \leq r \leq n, 1 \leq c \leq m)$$$, respectively the row and column where the proctor will initially teleport.

It is guaranteed that the both the sum of $$$nm$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

In response to each initial teleportation location, output "YES" without quotes if teleporting to that location is effective for stopping cheaters and "NO" without quotes otherwise.

Scoring
SubtaskConstraintPoints
$$$1$$$$$$n,m,q \leq 100,\;\sum nm \leq 5 \cdot 10^4,\;\sum q \leq 500$$$$$$20$$$
$$$2$$$No additional constraints$$$80$$$
Example
Input
1
6 6
101001
001010
000100
110010
000100
000001
2
1 5
4 4
Output
NO
YES
Note

For the first location, the proctor will teleport to the tile in the first row and the fifth column. The grid can be seen below, where "X" denotes the location of the proctor after initially teleporting.


1010X1
001010
000100
110010
000100
000001

It can be shown that the proctor can move to the following locations below, denoted by an "X". The proctor is able to check the desks marked with a "C".


10CXXC
00CXC0
000C00
110010
000100
000001

Thus, the answer is "NO" for the first query, as the proctor is not able to check all desks, making their initial teleportation to that location ineffective for stopping cheaters.

For the second location, it can be shown that the proctor can check all desks, making their teleportation to the tile on the fourth row and the fourth column effective for stopping cheaters.