芙莉莲与有趣的问题

时间限制： 2秒
内存限制： 512 MB
输入： 标准输入
输出： 标准输出

题目描述

尽管芙莉莲外表年轻，但她已经活了一千多年。精灵对时间的感知与人类不同，一两年对她来说不算什么。然而，她清楚地记得，在她生命中的第 $i$ 年，发生了 $a_i$ 件好事和 $b_i$ 件坏事。

有一天，芙莉莲的学生费伦开始询问她关于过去的事情。她问了 $q$ 个问题，在第 $i$ 个问题中，她提到了芙莉莲生命中的两年：第 $x_i$ 年和第 $y_i$ 年。芙莉莲虽然很清楚自己的一生，但不想回答无聊的问题，所以有些问题会得不到回答。

定义两个年份 $x$ 和 $y$ 是：

$a$-有趣的，如果 $a_x$ 能被 $a_y$ 整除，或者反过来 $a_y$ 能被 $a_x$ 整除；
$ab$-有趣的，如果 $a_x = b_y$ 或 $a_y = b_x$；
相互有趣的，如果它们要么是 $a$-有趣的，要么是 $ab$-有趣的，或者存在一个年份 $z$，使得 $x$ 和 $z$ 相互有趣，并且 $y$ 和 $z$ 相互有趣。

换句话说，如果存在一个年份序列 $x_1, x_2, \ldots, x_k$，使得任意相邻的 $x_i$ 和 $x_{i+1}$ 要么是 $a$-有趣的，要么是 $ab$-有趣的，那么芙莉莲认为 $x_1$ 和 $x_k$ 是相互有趣的。

请告诉费伦，她的哪些问题是有趣的（即问题中提到的年份 $x_i$ 和 $y_i$ 对于芙莉莲来说是相互有趣的），哪些不是。

第一行一个整数 $n$ —— 芙莉莲活过的年数 ($2 \le n \le 3 \cdot 10^5$)。

第二行有 $n$ 个整数 $a_i$ —— 每一年芙莉莲遇到的好事数量 ($1 \le a_i \le 3 \cdot 10^5$)。

第三行有 $n$ 个整数 $b_i$ —— 每一年芙莉莲遇到的坏事数量 ($0 \le b_i \le 3 \cdot 10^5$)。

第四行一个整数 $q$ —— 费伦想问的问题数量 ($1 \le q \le 5 \cdot 10^5$)。

接下来 $q$ 行，每行两个整数 $x_i$ 和 $y_i$ —— 第 $i$ 个问题中提及的年份 ($1 \le x_i, y_i \le n$)。

输出 $q$ 行，每行输出对应问题的答案。如果第 $i$ 个问题是有趣的，输出 YES（不带引号），否则输出 NO。

每个子任务的得分只有在通过该子任务及所有必要子任务的所有测试时才被计入。

子任务	分数	限制	必要子任务	测试信息
1	13	$n, q \le 100$	无	完全
2	14	对所有 $i$，$b_i = 0$	无	首次错误
3	14	对所有 $i$，$a_i$ 为质数	无	首次错误
4	14	$n, q \le 1000$	1	首次错误
5	18	$n \le 5000$, $q \le 5 \cdot 10^5$	1,4	首次错误
6	27	无额外限制	1–5	首次错误

输入：

输出：

YES
YES
YES
YES
YES
YES

输入：

6
2 3 4 5 6 7
9 9 9 9 9 9
5
1 2
1 4
1 5
4 6
4 5

输出：

YES
NO
YES
NO
NO