В этой задаче Вам следует пройти из одного угла шахматного поля в противоположный согласно определенным правилам, избегая совершения слишком большого количества шагов. \includegraphics{https://static.e-olymp.com/content/22/223dd6b7d297e56baacae6a714c0a0362b3b726b.jpg} Шахматная доска на плоскости состоит из \textbf{m} строк и\textbf{ n} колонок. Каждая ячейка доски содержит один из трех предметов: гору, бумагу или ножницы. Движение начинается в клетке (\textbf{1}, \textbf{1}) и совершается по направлению к (\textbf{m}, \textbf{n}) выполнением последовательности ходов. Ходом называется перемещение в любую клетку, расположенную не дальше чем \textbf{d} от текущей. Расстояние измеряется между центрами ячеек: расстояние между ячейками (\textbf{x_1}, \textbf{y_1}) и (\textbf{x_2}, \textbf{y_2}) равно . Каждый ход следует совершать в ячейку, содержащую предмет, который наносит поражение предмету в предыдущей ячейке. Как и в игре "Камень-Бумага-Ножницы”, камень побеждает ножницы, ножницы побеждают бумагу, а бумага побеждает камень. Когда мы заходим в ячейку, то убираем из нее предмет, таким образом запрещено дважды посещать одну и ту же ячейку. Поле довольно большое, поэтому предметы в ячейках определяются генератором случайных чисел, или более точно, линейным конгруэнтным генератором. Этот генератор имеет состояние, представляющее собой целое число \textbf{s} от \textbf{0} до \textbf{2^32} - \textbf{1}. Для получения следующего случайного числа от \textbf{0} до \textbf{r} - \textbf{1} выполняется присваивание \textbf{s} := (\textbf{s} ∙ \textbf{1 664 525} + \textbf{1 013 904 223}) mod \textbf{2^32} и возвращается остаток отделения \textbf{s} на \textbf{r}. Начальное состояние \textbf{s} задается на входе. Предметы в ячейках определяются следующим образом. Для каждой клетки генерируем случайное число из множества \{\textbf{0}, \textbf{1}, \textbf{2}\} (то есть \textbf{r} = \textbf{3}). Если это число равно нулю, то в клетке находится камень, если один, то бумага, а в случае двух - ножницы. Клетки просматриваются строка за строкой сверху вниз, клетки в одной строке просматриваются слева направо. Таким образом, порядок обхода клеток следующий: (\textbf{1}, \textbf{1}), (\textbf{1}, \textbf{2}), ... , (\textbf{1}, \textbf{n}), (\textbf{2}, \textbf{1}), (\textbf{2}, \textbf{2}), ... , (\textbf{2}, \textbf{n}), ... , (\textbf{m}, \textbf{1}), (\textbf{m}, \textbf{2}), ... , (\textbf{m}, \textbf{n}). \includegraphics{https://static.e-olymp.com/content/d9/d98be79eb148ae50821afda889189efe62f16b70.jpg} Очень важно завершить путешествие за время, не большее того, за которое можно пройти из ячейки (\textbf{1}, \textbf{1}) в ячейку (\textbf{m}, \textbf{n}) по прямой со скоростью, равной половине максимальной плюс три лишних хода. Формально количество ходов не должно превосходить действительное число . По заданному размеру поля, максимальной длине прыжка за один ход и начальному состоянию случайного числового генератора найдите путь, удовлетворяющий всем заданным условиям. \InputFile Первая строка содержит \textbf{m}, \textbf{n}, \textbf{d} и \textbf{s}: высота и ширина поля, максимальное расстояние одного хода и начальное состояние числового генератора (\textbf{100} ≤ \textbf{m}, \textbf{n} ≤ \textbf{2^16}, \textbf{10} ≤ \textbf{d} ≤ \textbf{100}, \textbf{0} ≤ \textbf{s} ≤ \textbf{2^32} - \textbf{1}). Обратите внимание на то, что нижние границы для чисел \textbf{m}, \textbf{n} и \textbf{d} достаточно большие. \OutputFile В первой строке вывести количество ходов \textbf{k} в найденном пути. В следующих (\textbf{k} + \textbf{1}) строке вывести координаты посещенных ячеек в порядке обхода. Сначала выводить номер строки, потом колонки. \includegraphics{https://static.e-olymp.com/content/d9/d98be79eb148ae50821afda889189efe62f16b70.jpg} Первой клеткой пути должна быть (\textbf{1}, \textbf{1}), последней (\textbf{m}, \textbf{n}). Каждая клетка должна быть посещена не более одного раза. Предмет на следующей клетке должен побеждать предмет на предыдущей. Расстояние между любыми двумя последовательными клетками пути не должно превосходить \textbf{d}, а общее количество ходов \textbf{k} не должно превосходить действительного числа . \includegraphics{https://static.e-olymp.com/content/36/36097bed7dcdc97591bacb91bf9038bd0bbc44f6.jpg} Если существует несколько путей, выведите один из них. Гарантируется, что во всех тестах существует путь, удовлетворяющий условиям длиной не больше . \Note Следующая таблица содержит значения \textbf{s} м предметы в посещаемых клетках заданного примера. \includegraphics{https://static.e-olymp.com/content/1c/1ceaa4e76d1a4530cee9b24457c52d38b4b1214c.jpg} \includegraphics{https://static.e-olymp.com/content/1d/1d094fce4b97cfd3d8e65accf5d89895d475c773.jpg} Значение дроби равно \textbf{3.0959}..., поэтому в примере следует совершить не более девяти ходов, а судьи формально гарантируют существование пути из семи или менее ходов.