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

У 2004 році мешканці планети Кремонід організували космічну експедицію для польоту до сусідньої галактики, де, на їхню думку, існує планета, придатна для життя. На космічному кораблі був збудований житловий комплекс, у якому розмістилося багато вчених.

Житловий комплекс має форму прямокутного паралелепіпеда розмірами n \times m \times k. Комплекс розділений на кубічні відсіки розміром 1 \times 1 \times 1, всього $nmk$ відсіків. Кожен відсік має координати (x, y, z), які відповідають його положенню у комплексі, де 1 \le x \le n, 1 \le y \le m, 1 \le z \le k.

Відстань між двома відсіками з координатами (x_1, y_1, z_1) та (x_2, y_2, z_2) визначається як:

Два відсіки знаходяться в одному ряду, якщо їх координати різняться рівно однією компонентою (наприклад, (2, 4, 3) та (2, 6, 3) знаходяться в одному ряду). Два відсіки вважаються сусідніми, якщо відстань між ними дорівнює одиниці.

У кожному відсіку було встановлено персональний комп’ютер. Після запуску жителі комплексу вирішили об’єднати свої комп’ютери в мережу. План побудови мережі такий: вибираються два відсіки в одному ряду. Перший з них називаємо початковим, другий — кінцевим. Робот, який прокладає мережу, починає з початкового відсіку. На кожному кроці робот переходить до сусіднього відсіку, відстань до кінцевого з якого мінімальна. При цьому він з'єднує комп’ютери у сусідніх відсіках вздовж шляху, якщо це не призводить до утворення циклу. Якщо таке з’єднання створило б цикл, робот запам’ятовує координати цієї пари сусідніх відсіків і не з’єднує їх комп’ютери. Робот переходить далі, поки не досягне кінцевого відсіку.

Ця процедура повторюється $q$ разів.

Ваше завдання — визначити, які пари відсіків запам’ятав робот.