过年了，可是由于肺炎疫情突发，鼠们纷纷委婉地拒绝参加新年宴会。结果偌大的宴会只有皮卡丘和跳蚤明确表明自己要赴约。

如果在这个节骨眼宴会现场被猫们围攻，那么只有皮卡丘能逃出去，跳蚤就凉了（虽然抓它好像没什么用，又不能吃）。

所以为了对外隐瞒宴会实际参加的人数，不引起恐慌，跳蚤提高了宴会现场的防卫等级：必须出示邀请函或者正确回答通关密码才能进入会场。

通关密码为一个在 $1$ 到 $m$ 之间均匀随机的质数 $p$。也即，先找出 $1 \le q \le m$ 的所有质数 $q$，然后再在这些质数中均匀随机出一个质数 $p$。

每名与会者的邀请函上有一个在 $1$ 到 $n$ 之间均匀随机出来的整数，第 $i$ 位与会者的邀请函上写的是 $a_i$。

此外，每个邀请函上还有一个整数 $t_i$：如果存在数字 $x$ 满足 $x^2 \equiv a_i \pmod p$，则 $t_i = 1$，否则 $t_i = -1$。

猫猫自然是不可能拿到邀请函了，但皮卡丘有情报表明猫猫已经窃取了跳蚤的邮箱，获取了 $100000$ 个邀请函上的 $a_i, t_i$。

因此，皮卡丘想知道假如情报属实，猫猫能不能猜出通关密码是多少？如果能猜出来，那他得赶紧警告跳蚤了。

为此，皮卡丘准备写个程序试试……

输入格式

第一行两个正整数 $n$，$m$，含义如前所述。

之后 $100000$ 行，第 $i$ 行一个正整数 $a_i$和一个整数 $t_i$。如果存在数字 $x$ 满足 $x^2 \equiv a_i \pmod p$,则 $t_i = 1$，否则 $t_i = -1$。

输出格式

一行一个整数，表示素数 $p$

样例一

见“样例数据下载”

样例一中，$n$ = $10000$，$m$ = $1000000$。容易发现，$1$ 到 $m$ 中只有一个素数符合条件。

样例二

见“样例数据下载”

限制与约定

保证对于每个点，恰有一个素数 $p$ 满足要求。

时间限制：$\texttt{1s}$

空间限制：$\texttt{1024MB}$

下载

样例数据下载