| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 2 | 2 | 2 | 100.000% |
Маленький Ян очень много играл в компьютерные игры, поэтому родители запретили мальчику играть в его любимый <<Тетрис>>.
Но Ян не отчаивается. Он смастерил свою собственную игру --- <<Настольный Тетрис>>. Правила этой игры очень просты. Игра производится на прямоугольном поле размера $n \times m$. Изначально некоторые клетки поля заняты, а остальные свободны. Игроку требуется набором фигурок из тетриса покрыть все свободные клетки, при этом фигурки не должны накладываться друг на друга или на уже занятые клетки. Так как все фигурки с одной стороны покрашены, а с другой нет, то переворачивать их нельзя, однако можно их поворачивать.
Изначально Ян хотел выпилить бесконечно много фигурок каждого типа, но он очень быстро устал, поэтому у него есть только $a_i$ фигурок типа $i$.
Ян смастерил несколько полей для игры, и теперь ему интересно, можно ли их покрыть фигурками. Помогите Яну решить эту задачу.
В первой строке входного файла заданы два целых числа $n$ и $m$ ($1 \le n,m \le 6$) --- размеры игрового поля. В следующей строке заданы семь целых чисел $a_i$ ($0 \le a_i \le 10$). Следующие $n$ строк входного файла содержат описание поля. Каждая строка содержит $m$ символов. Символ '.' означает, что клетка свободна, '#' --- занята.
Если покрыть свободные клетки фигурками нельзя выведите в выходной файл единственное слово <<NIE>> (нет по-польски). Иначе в первой строке выведите единственное слово <<TAK>> (да по-польски). В следующих $n$ строках выведите описание покрытого поля. Каждая строка описания должна содержать $m$ целых чисел --- номера фигурок, которыми покрыты соответствующие клетки поля. Фигурки должны иметь номера от $1$ до $9$, при этом разные фигурки должны иметь разные номера. Для изначально занятых клеток требуется выводить $0$.
4 5 3 0 0 0 0 0 0 ....# ....# #..## #..##
TAK 1 1 2 2 0 1 1 2 2 0 0 3 3 0 0 0 3 3 0 0
4 5 2 1 0 0 0 0 0 ....# ....# #..## #..##
NIE
4 4 1 1 0 3 0 2 0 .... .... .... ....
TAK 1 1 1 3 1 2 3 3 2 2 3 4 2 4 4 4