Дано поле, состоящее из \(n\) строк и \(m\) столбцов. Строки пронумерованы от \(1\) до \(n\) снизу вверх. Столбцы пронумерованы от \(1\) до \(m\) слева направо. В \(i\)-м столбце нижние \(a_i\) ячеек заблокированы (ячейки в строках \(1, 2, \dots, a_i\)), оставшиеся \(n - a_i\) ячеек разблокированы.
Робот ходит по этому полю. Ему можно посылать команды — двигаться вверх, вправо, вниз или влево. Если робот пытается перейти в заблокированную ячейку или за границы поля, то он взрывается.
Однако, робот сломан — он выполняет каждую команду \(k\) раз. То есть, если вы говорите ему двигаться вверх, например, то он перейдет вверх \(k\) раз (на \(k\) ячеек). Нельзя посылать команды, пока робот выполняет текущую.
Приходят \(q\) запросов о роботе. Каждый запрос определяется начальной клеткой, конечной клеткой и значением \(k\). Можно ли послать роботу произвольное количество команд (возможно, ноль) так, что он достигнет конечную клетку из начальной с учетом того, что каждая команда выполняется \(k\) раз?
Робот должен остановиться в конечной ячейке. Если он проходит через конечную клетку во время выполнения команд, то это не считается.
Выходные данные
На каждый запрос выведите «YES», если можно послать роботу произвольное количество команд (возможно, ноль) так, что он достигнет конечную клетку из начальной с учетом того, что каждая команда выполняется \(k\) раз. Иначе выведите «NO».