Фрирен и интересные вопросы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Несмотря на юную внешность, Фрирен прожила больше тысячи лет. Восприятие времени эльфийки отличается от человеческого, и год-другой для нее ничего не стоит. Тем не менее, она хорошо помнит, что в $$$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».

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
113$$$n, q \le 100$$$полная
214$$$b_i = 0$$$ для всех $$$i$$$первая ошибка
314$$$a_i$$$ — простое для всех $$$i$$$первая ошибка
414$$$n, q \le 1000$$$1первая ошибка
518$$$n \le 5000$$$, $$$q \le 5 \cdot 10^5$$$1, 4первая ошибка
627без дополнительных ограничений1 – 5первая ошибка

Примеры

Входные данные
4
7 5 2 10
2 7 2 11
6
1 2
1 3
1 4
2 3
2 4
3 4
Выходные данные
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