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

В 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$ раз.

Ваша задача — определить, какие пары отсеков запомнил робот.