配点 : 100 点
問題文
**工作时注意:将显示成功击落次数而不是分数。我们将在比赛开始前向原评委更正**这个问题是 输出 。另请注意非常具体的评审形式。
设以下问题为问题 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被确定。
- \prod_{k=l_i}^{r_i} A_k \equiv \prod_{k=L_i}^{R_i} B_k 是
在 \rm{mod} 998244353 当且仅当上述成立时,
制約
- 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 次,所以答案很可能是错误的。