Kosmik ekspedisiya
У 2004-cü ildə Kremonid planetinin sakinləri, həyat üçün yararlı bir planetin olduğunu düşündükləri qonşu qalaktikaya uçmaq üçün kosmik ekspedisiya təşkil etdilər. Kosmik gəmidə bir çox alimin yerləşdirildiyi yaşayış kompleksi qurulmuşdu.
Yaşayış kompleksi n×m×k ölçülərində düzbucaqlı paralelipiped formasındadır. Kompleks 1×1×1 ölçülərində kubik bölmələrə bölünmüşdür, cəmi nmk bölmə var. Hər bir bölmə kompleksdəki mövqeyinə uyğun gələn (x, y, z) koordinatlarına malikdir, burada 1 ≤ x ≤ n, 1 ≤ y ≤ m, 1 ≤ z ≤ k.
(x_1, y_1, z_1) və (x_2, y_2, z_2) koordinatlarına malik iki bölmə arasındakı məsafə
|x_1-x_2|+|y_1-y_2|+|z_1-z_2|
şəklində təyin olunur.
İki bölmə eyni sırada yerləşir, əgər onların koordinatları yalnız bir komponent üzrə fərqlənirsə (məsələn, (2, 4, 3) və (2, 6, 3) eyni sıradadır). İki bölmə qonşudur, əgər aralarındakı məsafə birlikdirsə.
Hər bir bölməyə fərdi kompüter quraşdırılmışdır. Uçuşdan sonra kompleksin sakinləri kompüterlərini şəbəkəyə birləşdirmək qərarına gəldilər. Şəbəkə çəkmə planı aşağıdakı prosedurdan ibarətdir: eyni sırada yerləşən iki bölmə seçilir. Birinci bölmə başlanğıc, ikincisi isə son bölmə adlanır. Şəbəkəni çəkən robot başlanğıc bölmədə işə başlayır. Hər addımda robot, son bölməyə olan məsafəsi minimal olan qonşu bölməyə keçir. Bu zaman, keçdiyi qonşu bölmələrdəki kompüterləri birləşdirir, əgər bu, dövrənin yaranmasına səbəb olmursa. Əgər birləşmə dövrə yaradırsa, robot həmin qonşu bölmələrin koordinatlarını yadda saxlayır və oradakı kompüterləri bir-birinə birləşdirmir. Robot son bölməyə çatana qədər hərəkət edir.
Bu prosedur q dəfə təkrarlanır.
Sizdən robotun yadda saxladığı bölmə cütlərini müəyyən etməyiniz tələb olunur.
Giriş verilənləri
Giriş faylının ilk sətiri dörd ədəd n, m, k, q (2 ≤ n, m, k ≤ 100, 1 ≤ q ≤ 20000) ehtiva edir.
Sonra robotun hərəkət etdiyi bölmə cütlərini təsvir edən q sətir gəlir. Hər sətir altı ədəd ehtiva edir: ilk üç ədəd başlanğıc bölmənin koordinatları, qalan üç ədəd isə son bölmənin koordinatlarıdır.
Çıxış verilənləri
Robotun yadda saxladığı hər bir bölmə cütü üçün çıxış faylı robotun keçdiyi qaydada bölmələrin koordinatları ilə altı ədəd ehtiva edən bir sətir içərməlidir.