B. Таргетинг на погоду
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Итак, владельцам рекламных объявлений определённых тематик требуется возможность управлять настройками показов в зависимости от погоды. В этой задаче вам потребуется реализовать простейшую версию этой функциональности — таргетинг на температуру в определённые диапазоны дней.

В вашем распоряжении есть исторические данные о температуре, а также прогноз на ближайшее будущее. А именно:

  • температура сегодня (этот день имеет номер $$$0$$$);
  • температура за прошедшие $$$N$$$ дней (вчерашний имеет номер $$$-1$$$, позавчерашний — $$$-2$$$ и так далее до дня $$$-N$$$, самого раннего из известных);
  • прогноз температуры на ближайшие $$$N$$$ дней (завтрашний имеет номер $$$1$$$, послезавтрашний — $$$2$$$ и так далее до дня $$$N$$$).

Кроме того, есть данные о настройках показа $$$B$$$ рекламных объявлений. Каждому из них соответствуют четыре числа $$$t_{min}$$$, $$$t_{max}$$$, $$$d_{min}$$$, $$$d_{max}$$$, означающие, что объявление можно показывать только в том случае, если за период от дня $$$d_{min}$$$ до дня $$$d_{max}$$$ включительно температура принимала или примет значение от $$$t_{min}$$$ до $$$t_{max}$$$ включительно. При этом гарантируется, что $$$d_{min} \le 0 \le d_{max}$$$, то есть диапазон дней должен включать сегодняшний.

Обратите внимание, что температура не дискретна! Например, если вчера значение температуры было $$$-5$$$, а сегодня $$$-2$$$, то необходимо считать, что в период, включающий сегодняшний и вчерашний дни, температура принимала не только значения $$$-5$$$ и $$$-2$$$, но и $$$-4$$$ и $$$-3$$$ (и даже $$$-3{,}14$$$, но в этой задаче все входные данные целочисленны).

Для каждого рекламного объявления определите, может ли оно быть показано в текущий день с учётом настроек и известных погодных данных.

Входные данные

В первой строке входного файла вводится единственное целое неотрицательное число $$$N$$$ ($$$N \le 100\,000$$$).

В следующей строке вводится $$$2N+1$$$ целых чисел — значения температуры в дни $$$-N$$$, $$$-N+1$$$, ..., $$$-1$$$, $$$0$$$, $$$1$$$, ..., $$$N$$$. Значения температуры по модулю не превосходят $$$10^9$$$.

В третьей строке содержится единственное целое положительное число $$$B$$$ ($$$B \le 100\,000$$$) — количество рекламных объявлений.

Наконец, в каждой из следующих $$$B$$$ строк содержатся 4 целых числа $$$t_{min}$$$, $$$t_{max}$$$, $$$d_{min}$$$, $$$d_{max}$$$, описывающие настройки соответствующего объявления. Гарантируется, что $$$-10^9 \le t_{min} \le t_{max} \le 10^9$$$ и $$$-N \le d_{min} \le 0 \le d_{max} \le N$$$.

Выходные данные

Для каждого из объявлений выведите в отдельной строке «yes», если оно может быть показано согласно настройкам, и «no» в противном случае.

Пример
Входные данные
2
2 4 5 -2 2
4
-1 -1 -1 1
0 10 -1 0
6 8 -2 2
3 3 -1 0
Выходные данные
yes
yes
no
no