409026: GYM103416 F Delivery 2[D]

You are a pizza delivery courier at Yankeks. The region you are working in can be represented as an $$$n \times m$$$ grid. Each cell of the grid is either empty or occupied.

You can move only between neighboring empty cells. Two cells are considered as neighboring if they share a side.

You are given $$$q$$$ queries of the following types:

• $$$0$$$ $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$
  • Make all cells $$$(x, y)$$$ which satisfy $$$x_1 \leq x \leq x_2$$$ and $$$y_1 \leq y \leq y_2$$$ empty.
  • $$$1 \leq x_1, x_2 \leq n$$$.
  • $$$1 \leq y_1, y_2 \leq m$$$.

• $$$1$$$
  • Cancel the last query of type 0.
  • It is guaranteed that there exists a non-cancelled query of type 0.

• $$$2$$$ $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$
  • Determine if you can deliver a pizza from cell $$$(x_1, y_1)$$$ to cell $$$(x_2, y_2)$$$.
  • $$$1 \leq x_1, x_2 \leq n$$$.
  • $$$1 \leq y_1, y_2 \leq m$$$.
  • It is guaranteed that cells $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ are empty.

Your task is to answer all queries of type 2.

The first line contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq n, m \leq 1000$$$) — the dimensions of the grid.

$$$n$$$ lines follow. The $$$i$$$-th line contains $$$m$$$ characters, the $$$j$$$-th of which is "1" if the cell on the intersection of the $$$i$$$-th row and the $$$j$$$-th column is occupied and "0" if it is empty.

The next line contains an integer $$$q$$$ ($$$1 \leq q \leq 20000$$$) — the number of queries.

The next q lines contain queries in the format described above.

For each query of type 2, print "YES" (without brackets) if it is possible to deliver a pizza, or "NO" (without brackets) otherwise.

5 5
00100
00100
11111
00000
11100
8
2 1 1 5 5
2 1 5 5 5
0 3 1 3 2
0 3 5 3 5
2 1 2 4 3
2 2 5 4 3
1
2 1 5 5 5

NO
NO
YES
YES
NO

13 13
0000000000000
0001100011000
0001110011000
0001101011000
0001100111000
0001100011000
0000000000000
0001100011000
0001100011000
0001100011000
0001100011000
0001111111000
0000000000000
1
2 1 1 13 13

YES