题目描述

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$。

比赛结束之后，只有你们通过了这道题。其他队的参赛成员找到你们，希望要一份你们的代码学习参考，但很不幸，你们的代码并没有保存下来。你能再复现一份吗？

输入格式

第一行一个正整数 $n$，表示 $\{a_i\}$ 和 $\{p_i\}$ 的长度。

第二行 $n$ 个整数，表示 $\{a_i\}$。

第三行 $n$ 个整数，表示 $\{p_i\}$。

第四行一个正整数 $q$，表示三元组 $\{u_i, v_i, w_i\}$ 的个数。

接下来 $q$ 行，每行三个整数，表示 $u_i, v_i, w_i$，含义与上述一致。

对于所有数据，满足：

• $2 \leq n \leq 5 \times 10^5$；
• $1 \leq q \leq 5 \times 10^5$；
• $1 \leq a_i \leq 10^7$；
• $a_i$ 互不相同；
• $u_i, v_i \in \{a_i\}$；
• $0 \leq p_i, w_i \leq 5 \times 10^6$。

输出格式

共 $q$ 行。

对于第 $i$ 行，若存在一条从 $u_i$ 到 $v_i$ 的路径，其点权异或和为 $w_i$，则输出 Yes，否则输出 No。

5
1 2 3 6 5
1 2 3 6 1145
4
2 3 6
3 6 10
2 3 0
1 2 0

Yes
No
Yes
No

8
1 2 3 4 5 6 7 8
3 19 5 8 2 17 6 17
6
3 5 629185
4 8 25
5 5 4274800
6 6 947319
1 2 16
8 8 2205033

No
Yes
No
No
No
No

提示

样例 #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。