409026: GYM103416 F Delivery 2[D]
Description
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.
InputThe 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.
OutputFor each query of type 2, print "YES" (without brackets) if it is possible to deliver a pizza, or "NO" (without brackets) otherwise.
ExamplesInput5 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 5Output
NO NO YES YES NOInput
13 13 0000000000000 0001100011000 0001110011000 0001101011000 0001100111000 0001100011000 0000000000000 0001100011000 0001100011000 0001100011000 0001100011000 0001111111000 0000000000000 1 2 1 1 13 13Output
YES