Лето уже в самом разгаре — а это значит, что нас всех ждут и дождливые, и жаркие дни. В дождь людям нужны зонты и дождевики, и производителям этих товаров крайне важно отслеживать рост интереса к ним. С другой стороны, производителям прохладительных напитков важны жаркие дни, когда на продвижение можно потратить бóльшие бюджеты.
Итак, владельцам рекламных объявлений определённых тематик требуется возможность управлять настройками показов в зависимости от погоды. В этой задаче вам потребуется реализовать простейшую версию этой функциональности — таргетинг на температуру в определённые диапазоны дней.
В вашем распоряжении есть исторические данные о температуре, а также прогноз на ближайшее будущее. А именно:
Кроме того, есть данные о настройках показа $$$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