Космическая экспедиция
В 2004 году обитатели планеты Кремонид организовали космическую экспедицию для полета в соседнюю галактику, где по их расчетам существует планета, пригодная для жизни. На космическом корабле был сконструирован жилой комплекс, куда заселили множество ученых.
Жилой комплекс имеет форму прямоугольного параллелепипеда, размерами n×m×k. Комплекс разбит на кубические отсеки с размерами 1×1×1, всего nmk отсеков. Каждый отсек имеет координаты (x, y, z), соответствующие положению отсека в комплексе, где 1 ≤ x ≤ n, 1 ≤ y ≤ m, 1 ≤ z ≤ k.
Расстоянием между двумя отсеками с координатами (x_1, y_1, z_1) и (x_2, y_2, z_2) назовем число
|x_1-x_2|+|y_1-y_2|+|z_1-z_2|.
Два отсека находятся в одном ряду, если их координаты отличаются ровно одной компонентой (например, (2, 4, 3) и (2, 6, 3) находятся в одном ряду). Два отсека являются соседними, если расстояние между ними равно единице.
В каждый отсек был установлен персональный компьютер. После взлета жители комплекса решили объединить свои компьютеры в сеть. Был разработан план прокладывания сети, который представляет собой следующую процедуру: выбираются два отсека, находящихся в одном ряду. Первый отсек назовем начальным, второй - конечным. Робот, прокладывающий сеть, стартует в начальном отсеке. На каждом шаге робот передвигается в тот соседний отсек, расстояние от которого до конечного минимально. При этом он соединяет пары компьютеров в соседних отсеках, через которые он проходит, если это не приводит к образованию цикла. Если же соединение приводит к образованию цикла, то робот запоминает координаты этой пары соседних отсеков и не соединяет компьютеры в них между собой. Робот перемещается, пока не достигнет конечного отсека.
Указанная процедура повторяется q раз.
Вам необходимо определить, какие пары отсеков запомнил робот.
Входные данные
Первая строка входного файла содержит четыре числа n, m, k, q (2 ≤ n, m, k ≤ 100, 1 ≤ q ≤ 20000).
Далее следует q строк, описывающих пары отсеков, между которыми продвигается робот. Каждая строка содержит шесть чисел: первые три числа - координаты начального отсека, оставшиеся три числа - координаты конечного отсека.
Выходные данные
Для каждой пары отсеков, которую робот запомнил, выходной файл должен содержать строку с шестью числами - координатами отсеков в порядке прохождения их роботом.