Камень-Бумага-Ножницы на плоскости

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

Шахматная доска на плоскости состоит из m строк и n колонок. Каждая ячейка доски содержит один из трех предметов: гору, бумагу или ножницы. Движение начинается в клетке (1, 1) и совершается по направлению к (m, n) выполнением последовательности ходов. Ходом называется перемещение в любую клетку, расположенную не дальше чем d от текущей. Расстояние измеряется между центрами ячеек: расстояние между ячейками (x_1, y_1) и (x_2, y_2) равно . Каждый ход следует совершать в ячейку, содержащую предмет, который наносит поражение предмету в предыдущей ячейке. Как и в игре "Камень-Бумага-Ножницы”, камень побеждает ножницы, ножницы побеждают бумагу, а бумага побеждает камень. Когда мы заходим в ячейку, то убираем из нее предмет, таким образом запрещено дважды посещать одну и ту же ячейку.

Поле довольно большое, поэтому предметы в ячейках определяются генератором случайных чисел, или более точно, линейным конгруэнтным генератором. Этот генератор имеет состояние, представляющее собой целое число s от 0 до 2^32 - 1. Для получения следующего случайного числа от 0 до r - 1 выполняется присваивание s := (s ∙ 1 664 525 + 1 013 904 223) mod 2^32 и возвращается остаток отделения s на r. Начальное состояние s задается на входе.

Предметы в ячейках определяются следующим образом. Для каждой клетки генерируем случайное число из множества {0, 1, 2} (то есть r = 3). Если это число равно нулю, то в клетке находится камень, если один, то бумага, а в случае двух - ножницы. Клетки просматриваются строка за строкой сверху вниз, клетки в одной строке просматриваются слева направо. Таким образом, порядок обхода клеток следующий: (1, 1), (1, 2), ... , (1, n), (2, 1), (2, 2), ... , (2, n), ... , (m, 1), (m, 2), ... , (m, n).

Очень важно завершить путешествие за время, не большее того, за которое можно пройти из ячейки (1, 1) в ячейку (m, n) по прямой со скоростью, равной половине максимальной плюс три лишних хода. Формально количество ходов не должно превосходить действительное число .

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

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

Первая строка содержит m, n, d и s: высота и ширина поля, максимальное расстояние одного хода и начальное состояние числового генератора (100 ≤ m, n ≤ 2^16, 10 ≤ d ≤ 100, 0 ≤ s ≤ 2^32 - 1). Обратите внимание на то, что нижние границы для чисел m, n и d достаточно большие.

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

В первой строке вывести количество ходов k в найденном пути. В следующих (k + 1) строке вывести координаты посещенных ячеек в порядке обхода. Сначала выводить номер строки, потом колонки.

Первой клеткой пути должна быть (1, 1), последней (m, n). Каждая клетка должна быть посещена не более одного раза. Предмет на следующей клетке должен побеждать предмет на предыдущей. Расстояние между любыми двумя последовательными клетками пути не должно превосходить d, а общее количество ходов k не должно превосходить действительного числа .

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

Примеры

Примечание

Следующая таблица содержит значения s м предметы в посещаемых клетках заданного примера.

Значение дроби равно 3.0959..., поэтому в примере следует совершить не более девяти ходов, а судьи формально гарантируют существование пути из семи или менее ходов.