탄광

바이테시아의 한 탄광에서 최근 파업이 일어났다. 분노한 광부들이 탄광의 모든 데이터를 파괴했다. 당신은 탄광의 여러 부분에서 어떤 종류의 석탄을 캤는지에 대한 데이터를 복구하기 위해 고용되었다.

회사는 $k$가지 종류의 석탄을 채굴한다. 탄광은 직사각형 격자이다. 격자의 모든 단위 정사각형은 정확히 한 종류의 석탄을 채굴하는 구역이다. 단위 정사각형 변의 일부 중점에는 엘리베이터가 있고, 탄광에서 채굴되는 $k$가지 석탄 종류마다 하나씩 있다. 탄광은 예술 작품이어야 하므로, 석탄 종류 $i$를 채굴하는 단위 정사각형의 집합은 석탄 종류 $i$에 배정된 엘리베이터가 있는 점에 대해 대칭이다.

탄광의 크기, 수 $k$, 그리고 $k$개 엘리베이터의 위치가 주어진다. 당신의 임무는 위 조건을 만족하도록 단위 정사각형을 석탄 종류에 배정하는 방법을 결정하거나, 그러한 배정이 존재하지 않음을 판별하는 것이다.

입력의 첫 줄에는 정수 $z$, 즉 테스트 케이스의 수가 주어진다. 그다음 $z$개의 테스트 케이스가 다음과 같이 이어진다.

각 테스트 케이스 설명의 첫 줄에는 세 정수 $n$, $m$, $k$가 주어진다 ($1 \leq n, m$, $n \cdot m \leq 1\,500$, $1 \leq k \leq 100$). 이는 탄광의 크기와 탄광에서 채굴되는 서로 다른 석탄 종류의 수이다. 탄광의 가장 왼쪽 위 칸의 왼쪽 위 모서리 좌표는 $(0, 0)$이고, 가장 오른쪽 아래 칸의 오른쪽 아래 모서리 좌표는 $(n, m)$이다.

그다음 $k$개 엘리베이터의 위치가 이어진다. 각 위치는 엘리베이터 $i$, $j$의 좌표를 담은 한 줄로 주어진다 ($0 \leq i \leq n$, $0\leq j \leq m$). $i, j$ 중 정확히 하나는 정수이고 다른 하나는 정수의 절반이며, 이는 격자 단위 정사각형 변 위의 한 점을 나타낸다. ($1$부터 시작하여) $l$번째 엘리베이터는 석탄 종류 $l$에 배정된다.

각 테스트 케이스마다, 격자의 모든 단위 정사각형에 석탄 종류를 올바르게 배정하는 방법이 존재하면 "YES"를, 존재하지 않으면 "NO"를 한 줄에 출력해야 한다. 또한 그러한 배정이 존재하면, 이어서 $n$개의 줄을 출력해야 하며, 각 줄에는 공백으로 구분된 $m$개의 정수가 있어야 한다. ($1$부터 시작하여) $i$번째 줄의 $j$번째 수는 왼쪽 위 좌표가 $(i - 1, j - 1)$이고 오른쪽 아래 좌표가 ($i, j$)인 정사각형에서 채굴되는 석탄 종류를 나타내는 정수여야 한다. 석탄 종류는 $1$부터 $k$까지의 정수로 표시한다. 가능한 답이 여러 개라면 그중 아무거나 하나를 출력한다.