H - Hack Hash 解説 /

実行時間制限: 5 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

この問題は output only です。また、非常に特殊なジャッジ形式に注意してください。

以下の問題を問題 A とします。 これは、 ABC367 の F 問題 と同じです。

長さ N の正整数列 A=(A_1,A_2,\dots,A_N), B=(B_1,B_2,\dots,B_N) が与えられます。
Q 個のクエリが与えられるので順に処理してください。 i 番目のクエリは以下で説明されます。

  • 正整数 l_i,r_i,L_i,R_i が与えられる。数列 (A_{l_i},A_{l_i+1},\dots,A_{r_i}) を並び替えることで (B_{L_i},B_{L_i+1},\dots,B_{R_i}) に一致させることができるならば Yes を、できないならば No を出力せよ。

問題 A に対する以下の解法を、制約を満たすようなテストケースをひとつ挙げることにより撃墜してください。

  • i = 1,2,\dots,N について、 f[i] を 1 以上 998244352 以下の一様ランダムな整数で定める。
  • A の全ての要素について、 A_i = f[A_i] と置換する。
  • B の全ての要素について、 B_i = f[B_i] と置換する。
  • その後、全てのクエリについて Yes か No かを以下の通りに判定する。
    • \prod_{k=l_i}^{r_i} A_k \equiv \prod_{k=L_i}^{R_i} B_k が \rm{mod} 998244353 上で成立する時、またその時に限り、 Yes と判定する。

制約

  • 1 \le N,Q
  • N+Q \le 10^6
  • 1 \le A_i,B_i \le N
  • 1 \le l_i \le r_i \le N
  • 1 \le L_i \le R_i \le N
  • 入力は全て整数

入力

この問題では、入力は与えられない。

出力

テストケースを以下の形式で出力せよ。

N Q
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
l_1 r_1 L_1 R_1
l_2 r_2 L_2 R_2
\vdots
l_Q r_Q L_Q R_Q

ジャッジ

提出されたテストケースの形式が誤っていた場合やテストケースが制約に違反している場合、ジャッジの判定は不定である。
そうでない場合、審判プログラムはそのテストケースに対して問題文中の解法を 50 回実行する。このうち 40 回以上で不正解が得られた時、またその時に限り、 AC の判定を得ることができる。なお、この制約の下でAC の確率を1-10^{-10}程度まで上げることが可能である。 撃墜確率が不十分な入力に対しては提出結果が運に左右される場合がある。

サンプル

例えば、以下のテストケースは問題文中の制約を満たす。

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

しかし、このテストケースでは非常に高い確率で撃墜回数が 40 回に届かないため、非常に高い確率で不正解と判定される。