알고리즘 애호가인 견습생 Mike가 지나치게 복잡한 시스템을 다루는 데 어려움을 겪는 것은 그리 놀라운 일이 아닙니다. 불행히도, 이는 현재 그가 인턴으로 근무 중인 회사에서 큰 문제가 되었습니다.

Mike가 맡은 프로젝트는 회사의 '지능형 병렬 컴퓨팅 클러스터'를 다루는 것입니다. 이는 거창한 이름일 뿐, 실제로는 총 $n$개의 작업을 처리하는 단순한 작업 스케줄러입니다. 일부 작업은 다른 작업이 성공적으로 실행된 후에만 실행될 수 있습니다. 이러한 의존 관계는 총 $m$개 존재합니다.

작업 간에는 (직접적이든 간접적이든) 순환 의존성이 없음이 보장됩니다.

실행이 시작되면, 시스템은 모든 의존성을 만족하도록 작업을 실행할 순서를 지능적으로 선택합니다(순서는 실행마다 달라질 수 있습니다). 유효한 순서를 선택한 후, 시스템은 $n$개의 작업을 해당 순서대로 실행하기 시작합니다. 시스템이 작업을 실행하기 시작할 때, 해당 작업의 ID를 로그 파일에 출력합니다.

불행히도 오늘은 Mike가 회사에서 인턴으로 일한 첫날이었고, 그는 그다지 신중하지 못했습니다. 그 결과, 그는 실수로 시스템을 $k$번 병렬로 실행했습니다. 시스템은 불규칙하게 작업을 시작하고 로그 파일에 출력하기 시작했습니다. 이제 로그 파일에는 실행된 모든 작업의 ID가 $n \cdot k$개 포함되어 있습니다. 같은 실행에서 나온 작업 ID들은 실행된 순서대로 출력되었지만, 서로 다른 실행에서 나온 출력들은 임의로 섞여 있을 수 있습니다.

당신의 임무는 로그 파일에 있는 정보를 바탕으로 각 작업이 $k$번의 실행 중 어느 실행에서 수행되었는지 알아내는 것입니다.

입력

첫 번째 줄에는 세 정수 $n, k, m$ ($1 \le n, k \le 500\,000$, $0 \le m \le 250\,000$, $n \cdot k \le 500\,000$)이 주어지며, 이는 시스템의 작업 수, Mike가 트리거한 실행 횟수, 의존성 개수를 나타냅니다.

이어지는 $m$개의 줄에는 각각 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$, 모든 $1 \le i \le m$에 대하여) 쌍이 주어지며, 이는 "작업 $a_i$는 작업 $b_i$보다 먼저 실행되어야 한다"는 의존성을 나타냅니다.

마지막 줄에는 로그 파일에 출력된 순서대로 $n \cdot k$개의 정수 $c_i$ ($1 \le c_i \le n$, 모든 $1 \le i \le n \cdot k$에 대하여)가 주어집니다.

출력

로그 파일에 나타난 각 작업에 해당하는 실행 ID를 나타내는 $n \cdot k$개의 정수 $r_i$ ($1 \le r_i \le k$, 모든 $1 \le i \le n \cdot k$에 대하여)를 한 줄에 출력하십시오. 구체적으로, $r_i$는 로그 파일에 나타난 $i$번째 작업에 해당하는 실행 ID여야 합니다.

여러 해답이 가능한 경우, 그중 아무거나 하나를 출력해도 됩니다. 입력 데이터는 유효하며 항상 해답이 존재함이 보장됩니다.

예제

입력 1

3 3 2
1 2
1 3
1 1 2 3 3 2 1 2 3

출력 1

1 2 2 1 2 1 3 3 3