新年的邀请函 - 题目 - Universal Online Judge

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

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

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

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

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

此外，每个邀请函上还有一个整数 $t_{i}$ ：如果存在数字 $x$ 满足 $x^{2} \equiv a_{i} (\mod 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} (\mod p)$ ,则 $t_{i} = 1$ ，否则 $t_{i} = - 1$ 。

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

见“样例数据下载”

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

见“样例数据下载”

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

时间限制： $1s$

空间限制： $1024MB$

Universal Online Judge