Коровы увлеклись буквенными пазлами. В $R$ строках ($(1 \le R \le 10)$) и $C$ столбцах ($(1 \le C \le 10)$) края — буквы, а не фигурный картон.

У каждой детали номер и $4$ буквы или границы, совмещаемые как в обычном пазле. Псевдобуква 0 (цифра ноль) — граница. Их может быть несколько у угловой детали или даже верхней детали столбца в пазле $4\times1$. Ниже шесть деталей собраны одним из многих способов; границы показаны линиями вместо 0.

              +---+  +---+  +---+
              | 1 c  c 3 d  d 5 |
              +-d-+  + a +  +-e-+

              +-d-+  +-a-+  +-e-+
              | 2 b  b 4 b  b 6 |
              +---+  +---+  +---+

Буквы соприкасающихся краёв совпадают, границы правильно расположены сверху, снизу и по бокам.

Деталь задаётся номером и четырьмя краями по часовой стрелке, буквы $a,\ldots,z$ или 0. При размещении возможен поворот.

Найдите хотя бы одну сборку. Тесты с большими $R$ и $C$ легче благодаря большему разнообразию букв краёв.

Входные данные

• Строка $1$: целые $R$ и $C$ через пробел.

• Строки $2,\ldots,R\times C+1$: пять значений через пробел — целый номер и четыре обозначения краёв.

Выходные данные

• Строки $1,\ldots,R\times C$: строка $R\times (i-1)+j$ описывает деталь в строке $i$, столбце $j$: пять значений через пробел — целый номер и края сверху, справа, снизу, слева.

Примеры

Входные данные 1

2 3
1 c d 0 0
2 0 d b 0
3 c 0 d a
4 b a b 0
5 d 0 0 e
6 0 0 b e

Выходные данные 1

1 0 c d 0
3 0 d a c
5 0 0 e d
2 d b 0 0
4 a b 0 b
6 e 0 0 b

Примечание

Вход описывает пазл, но некоторые детали повёрнуты относительно примера ответа.

Как на рисунке в условии. Другие решения, например отражения, допустимы; проверяющая программа проверит ответ.

Автор задачи: Rob Kolstad, 2008