eolymp
bolt
Try our new interface for solving problems
Məsələlər

Космическая экспедиция

Космическая экспедиция

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

В 2004 году обитатели планеты Кремонид организовали космическую экспедицию для полета в соседнюю галактику, где по их расчетам существует планета, пригодная для жизни. На космическом корабле был сконструирован жилой комплекс, куда заселили множество ученых.

Жилой комплекс имеет форму прямоугольного параллелепипеда, размерами n×m×k. Комплекс разбит на кубические отсеки с размерами 1×1×1, всего nmk отсеков. Каждый отсек имеет координаты (x, y, z), соответствующие положению отсека в комплексе, где 1xn, 1ym, 1zk.

Расстоянием между двумя отсеками с координатами (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 раз.

Вам необходимо определить, какие пары отсеков запомнил робот.

Giriş verilənləri

Первая строка входного файла содержит четыре числа n, m, k, q (2n, m, k100, 1q20000).

Далее следует q строк, описывающих пары отсеков, между которыми продвигается робот. Каждая строка содержит шесть чисел: первые три числа - координаты начального отсека, оставшиеся три числа - координаты конечного отсека.

Çıxış verilənləri

Для каждой пары отсеков, которую робот запомнил, выходной файл должен содержать строку с шестью числами - координатами отсеков в порядке прохождения их роботом.

Nümunə

Giriş verilənləri #1
3 3 2 4
1 1 1 2 1 1
1 2 1 2 2 1
1 3 1 1 1 1
2 1 1 2 3 1

Çıxış verilənləri #1
2 1 1 2 2 1