P11867 大家的公因数 2

4202 年，第 2184 届威海市大学生程序设计竞赛如期举行。小威与你组队参加了这次竞赛，你们在五小时的比赛中大杀四方，仅使用两小时的时间就解决了 12 题。现在，你们翻开了最后一道题的题面，但你们发现，纸上只印了两个正整数序列 $\{a_i\}$ 和 $\{p_i\}$ 和一个三元组序列 $\{u_i, v_i, w_i\}$。 你以为是印刷错误，于是你看向了小威的纸质题面，却发现小威也在看你的。你们面面相觑，不知道如何是好。最终，你们决定，猜一个题意！或许你们就是天命人吧，按照你们猜的题意写完代码提交后，一发通过了该题，AK 了这场比赛。 你们猜的题意是这样的：对于正整数序列中的两个数 $a_i$ 和 $a_j$，当且仅当它们有一个**大于 1** 的公因数时，它们之间有一条无向边连接。如此，你得到了一张无向图，每个点上有点权 $p_i$。你现在想知道，对于每个三元组，是否存在一条从 $u_i$ 到 $v_i$ 的路径，其点权异或和为 $w_i$。 比赛结束之后，只有你们通过了这道题。其他队的参赛成员找到你们，希望要一份你们的代码学习参考，但很不幸，你们的代码并没有保存下来。你能再复现一份吗？

无

无

样例 #1 对应的无向图如下所示：  对于第一个查询，一条可行的路径为：$2 \to 2 \to 6 \to 3 \to 3$； 对于第二个查询，无法找到一条路径使得异或和为 $10$； 对于第三个查询，一条可行的路径为：$2 \to 2 \to 6 \to 6 \to 3 \to 3$； 对于第四个查询，$1$ 和 $2$ 之间不存在路径，故查询结果为 `No`。