外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

V - Sandbox

作成者 nekooooooo、siooisi、jammy、trueryob

テスター siooisi、trueryob

配点 550 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

問題文

わりとねこくんが管理している N×NN \times N のマス目で表される砂場があります。最初、砂場には足跡が 11 つもありません。

これから、QQ 回のイベントが時系列順に発生します。kk 番目のイベントは以下のいずれかです。

これから、QQ 回のイベントが時系列順に発生します。 kk 番目のイベントの種類は tkt_k で表されます。

  • tk=1t_k = 1 のとき、ねこが砂場を通過しようとします。

    • dk=1d_k = 1 なら、 pkp_k 列目を上端から下端へ通ろうとします。
    • dk=2d_k = 2 なら、 pkp_k 行目を左端から右端へ通ろうとします。

    通ろうとする行または列の NN マスのうち、足跡のあるマスが 11 つでもあれば、ねこは通過に失敗します。すべてのマスに足跡がなければ、ねこは通過に成功し、その NN マスすべてに足跡がつきます。

  • tk=2t_k = 2 のとき、清掃員が砂場を清掃します。

    • dk=1d_k = 1 なら、第 pkp_k 列にある足跡をすべて消します。
    • dk=2d_k = 2 なら、第 pkp_k 行にある足跡をすべて消します。

    清掃員は足跡を残しません。

登場するすべてのねこが無事に砂場を通過できるか判定してください。

制約

  • 2≤N≤1052 \le N \le 10^5
  • 1≤Q≤2×1051 \le Q \le 2 \times 10^5
  • tk∈{1,2}t_k \in \{1, 2\}
  • dk∈{1,2}d_k \in \{1, 2\}
  • 1≤pk≤N1 \le p_k \le N
  • タイプ 1 のイベントは少なくとも 11 つ以上存在する
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

NQN \quad Q t1d1p1t_1 \quad d_1 \quad p_1 t2d2p2t_2 \quad d_2 \quad p_2 ⋮\vdots tQdQpQt_Q \quad d_Q \quad p_Q

出力

すべてのねこが足跡を踏まずに無事通過できる場合は Yes を、途中で 11 匹でも失敗する場合は No を 11 行に出力してください。

入力例 1

3 3
1 1 2
2 2 1
1 2 1

出力例 1

Yes

最初のねこが 22 列目を通過します。その後、 11 行目が清掃され、マス (1,2)(1, 2) の足跡が消えます。最後のねこが通る 11 行目には足跡が残っていないため、無事に通過できます。

入力例 2

3 2
1 1 2
1 2 1

出力例 2

No

最初のねこが 22 列目を通過します。次のねこが通ろうとする 11 行目には、マス (1,2)(1, 2) に足跡が残っているため、通過できません。

入力例 3

2 4
1 1 1
2 2 1
2 2 2
1 1 1

出力例 3

Yes

参加受付は終了しました。