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