시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 207 21 8 16.327%

문제

준하는 세계적인 화가이다. 한때 수학의 길을 걷고자 했으나 꿈을 접고 미술계에 몸을 담게 되었다. 준하의 작품은 도장을 이용하여 만드는 것으로 유명하다.

준하는 크기와 모양이 각각 다른 도장을 여러 개 준비한 다음, 도화지 여기저기에 도장을 찍는 방법으로 작품을 만든다. 이런 독특한 방식으로 만든 작품이 수억을 호가하다 보니 모조품을 만들려는 세력이 존재하기 마련이다.

바로 강민이가 그러하다. 강민이는 준하의 작품을 모방하고 양산해서 거액을 벌어들이려는 야망을 품고 있다. 강민이를 도와 도장의 종류와 도장을 찍는 좌표가 주어졌을 때, 좌표대로 도장을 찍어 그림을 완성하는 프로그램을 만들어주자.

입력

첫째 줄에 도화지의 세로 크기 N과 가로 크기 M이 주어진다. (1≤N,M≤1,000)

둘째 줄에 도장의 수 K가 주어진다. (1≤K≤500) 그다음 줄부터 도장의 크기와 모양이 K개 주어진다. 한 도장마다 도장의 크기 H, W가 주어지고, 다음 줄부터 H 줄에 걸쳐 도장의 모양이 주어진다. (1≤H,W≤500) 도장은 1번부터 K 번까지 번호가 매겨져 있다.

그 다음 도장을 찍는 좌표의 개수 Q 가 주어진다. (1≤Q≤10,000) 그 다음 줄 부터 Q줄에 걸쳐 도장의 번호 T와 도장을 찍을 좌표 Y,X가 순서대로 주어진다. (1≤T≤K) (0≤Y,X≤1,000)

Y, X는 도장을 찍을 좌표의 가장 왼쪽 위 좌표를 의미한다. 도화지를 벗어나는 입력은 주어지지 않는다.

출력

도화지에 그려진 그림을 출력한다. 출력된 그림의 크기는 도화지의 크기와 같아야 한다. 아무것도 그려지지 않은 좌표는 ‘.’으로 출력한다. 도장을 찍은 순서에 맞게 그림이 출력되어야 함에 유의하자.

예제 입력

5 5
2
3 3
ooo
ooo
ooo
3 3
xxx
xxx
xxx
3
1 0 0
2 1 1
1 2 2

예제 출력

ooo..
oxxx.
oxooo
.xooo
..ooo

힌트