← 返回题目列表

AtCoder · bitflyer2018_final_f

F. 交付难题

中文机器翻译题面 查看原题

配点 : 800 点

問題文

斯努克君,Q 打算在若干天内,每天解如下谜题。

  • 斯努克君所持有的终端,每天都会收到由纵 H 行、横 W 列组成的格状棋盘。每个格子要么涂白,要么涂黑。但是,i+1 日目 (1 ≤ i ≤ Q-1分发到) 的棋盘是,i 第 日收到的棋盘,从上方 r_i 第 行从左开始 c_i 列的格子的黑白颜色会被反转。
  • 对于传送过来的棋盘,Sukune君一开始最多 1 可以指定棋盘中的矩形区域,并将该区域内所有格子的黑白颜色反转。
  • 之后,Sukune君可以 1 选择某一行或某一列,并将其中所有格子的黑白颜色反转,这样的操作可以进行任意次数。
  • 目标是使棋盘上的所有格子颜色相同。

Sukune君很聪明,所以他察觉到在传送过来的棋盘中,肯定会存在无法解开的情况。因此,请代替Sukune君,判断每天的棋盘是否存在将所有格子颜色变得相同的方法。

但是,1 第n天传送的棋盘,从上到下 i 行目 (1 ≤ i ≤ H) 从左到右 j 列目 (1 ≤ j ≤ W) 的格子是,s_{ij} 被给予 . 时为白色, # 时为黑色涂。

制約

  • 1 ≤ H ≤ 2\,000
  • 1 ≤ W ≤ 2\,000
  • 1 ≤ Q ≤ 300\,000
  • s_{ij} 为 . 或 上面写着字符 #
  • 1 ≤ r_i ≤ H (1 ≤ i ≤ Q-1)
  • 1 ≤ c_i ≤ W (1 ≤ i ≤ Q-1)

入力

输入将以以下格式从标准输入给出。

H W Q
s_{11}s_{12}...s_{1W}
:
s_{H1}s_{H2}...s_{HW}
r_1 c_1
:
r_{Q-1} c_{Q-1}

出力

Q 输出行。 i 行目 (1 ≤ i ≤ Q) 中,i 若存在让第 N 天的棋盘上所有格子涂成同一颜色的方法, Yes 若不存在则 No 。


入力例 1

3 4 4
...#
.###
.#.#
3 1
2 4
2 2

出力例 1

No
No
No
Yes

4 第 N 天的棋盘是可以让所有格子涂成同一颜色的棋盘。

...#
..#.
##.#

可以通过以下方法将该棋盘上的所有格子涂成白色。

  1. 反转盘面右下端的 2 行 2 列的矩形区域。
  2. 从上数第 3 行的所有格子反转。
  3. 从左数第 4 列的所有格子反转。

入力例 2

4 4 5
####
####
....
####
2 2
3 2
2 3
3 3

出力例 2

Yes
Yes
Yes
No
Yes