Задачі
Космічна експедиція
Космічна експедиція
У \textbf{2004} році мешканці планети Кремонід організували космічну експедицію для польоту у сусідню галактику, де за їхніми розрахунками існує планета, придатна для життя. На космічному кораблі було сконструйовано житловий комплекс, куд заселили багато вчених.
Житловий комплекс має форму прямокутного паралелепвпеда, розмврами \textbf{n}×\textbf{m}×\textbf{k}. Комплекс разбито на кубічні відсіки з розмірами \textbf{1}×\textbf{1}×\textbf{1}, усього \textbf{nmk} відсіків. Кожен відсік має координати \textbf{(x, y, z)}, які відповідають положенню відсіку у комплексі, де \textbf{1} ≤ \textbf{x} ≤ \textbf{n}, \textbf{1} ≤ \textbf{y} ≤ \textbf{m}, \textbf{1} ≤ \textbf{z} ≤ \textbf{k}.
Відстанню між двома відсіками з координатами \textbf{(x_1, y_1, z_1)} та \textbf{(x_2, y_2, z_2)} назвемо число
\textbf{|x_1-x_2|+|y_1-y_2|+|z_1-z_2|}.
Два відсіки знаходяться у одному ряду, якщо їхні координати відрізняються рівно однією компонентою (наприклад, \textbf{(2, 4, 3)} та \textbf{(2, 6, 3)} знаходяться у одному ряду). Два відсіки є сусідніми, якщо відстань між ними дорівнює одиниці.
У кожен відсік було встановлено персональний комп'ютер. Після зльоту жителі комплексу вирішили об'єднати свої комп'ютери у мережу. Було розроблено план прокладання мережі, який являє собою наступну процедуру: вибираються два відсіки, які знаходяться в одному ряду. Перший відсік назвемо початковим, другий - кінцевим. Робот, який прокладає мережу, стартує у початковому відсіку. На кожному кроці робот пересувається у той сусідній відсік, відстань від якого до кінцевого мінімальна. При цьому він з'єднує пари комп'ютерів у сусідніх відсіках, через які він проходить, якщо це не призводить до утворення циклу. Якщо ж з'єднання призводить до утворення циклу, то робот запам'ятовує координати цієї пари сусідніх відсіків і не з'єднує комп'ютери у них між собою. Робот переміщується, доки не досягне кінцевого відсіку.
Вказана процедура повторюється \textbf{q} разів.
Вам необхідно визначити, які пари відсіків запам'ятав робот.
\InputFile
Перший рядок вхідного файлу містить чотири числа \textbf{n}, \textbf{m}, \textbf{k}, \textbf{q} (\textbf{2} ≤ \textbf{n}, \textbf{m}, \textbf{k} ≤ \textbf{100}, \textbf{1} ≤ \textbf{q} ≤ \textbf{20000}).
Далі йде \textbf{q} рядків, які описують пари відсіків, між якими просувається робот. Кожен рядок містить шість чисел: перші три числа - координати початкового відсіку, три числа, що залишились, - координати кінцевого відсіку.
\OutputFile
Для кожної пари відсіків, які робот запам'ятав, вихідний файл повинен містити рядок з шістьмома числами - координатами відсіків у порядку проходження їх роботом.
Вхідні дані #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
Вихідні дані #1
2 1 1 2 2 1