Камінь-Папір-Ножиці на площині

У цій задачі вам потрібно пройти з одного кута шахівниці в протилежний, дотримуючись певних правил і уникаючи зайвих кроків.

Шахівниця на площині складається з 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..., тому в прикладі слід здійснити не більше дев'яти ходів, а судді формально гарантують існування шляху з семи або менше ходів.