English · Original
Chinese · Translation
Formal · Original
**Pay attention to the output section below, where you will see the information about flushing the output.**
Bearland is a grid with _h_ rows and _w_ columns. Rows are numbered 1 through _h_ from top to bottom. Columns are numbered 1 through _w_ from left to right. Every cell is either allowed (denoted by '_._' in the input) or permanently blocked (denoted by '_#_').
Bearland is a cold land, where heavy snow often makes travelling harder. Every day a few allowed cells are **temporarily** blocked by snow. Note, that this block works only on this particular day and next day any of these cells might be allowed again (unless there is another temporarily block).
It's possible to move directly between two cells only if they share a side and none of them is permanently or temporarily blocked.
Limak is a little polar bear who lives in Bearland. His house is at the top left cell, while his school is at the bottom right cell. Every day Limak should first go from his house to the school and then return back to his house. Since he gets bored easily, he doesn't want to **visit the same cell twice** on one day, except for the cell with his house, where he starts and ends. If Limak can reach a school and return home avoiding revisiting cells, he calls a day _interesting_.
There are _q_ days you must process, one after another. For each of these days you should check if it's interesting and print "_YES_" or "_NO_" on a separate line. In order to be able to read the description of the next day you should print the answer for the previous one and flush the output.
It's guaranteed that a day with no cells temporarily blocked by snow would be interesting. It's also guaranteed that cells with Limak's house and school are never blocked (neither permanently or temporarily).
## Input
The first line of the input contains three integers _h_, _w_ and _q_ (2 ≤ _h_, _w_ ≤ 1000, 1 ≤ _q_ ≤ 10 000) — the height and the width of the grid, and the number of days, respectively.
Next _h_ lines describe which cells are allowed and which permanently blocked. The _i_\-th line contains a string of length _w_, describing the _i_\-th row. Every character is either '_._' (denoting an allowed cell) or '_#_' (denoting a permanently blocked cell). It's guaranteed that a day with no cells temporarily blocked by snow would be interesting.
Then, the description of _q_ days is given. The description of the _i_\-th day starts with a line containing a single integer _k__i_ (1 ≤ _k__i_ ≤ 10) — the number of cells that are temporarily blocked by snow on that day. Each of next _k__i_ lines contains two integers _r__i_, _j_ and _c__i_, _j_ (1 ≤ _r__i_, _j_ ≤ _h_, 1 ≤ _c__i_, _j_ ≤ _w_), representing a cell at the intersection of the row _r__i_, _j_ and the column _c__i_, _j_. The given _k__i_ cells are distinct and none of them is permanently blocked. Also, none of them contains Limak's house or school.
## Output
For each of _q_ days print "_YES_" if that day is interesting, and otherwise print "_NO_", both without the quotes. After printing an answer, you have to both print the end-of-line character and _flush_ the output. Then you can proceed to the next day. You can get _Idleness Limit Exceeded_ if you don't print anything or if you forget to flush the output.
To flush you can use (just after printing a _YES/NO_ and end-of-line):
* _fflush(stdout)_ in C++;
* _System.out.flush()_ in Java;
* _stdout.flush()_ in Python;
* _flush(output)_ in Pascal;
* See the documentation for other languages.
[samples]
## Note
In the first sample, there are 4 days. Drawings below show how Limak could go to school and return to his home in the second and the third day (on the left and on the right respectively). A permanently blocked cell is painted red, while cells temporarily blocked by snow are painted orange. Black and green arrows should Limak's way to the school and back to the house respectively.
<center></center>For the second sample, below you can see how the grid looks like on each day, where '_#_' denotes a cell that is blocked, either temporarily or permanently.
<center></center>
*请注意下面的输出部分，其中包含有关刷新输出的信息。*
Bearland 是一个包含 #cf_span[h] 行和 #cf_span[w] 列的网格。行从上到下编号为 #cf_span[1] 到 #cf_span[h]，列从左到右编号为 #cf_span[1] 到 #cf_span[w]。每个单元格要么是允许的（输入中用 '_._' 表示），要么是永久阻塞的（用 '_#_' 表示）。
Bearland 是一个寒冷的地区，大雪常常使旅行变得更加困难。每天，一些允许的单元格会被雪 *临时* 阻塞。请注意，这种阻塞仅在当天有效，第二天这些单元格可能再次允许通行（除非再次被临时阻塞）。
只有当两个单元格共享一条边，且两者均未被永久或临时阻塞时，才能在它们之间直接移动。
Limak 是一只生活在 Bearland 的小北极熊。他的家位于左上角的单元格，而他的学校位于右下角的单元格。每天，Limak 必须先从家前往学校，然后再返回家中。由于他容易感到无聊，他不希望在同一天 *访问同一个单元格两次*，除了他出发和结束的家所在的单元格。如果 Limak 能够在不重复访问单元格的情况下到达学校并返回家中，他就称这一天为 _有趣的_。
你需要处理 #cf_span[q] 天，依次进行。对于每一天，你需要判断它是否有趣，并在单独的一行上打印 "_YES_" 或 "_NO_"。为了能够读取下一天的描述，你必须先打印出前一天的答案并刷新输出。
保证在没有任何单元格被雪临时阻塞的情况下，这一天是有趣的。同时保证 Limak 的家和学校的单元格永远不会被阻塞（无论是永久还是临时）。
输入的第一行包含三个整数 #cf_span[h], #cf_span[w] 和 #cf_span[q]（#cf_span[2 ≤ h, w ≤ 1000], #cf_span[1 ≤ q ≤ 10 000]）——网格的高度、宽度和天数。
接下来的 #cf_span[h] 行描述哪些单元格是允许的，哪些是永久阻塞的。第 #cf_span[i] 行包含一个长度为 #cf_span[w] 的字符串，描述第 #cf_span[i] 行。每个字符要么是 '_._'（表示允许的单元格），要么是 '_#_'（表示永久阻塞的单元格）。保证在没有任何单元格被雪临时阻塞的情况下，这一天是有趣的。
然后给出 #cf_span[q] 天的描述。第 #cf_span[i] 天的描述以一行开始，包含一个整数 #cf_span[ki]（#cf_span[1 ≤ ki ≤ 10]）——当天被雪临时阻塞的单元格数量。接下来的 #cf_span[ki] 行每行包含两个整数 #cf_span[ri, j] 和 #cf_span[ci, j]（#cf_span[1 ≤ ri, j ≤ h], #cf_span[1 ≤ ci, j ≤ w]），表示位于第 #cf_span[ri, j] 行和第 #cf_span[ci, j] 列的单元格。给定的 #cf_span[ki] 个单元格互不相同，且都不是永久阻塞的，也不包含 Limak 的家或学校。
对于 #cf_span[q] 天中的每一天，如果这一天是有趣的，则打印 "_YES_"，否则打印 "_NO_"，均不带引号。打印答案后，必须打印换行符并 _刷新_ 输出，然后才能继续处理下一天。如果你不打印任何内容或忘记刷新输出，可能会得到 _空闲时间超限_ 错误。
要刷新输出，可以在打印完 _YES/NO_ 和换行符后使用：
在第一个样例中，有 #cf_span[4] 天。下图显示了 Limak 在第二天和第三天如何前往学校并返回家中（分别在左和右）。永久阻塞的单元格用红色表示，被雪临时阻塞的单元格用橙色表示。黑色和绿色箭头分别表示 Limak 前往学校和返回家中的路径。
对于第二个样例，下图显示了每天网格的状况，其中 '_#_' 表示被阻塞的单元格（无论是临时还是永久）。
## Input
输入的第一行包含三个整数 #cf_span[h], #cf_span[w] 和 #cf_span[q]（#cf_span[2 ≤ h, w ≤ 1000], #cf_span[1 ≤ q ≤ 10 000]）——网格的高度、宽度和天数。接下来的 #cf_span[h] 行描述哪些单元格是允许的，哪些是永久阻塞的。第 #cf_span[i] 行包含一个长度为 #cf_span[w] 的字符串，描述第 #cf_span[i] 行。每个字符要么是 '_._'（表示允许的单元格），要么是 '_#_'（表示永久阻塞的单元格）。保证在没有任何单元格被雪临时阻塞的情况下，这一天是有趣的。然后给出 #cf_span[q] 天的描述。第 #cf_span[i] 天的描述以一行开始，包含一个整数 #cf_span[ki]（#cf_span[1 ≤ ki ≤ 10]）——当天被雪临时阻塞的单元格数量。接下来的 #cf_span[ki] 行每行包含两个整数 #cf_span[ri, j] 和 #cf_span[ci, j]（#cf_span[1 ≤ ri, j ≤ h], #cf_span[1 ≤ ci, j ≤ w]），表示位于第 #cf_span[ri, j] 行和第 #cf_span[ci, j] 列的单元格。给定的 #cf_span[ki] 个单元格互不相同，且都不是永久阻塞的，也不包含 Limak 的家或学校。
## Output
对于 #cf_span[q] 天中的每一天，如果这一天是有趣的，则打印 "_YES_"，否则打印 "_NO_"，均不带引号。打印答案后，必须打印换行符并 _刷新_ 输出，然后才能继续处理下一天。如果你不打印任何内容或忘记刷新输出，可能会得到 _空闲时间超限_ 错误。要刷新输出，可以在打印完 _YES/NO_ 和换行符后使用：
_fflush(stdout)_ 在 C++ 中；
_System.out.flush()_ 在 Java 中；
_stdout.flush()_ 在 Python 中；
_flush(output)_ 在 Pascal 中；
其他语言请参阅文档。
[samples]
## Note
在第一个样例中，有 #cf_span[4] 天。下图显示了 Limak 在第二天和第三天如何前往学校并返回家中（分别在左和右）。永久阻塞的单元格用红色表示，被雪临时阻塞的单元格用橙色表示。黑色和绿色箭头分别表示 Limak 前往学校和返回家中的路径。
对于第二个样例，下图显示了每天网格的状况，其中 '_#_' 表示被阻塞的单元格（无论是临时还是永久）。
**Definitions**
Let $ h, w \in \mathbb{Z}^+ $ be the height and width of the grid.
Let $ G = (V, E) $ be the grid graph where:
- $ V = \{ (i,j) \mid 1 \leq i \leq h,\ 1 \leq j \leq w,\ \text{cell } (i,j) \text{ is not permanently blocked} \} $,
- $ E = \{ ((i,j), (i',j')) \mid |i-i'| + |j-j'| = 1,\ (i,j), (i',j') \in V \} $.
Let $ s = (1,1) $ be the start (house) and $ t = (h,w) $ be the target (school).
Let $ Q \in \mathbb{Z}^+ $ be the number of days.
For each day $ d \in \{1, \dots, Q\} $:
- Let $ B_d \subseteq V \setminus \{s, t\} $ be the set of $ k_d $ cells temporarily blocked on day $ d $.
- Let $ G_d = (V_d, E_d) $ be the subgraph of $ G $ induced by $ V_d = V \setminus B_d $.
**Constraints**
1. $ 2 \leq h, w \leq 1000 $, $ 1 \leq Q \leq 10{,}000 $
2. $ 1 \leq k_d \leq 10 $ for each day $ d $
3. $ s, t \notin B_d $ for all $ d $
4. The graph $ G $ (with no temporary blocks) admits two vertex-disjoint paths from $ s $ to $ t $ (except at $ s $ and $ t $).
**Objective**
For each day $ d $, determine whether there exist two vertex-disjoint paths (sharing only $ s $ and $ t $) from $ s $ to $ t $ in $ G_d $.
Output "YES" if such paths exist, "NO" otherwise.
API Response (JSON)
{
"problem": {
"name": "H. New Year and Snowy Grid",
"description": {
"content": "**Pay attention to the output section below, where you will see the information about flushing the output.** Bearland is a grid with _h_ rows and _w_ columns. Rows are numbered 1 through _h_ from top",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 9000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF750H"
},
"statements": [
{
"statement_type": "Markdown",
"content": "**Pay attention to the output section below, where you will see the information about flushing the output.**\n\nBearland is a grid with _h_ rows and _w_ columns. Rows are numbered 1 through _h_ from top...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "*请注意下面的输出部分，其中包含有关刷新输出的信息。*\n\nBearland 是一个包含 #cf_span[h] 行和 #cf_span[w] 列的网格。行从上到下编号为 #cf_span[1] 到 #cf_span[h]，列从左到右编号为 #cf_span[1] 到 #cf_span[w]。每个单元格要么是允许的（输入中用 '_._' 表示），要么是永久阻塞的（用 '_#_' 表示）。\n\nBear...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ h, w \\in \\mathbb{Z}^+ $ be the height and width of the grid. \nLet $ G = (V, E) $ be the grid graph where: \n- $ V = \\{ (i,j) \\mid 1 \\leq i \\leq h,\\ 1 \\leq j \\leq w,\\ \\text{cel...",
"is_translate": false,
"language": "Formal"
}
]
}