시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 9 4 3 42.857%

문제

동규는 이번에 새로 나온 그림판 프로그램을 설치했다. 이 프로그램에서 지원하는 색상의 개수는 K개이며, 각 색상은 1부터 K까지 번호가 매겨져 있다. 그림을 그릴 수 있는 캔버스의 크기는 N*N이다. 가장 처음에 모든 칸은 흰색 (1번 색상)으로 칠해져 있다. 이 그림판은 마우스를 이용해서 그림을 그릴 수 없고 키보드로 명령어를 입력해야 한다.

캔버스의 가장 왼쪽 위 칸의 좌표는 (0, 0)이다. 첫 번째 좌표는 x로 행ㅇ르 나타내고, 두 번째 좌표는 y로 열을 나타낸다.

동규가 가장 좋아하는 그림판 명령어는 PAINT c x1 y1 x2 y2이다. 이 명령어는 선택한 직사각형을 체스판 패턴으로 칠한다. 여기서 c는 색칠할 색상이고, (x1, y1), (x2, y2)는 색칠할 직사각형의 왼쪽 위와 오른쪽 아래 좌표이다.

가장 왼쪽 위 칸의 색상은 명령어에서 고른 색상 c가 된다. 나머지 칸의 색은 체스판 패턴에 의해서 결정된다. 이 때, 색칠되지 않는 칸의 색상은 원래 색상을 그대로 유지한다. 아래 그림은 흰색 캔버스에 빨간 체스판 패턴을 칠했을 때의 모습이다.

그림판에는 두 가지 명령어가 더 있다. 첫 번째는 SAVE로 현재 캔버스를 저장하는 명령이다. 두 번째 명령은 LOAD x로 x번째 저장한 캔버스를 불러오는 명령이다.

하루종일 그림을 그리던 동규는 실수로 저장을 하지 않고 프로그램을 종료했다. 하지만, 이 프로그램은 사용자가 입력한 명령을 순서대로 저장하고 있다. 동규가 입력한 명령을 수행했을 때, 각 칸에 색칠되어 있는 색상을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1000), K(2 ≤ K ≤ 100,000), M(1 ≤ M ≤ 100,000, M은 명령의 개수)이 주어진다.

다음 M개의 줄에는 문제에서 설명한 세 가지 명령어중 하나가 주어진다. 올바르지 않은 명령이 주어지는 경우는 없다.

출력

N개 줄에 각 칸의 색상을 나타내는 N개의 숫자를 출력한다.

예제 입력

3 4 7
PAINT 2 0 0 1 1
SAVE
PAINT 3 1 1 2 2
SAVE
PAINT 4 0 2 0 2
LOAD 2
PAINT 4 2 0 2 0

예제 출력

2 1 1
1 3 1
4 1 3

힌트