問題文

H 行 W 列のマス目があり、上から i (1 \leq i \leq H) 行目、左から j (1 \leq j \leq W) 列目のマスを (i, j) と表します。

最初すべてのマスは白いです。ここで、Q 個のクエリが以下の形式で与えられます。

i (1 \leq i \leq Q) 番目のクエリについて：

• t_i = 1 のとき

  • 整数 r_i, c_i が与えられる。
  • 白いマス (r_i, c_i) が赤色で塗られる。

• t_i = 2 のとき

  • 整数 {ra}_i, {ca}_i, {rb}_i, {cb}_i が与えられる。
  • 次の 2 つの条件両方を満たすとき Yes、そうでなければ No と出力する。
    • マス ({ra}_i, {ca}_i) とマス ({rb}_i, {cb}_i) が赤色で塗られている。
    • マス ({ra}_i, {ca}_i) からマス ({rb}_i, {cb}_i) まで赤色マス上を上下左右に移動することで辿り着ける。

以上の Q 個のクエリを順に処理してください。

制約

• 1 \leq H, W \leq 2000
• 1 \leq Q \leq 100000
• 1 \leq t_i \leq 2
• t_i = 1 のとき、1 \leq r_i \leq H、1 \leq c_i \leq W
• t_i = 2 のとき、1 \leq {ra}_i, {rb}_i \leq H、1 \leq {ca}_i, {cb}_i \leq W
• t_i = 1 かつ t_j = 1 (1 \leq i < j \leq Q) のとき、(r_i, c_i) \neq (r_j, c_j)
• 与えられる入力は全て整数

入力例 1

3 3
10
1 2 2
1 1 1
2 1 1 2 2
1 3 2
2 1 1 2 2
2 2 2 3 2
1 2 3
1 2 1
2 1 1 2 2
2 1 1 3 3

出力例 1

No
No
Yes
Yes
No

与えられた 10 個のクエリを順に処理すると以下のようになります。

• マス (2, 2) が赤色で塗られる。
• マス (1, 1) が赤色で塗られる。
• マス (1, 1) からマス (2, 2) までは赤色マス上を上下左右に移動することで到達できないので No を出力する。
• マス (3, 2) が赤色で塗られる。
• マス (1, 1) からマス (2, 2) までは赤色マス上を上下左右に移動することで到達できないので No を出力する。
• マス (2, 2) からマス (3, 2) までは赤色に塗られていて、上下方向で隣接しているマスなので Yes を出力する。
• マス (2, 3) が赤色で塗られる。
• マス (2, 1) が赤色で塗られる。
• マス (1, 1) からマス (2, 2) まではマス (1, 1) → マス (2, 1) → マス (2, 2) と赤色マス上を上下左右に移動して到達できるので Yes を出力する。
• マス (1, 1) からマス (3, 3) までは赤色マス上を上下左右に移動することでたどり着けないので No を出力する。

入力例 2

1 1
3
2 1 1 1 1
1 1 1
2 1 1 1 1

出力例 2

No
Yes

1 マスも赤色で塗られていない場合に注意してください。

入力例 3

5 5
42
2 3 4 3 4
2 3 2 3 2
1 4 1
2 4 1 2 2
1 1 2
1 4 5
1 3 3
2 4 2 1 3
1 3 5
2 2 4 2 3
2 2 4 2 5
2 3 4 5 1
2 3 1 2 2
2 3 1 1 2
2 2 4 5 2
2 3 2 5 3
1 4 3
2 3 3 3 5
2 3 1 3 2
1 1 5
2 4 4 5 3
1 1 4
2 1 3 2 5
2 4 3 1 4
2 2 3 3 3
1 2 1
1 2 5
2 1 4 5 3
2 4 4 2 5
2 4 2 2 4
1 2 2
2 4 1 5 2
1 2 4
2 3 1 4 1
1 4 4
2 3 2 2 1
2 1 1 5 2
1 4 2
2 4 2 3 5
1 3 2
1 3 4
1 2 3

出力例 3

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes