Kosmik ekspedisiya#5470

Kosmik ekspedisiya

2 saniyə

64 meqabayt

Çox asan

2004-cü ildə Kremonid planetinin sakinləri, həyat üçün yararlı olduğunu düşündükləri qonşu qalaktikaya uçmaq üçün kosmik ekspedisiya təşkil etdilər. Kosmik gəmidə bir çox alim üçün yaşayış kompleksi qurulmuşdu.

Yaşayış kompleksi $n \times m \times k$ n \times m \times k ölçülərində düzbucaqlı paralelpiped formasındadır. Kompleks $1 \times 1 \times 1$ 1 \times 1 \times 1 ölçülərində kubik bölmələrə bölünüb, cəmi $nmk$ bölmə var. Hər bir bölmə kompleksdəki mövqeyinə uyğun gələn $(x, y, z)$ (x, y, z) koordinatlarına malikdir, burada $1 \leq x \leq n$ 1 \le x \le n, $1 \leq y \leq m$ 1 \le y \le m, $1 \leq z \leq k$ 1 \le z \le k.

$(x_{1}, y_{1}, z_{1})$ (x_1, y_1, z_1) və $(x_{2}, y_{2}, z_{2})$ (x_2, y_2, z_2) koordinatlarına malik iki bölmə arasındakı məsafə aşağıdakı kimi təyin olunur:

∣ x_{1} - x_{2} ∣ + ∣ y_{1} - y_{2} ∣ + ∣ z_{1} - z_{2} ∣.

|x_1-x_2| + |y_1-y_2| + |z_1-z_2|.

İki bölmə eyni sıradadır, əgər onların koordinatları yalnız bir komponent üzrə fərqlənirsə (məsələn, $(2, 4, 3)$ (2, 4, 3) və $(2, 6, 3)$ (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ənin qurulma planı belədir: eyni sırada yerləşən iki bölmə seçilir. Birinci bölmə başlanğıc, ikinci isə son bölmə adlanır. Şəbəkəni quran 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ə yaradarsa, 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ş

Giriş faylının ilk sətri dörd ədəd $n$ , $m$ , $k$ , $q$ ( $2 \leq n, m, k \leq 100$ 2 \le n, m, k \le 100, $1 \leq q \leq 20000$ 1 \le q \le 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 üçü başlanğıc bölmənin koordinatları, qalan üçü isə son bölmənin koordinatlarıdır.

Çıxış

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.

Nümunələr

Nümunə 1