Кладбище имеет форму прямоугольника, в котором N рядов по M могил в каждом ряду. Кладбище окружено высокой стеной. Как вы уже знаете, Лара Крофт проникла на кладбище через подкоп с северо-западного угла с целью добыть спрятанное сокровище. Для этого она прорыла под кладбищем длинный подземный ход по такому правилу:

1. Если дальше по ходу движения хода находилась целая могила, то Лара удлиняла ход и разоряла эту могилу.
2. Если же впереди была стена кладбища или уже разорённая могила, то Лара поворачивала на 90 градусов вправо и продолжала своё подлое дело.

Лара только что нашла сокровище в могиле (r_T, c_T) и отправилась домой пить шампанское. Но тёмные силы решили устроить ей ловушку. Как только Лара дойдёт до могилы (r_L, c_L), запустится охранная сигнализация компании «LaraKiller», оживляющая скелетов в некоторых из разорённых могил. Все эти скелеты оживают одновременно, ровно через T секунд после включения сигнализации.

Лара понимает, что включилась сигнализация. Она может убежать с кладбища (если успеет) или спрятаться в одной из могил, которые она до этого разорила. Лара может бежать по своему подземному ходу (в сторону выхода или обратно) со скоростью не более одной могилы в секунду, поэтому за T секунд она может успеть спрятаться в любой из разорённых могил на расстоянии не более T от (r_L, c_L), считая по прорытому ходу.

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

В первой строке записаны целые числа N и M — размеры кладбища (2 ≤ N, M ≤ 100). Северо-западная могила имеет координаты (1, 1) а юго-восточная — (N, M). Лара начала рыть свой ход с могилы (1, 1), двигаясь на восток, то есть к могиле (1, 2).

Во второй строке записаны целые числа r_T и c_T — координаты могилы с сокровищем. В третьей строке записаны целые числа r_L и c_L — координаты Лары в момент включения сигнализации. 1 ≤ r_T, r_L ≤ N; 1 ≤ c_T, c_L ≤ M. Гарантируется, что ход, прорытый от могилы (1, 1) до могилы (r_T, c_T), проходит через могилу (r_L, c_L).

В четвёртой строке записано целое число T — время оживления скелетов, в секундах (0 ≤ T ≤ 27000).

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

На рисунке отмечены могилы, в которых Лара может успеть спрятаться.