配点: 5 点
問題文
长度 小于或等于 N 整数序列 给出 A = (A_1, A_2, \ldots, A_N) 。 最初,您对这个整数序列一无所知。 有关
整数列 A (统称为该事件)的信息和问题 给出了 Q 。从一开始 i 番目 (1 \leq i \leq Q) 事件是 4 整数集 查找 (T_i, X_i, Y_i, V_i) ,是这样的: 当
- T_i = 0 时,这是 这意味着给出了信息 A_{X_i} + A_{Y_i} = V_i 。在这里,请务必 假设 X_i+1=Y_i 。
- T_i = 1 时,这是
这意味着给出了信息 A_{X_i} = V_i 当假设 A_{Y_i} 的值是多少?意味着问题。
- 更准确地说, 使所有 A_{X_i}=V_i 和 按字典顺序比较 A_{X_j} + A_{Y_j} = V_j \ (1 \leq j \lt i, T_j = 0) 都成立的长度。 在 N 整数序列 给出 A 中, 输出 A_{Y_i} 的值是多少?代表问题。
逐步浏览事件并回答每个事件的问题。
不过,提问时的答案
当 A_{Y_i} 无法以一种方式确定时,改为 Ambiguous 。
制約
- 1\leq N\leq10^5
- 1\leq Q\leq10^5
- T_i=0 或 至少 T_i=1\ (1\leq i\leq Q)
- 1\leq X_i,Y_i\leq N\ (1\leq i\leq Q)
- T_i=0 如果 X_i+1=Y_i\ (1\leq i\leq Q)
- 0\leq V_i\leq 2\times10^9\ (1\leq i\leq Q)
- 没有给出矛盾的输入。
- 换句话说,i=1,2,\ldots,Q , T_i=0 如果 T_j=0\ (1\leq j\leq i) 小于 j 以同样的方式定义 A_{X_j}+A_{Y_j}=V_j 都成立, 使所有 T_i=1 如果 A_{X_i}=V_i 和 按字典顺序比较 T_j=0\ (1\leq j \lt i) 小于 j 以同样的方式定义 A_{X_j}+A_{Y_j}=V_j 都成立的长度。 N 整数序列 给出 A 存在。
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N Q T_1 X_1 Y_1 V_1 T_2 X_2 Y_2 V_2 \vdots T_Q X_Q Y_Q V_Q
出力
请按顺序输出每个问题的答案。
但是,如果在提问时答案不确定,则 Ambiguous 。
入力例 1
4 7 0 1 2 3 1 1 2 1 1 3 4 5 0 3 4 6 1 3 4 5 0 2 3 6 1 3 1 5
出力例 1
2 Ambiguous 1 2
对于每个问题,答案是:
- 1 第二个问题(i=2), 满足A_1=1 和 A_1+A_2=3 的序列 A 就是全部 它是 A_2=2 满足,所以应该输出的是 2 。
- 2 第二个问题(i=3),
满足A_3=5 和 A_1+A_2=3 的序列 A 有
直到 (A_1,A_2,A_3,A_4)=(1,2,5,10) 呀
请注意,它可能是 (A_1,A_2,A_3,A_4)=(3,0,5,0) 等
由于 A_4 没有单一值,因此应该输出的是
有一块木板,分为
Ambiguous。 - 3 第二个问题(i=5), 满足A_3=5 和 A_1+A_2=3,A_3+A_4=6 的序列 A 就是全部 它是 A_4=1 满足,所以应该输出的是 1 。
- 4 第二个问题(i=7), 满足A_3=5 和 A_1+A_2=3,A_3+A_4=6,A_2+A_3=6 的序列 A 就是全部 它是 A_1=2 满足,所以应该输出的是 2 。
入力例 2
15 25 0 11 12 41 0 1 2 159 0 14 15 121 0 4 5 245 0 12 13 157 0 9 10 176 0 6 7 170 0 2 3 123 0 7 8 167 0 3 4 159 1 12 11 33 0 10 11 116 0 8 9 161 1 9 12 68 1 12 12 33 1 7 12 74 0 5 6 290 1 8 9 93 0 13 14 127 1 10 12 108 1 14 1 3 1 13 8 124 1 12 11 33 1 12 10 33 1 5 15 194
出力例 2
8 33 33 33 68 33 144 93 8 108 118