Задача: Склад

На складе имеется 8 ящиков видов <<A>>, <<Б>>, <<В>>, <<Г>>, по два ящика каждого вида. Ящики распределены на 4 стопки, пронумерованных числами от 1 до 4. Первоначально в стопке 1 ящик A стоял на ящике В, в стопке 2 — ящик Б на ящике В, в стопке 3 — ящик A на ящике Г, в стопке 4 — ящик Б на ящике Г (см. рисунок).

Вам необходимо переставить ящики так, чтобы в каждой стопке были ящики одного вида (порядок неважен), например, все ящики вида А могут оказаться в стопке 2, все ящики вида Б — в стопке 4 и т.д.

При помощи погрузчика вы можете взять верхний ящик из одной стопки и поставить его поверх другой стопки. Например, если переставить ящик из стопки 1 в стопку 2, то получится следующее расположение:

Инструкцию для погрузчика будем записывать в виде двух чисел. Первое число — номер стопки, из которой берётся ящик, второе число — номер стопки, в которую перемещается ящик. Пример перемещения выше будет записываться, как <<1 2>>.

Одно перемещение выполняется за одну минуту. Но у вас есть два погрузчика, и если они не мешают друг другу, то могут выполнять два перемещения одновременно. У одновременно выполняемых перемещений все номера стопок (как начальных, так и конечных) должны быть различны. Например, можно одновременно выполнить перемещения <<1 3>> и <<4 2>>, но нельзя одновременно выполнить перемещения <<1 3>> и <<3 2>>, потому что стопка номер 3 участвует в каждом из этих перемещений.

Запишите последовательность перемещений, в результате выполнения которых ящики будут расставлены нужным образом. В каждой строке записывайте ровно одно перемещение (два числа). Если два перемещения выполняются одновременно, они также записываются в двух соседних строках, например:

3
4 2

Формат записи ответа:

Ответ — это последовательность строк. Каждая строка описывает одно перемещение в формате:
<номер стопки-источника> <номер стопки-назначения>

Чтобы указать, что два перемещения выполняются параллельно, запишите их в двух соседних строках. Порядок этих строк имеет значение: первая записанная операция будет выполняться первым погрузчиком, вторая — вторым.

Пример записи параллельных ходов:

1 4
2 3

Это означает, что первый погрузчик забирает верхний ящик из стопки 1 и кладёт его на стопку 4, а второй погрузчик в то же самое время забирает ящик из стопки 2 и кладёт его на стопку 3. На это будет затрачена 1 минута.

Ваш ответ: