Несмотря на юную внешность, Фрирен прожила больше тысячи лет. Восприятие времени эльфийки отличается от человеческого, и год-другой для нее ничего не стоит. Тем не менее, она хорошо помнит, что в $$$i$$$-й год жизни с ней произошли $$$a_i$$$ хороших событий и $$$b_i$$$ плохих.
Однажды Ферн, ученица Фрирен, стала расспрашивать наставницу о ее прошлом. Она задала $$$q$$$ вопросов, в $$$i$$$-м из которых упомянула два года из жизни Фрирен: $$$x_i$$$-й и $$$y_i$$$-й. Фрирен, хоть и хорошо помнит свою жизнь, не хочет отвечать на скучные вопросы, поэтому некоторые из них останутся без ответа.
Скажем, что два года $$$x$$$ и $$$y$$$ являются
Иными словами, если есть последовательность лет $$$x_1, \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 \leq 5 \cdot 10^5$$$).
В $$$i$$$-й из следующих $$$q$$$ строк дана пара целых чисел $$$x_i$$$ и $$$y_i$$$ — упомянутые Ферн в $$$i$$$-м вопросе года из жизни Фрирен ($$$1 \le x_i, y_i \le n$$$).
Выведите $$$q$$$ строк, в $$$i$$$-й из которых выведите ответ на соответствующий запрос. Выведите «YES» (без кавычек), если $$$i$$$-й вопрос Ферн будет интересным, а иначе выведите «NO».
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
1 | 13 | $$$n, q \le 100$$$ | полная | |
2 | 14 | $$$b_i = 0$$$ для всех $$$i$$$ | первая ошибка | |
3 | 14 | $$$a_i$$$ — простое для всех $$$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 | первая ошибка |
47 5 2 102 7 2 1161 21 31 42 32 43 4
YES YES YES YES YES YES
62 3 4 5 6 79 9 9 9 9 951 21 41 54 64 5
YES NO YES NO NO