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

Дано поле, состоящее из $$$n$$$ строк и $$$m$$$ столбцов. Строки пронумерованы от $$$1$$$ до $$$n$$$ снизу вверх. Столбцы пронумерованы от $$$1$$$ до $$$m$$$ слева направо. В $$$i$$$-м столбце нижние $$$a_i$$$ ячеек заблокированы (ячейки в строках $$$1, 2, \dots, a_i$$$), оставшиеся $$$n - a_i$$$ ячеек разблокированы.

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

Однако, робот сломан — он выполняет каждую команду $$$k$$$ раз. То есть, если вы говорите ему двигаться вверх, например, то он перейдет вверх $$$k$$$ раз (на $$$k$$$ ячеек). Нельзя посылать команды, пока робот выполняет текущую.

Приходят $$$q$$$ запросов о роботе. Каждый запрос определяется начальной клеткой, конечной клеткой и значением $$$k$$$. Можно ли послать роботу произвольное количество команд (возможно, ноль) так, что он достигнет конечную клетку из начальной с учетом того, что каждая команда выполняется $$$k$$$ раз?

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

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

В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le m \le 2 \cdot 10^5$$$) — количество строк и столбцов на поле.

Во второй строке записаны $$$m$$$ целых чисел $$$a_1, a_2, \dots, a_m$$$ ($$$0 \le a_i \le n$$$) — количество заблокированных ячеек внизу $$$i$$$-го столбца.

В третьей строке записано одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.

В каждой из следующих $$$q$$$ строк записаны пять чисел $$$x_s, y_s, x_f, y_f$$$ и $$$k$$$ ($$$a[y_s] < x_s \le n$$$; $$$1 \le y_s \le m$$$; $$$a[y_f] < x_f \le n$$$; $$$1 \le y_f \le m$$$; $$$1 \le k \le 10^9$$$) — строка и столбец начальной ячейки, строка и столбец конечной ячейки и количество раз, которое выполняется каждая команда. Начальная и конечная клетки разблокированы.

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

На каждый запрос выведите «YES», если можно послать роботу произвольное количество команд (возможно, ноль) так, что он достигнет конечную клетку из начальной с учетом того, что каждая команда выполняется $$$k$$$ раз. Иначе выведите «NO».

Пример
Входные данные
11 10
9 0 0 10 3 4 8 11 10 8
6
1 2 1 3 1
1 2 1 3 2
4 3 4 5 2
5 3 11 5 3
5 3 11 5 2
11 9 9 10 1
Выходные данные
YES
NO
NO
NO
YES
YES