F - 配信パズル
解説
/
実行時間制限: 4 sec / メモリ制限: 256 MB
配点 : 800 点
問題文
すぬけ君は、Q 日間にわたって、毎日次のようなパズルを解こうとしています。
- すぬけ君の持っている端末に、縦 H 行、横 W 列からなる格子状の盤面が毎日配信されてくる。それぞれのマスは白または黒で塗られている。ただし、i+1 日目 (1 ≤ i ≤ Q-1) に配信されてくる盤面は、i 日目に配信される盤面の上から r_i 行目で左から c_i 列目のマスの白黒が反転したものである。
- 配信されてきた盤面に対し、すぬけ君ははじめに最大 1 回、盤面の中の長方形領域を指定し、領域中の全てのマスの白黒を反転させる。
- その後、すぬけ君は 1 つの行または列を選び、その中の全てのマスの白黒を反転させるという操作を好きな回数だけ行える。
- 盤面の全てのマスを同じ色にすることが目的である。
すぬけ君は賢いので、配信されてくる盤面の中には絶対に解けないものが存在することに勘付いています。そこで、すぬけ君の代わりに、それぞれの日の盤面について、盤面の全てのマスを同じ色にする方法が存在するかどうかを判定してください。
ただし、1 日目に配信される盤面は、上から 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 日目の盤面の全てのマスを同じ色にする方法が存在する場合 Yes
を、そうでない場合 No
を出力せよ。
入力例 1
3 4 4 ...# .### .#.# 3 1 2 4 2 2
出力例 1
No No No Yes
4 日目の盤面が、全てのマスを同じ色にする方法が存在する盤面です。
...# ..#. ##.#
この盤面からは、以下のようにして全てのマスを白にできます。
- 盤面の右下端の 2 行 2 列の長方形領域を反転させる。
- 上から 3 行目の全てのマスを反転させる。
- 左から 4 列目の全てのマスを反転させる。
入力例 2
4 4 5 #### #### .... #### 2 2 3 2 2 3 3 3
出力例 2
Yes Yes Yes No Yes