2024 上海市大学生编程新锐挑战赛

C. sha7dow loves rand function
PDF 题面可用
你可以在这里下载。

单点时限: 1.0 sec

内存限制: 128 MB

$\texttt{sha7dow}$ 很喜欢各种随机函数,总有人想让他帮忙生成各种周期的神神秘秘的随机数,要避开每个人不喜欢的数字还不能直接用 mt19937(steady_clock::now().time_since_epoch().count()) 很烦的 $\texttt{sha7dow}$ 想找到一个完美的随机数生成器满足大家的所有要求。所以他希望你能用线性同余法生成一个随机的无穷数列 $x_i$,使得给定的 $n$ 个数 $t_i$ 都是这个数列的周期,$m$ 个数 $s_i$ 都不是这个数列的周期。具体地,$x_0=0$,$x_i = (ax_{i-1} + b) \bmod c$,你需要帮助 $\texttt{sha7dow}$ 给出一组可行的 $a,b,c$ 的取值,或遗憾地告诉 $\texttt{sha7dow}$ 这是不可行的。

输入格式

第一行包含两个整数 $n,m$。
第二行包含 $n$ 个整数 $t_i$,$t_i$ 都是生成的随机数列的周期。
第三行包含 $m$ 个整数 $s_i$,$s_i$ 都不是生成的随机数列的周期。

输出格式

输出一行三个整数 $a,b,c$,若不可行,则输出 0 0 0

样例

Input
2 1
20 40
66
Output
22 33 10

提示

$1 \leqslant n,m \leqslant 10^5$
$1 \leqslant t_i,s_i \leqslant 10^9$
$0 \leqslant a,b,c \leqslant 10^9$
$r = a \bmod b$ 当且仅当 $a=qb+r, r \in [0,b)$