도장 찍기

시간 제한1초메모리 제한512 MB

요약

최대 100 by 100 그림의 # 칸을 . 칸을 칠하지 않고 주어진 스탬프로 모두 찍을 수 있는지 판단합니다.

난이도: 어려움10점 중 8점
유형: 백트래킹, 완전 탐색, 행렬
정답자: 아직 제출이 없습니다

문제

비투시는 오랫동안 모눈종이의 몇몇 칸을 사인펜으로 칠해 픽셀 그림을 만들며 놀았습니다. 완성한 그림은 침대 위에 걸어 두었고, 빈자리가 남아 있는 한 멈추지 않겠다고 했습니다.

엄마는 이 놀이가 아이의 시간을 너무 많이 빼앗는다고 생각해서, 예전에 가지고 놀던 도장들을 다락에서 가져다주었습니다. 각 도장은 종이에 찍으면 언제나 똑같은, 정해진 모양의 칸들을 “칠”합니다. 비투시는 도장이 마음에 들었지만, 이 도장들만으로 새 그림을 완성할 수 있을지 확신하지 못합니다.

완성할 그림의 모습과 각 도장이 찍는 모양이 주어질 때, 비투시가 사인펜을 쓰지 않고 그림을 완성할 수 있는지 판별하세요. 비투시는 도장을 회전하지 않습니다(두 번째 예제 참고). 그림은 종이 전체를 채우지 않지만, 그림에 속하지 않는 칸은 하나도 칠해져서는 안 된다는 점에 유의하세요(처음 두 예제 참고).

입력

첫째 줄에는 그림의 크기를 나타내는 두 정수 $W$ 와 $S$ 가 주어집니다 ( $1 \le W, S \le 100$ ).

다음 $W$ 개의 줄에는 각각 # 또는 . 문자가 $S$ 개씩 주어집니다. #는 그 칸이 적어도 한 번은 도장으로 칠해져야 함을, .는 그 칸이 비어 있어야 함을 뜻합니다.

그다음 줄에는 비투시가 가진 도장의 개수 $P$ 가 주어집니다 ( $1 \le P \le 20$ ).

각 도장의 설명은 그림과 비슷합니다. 먼저 도장의 크기를 나타내는 두 정수 $R$ 과 $C$ 가 주어지고 ( $1 \le R, C \le 10$ ), 이어서 # 또는 . 문자가 $C$ 개씩 있는 $R$ 개의 줄이 주어집니다. 도장을 어떤 위치에 찍으면 # 아래에 놓인 모든 칸이 칠해지고, . 아래에 놓인 칸의 상태는 바뀌지 않습니다.

출력

표준 출력에 한 단어를 출력합니다. 주어진 도장들로 그림을 완성할 수 있으면 TAK을, 그렇지 않으면 NIE를 출력합니다. (TAK은 “예”, NIE는 “아니오”라는 뜻입니다.)

예제3

예제 1

입력

5 5
..#..
.###.
..#..
..###
..#..
2
3 5
.....
.###.
.....
4 1
#
#
#
#

예상 출력

TAK

예제 2

입력

6 6
##....
######
.####.
.#####
.##.##
.#....
1
2 2
##
#.

예상 출력

NIE

예제 3

입력

5 13
#####.#.#####
#...#.#.#....
#...#.#.#.###
#...#.#.#...#
#####.#.#####
4
3 3
.#.
###
.#.
3 5
#...#
#....
#...#
1 3
###
2 5
....#
#####

예상 출력

TAK