身為一名演算法愛好者，Mike 對於處理過於複雜的系統感到吃力並不令人意外。不幸的是，這在他目前實習的公司中變成了一個大問題。

Mike 被指派的專案涉及維護公司的「智慧平行運算叢集」。這只是一個好聽的名字；實際上，該系統只是一個簡單的作業排程器，總共處理 $n$ 個作業。某些作業在執行前可能依賴於其他作業的成功執行。總共有 $m$ 個這樣的依賴關係。

保證作業之間不存在（直接或間接的）循環依賴。

當執行開始時，系統會智慧地選擇一個執行順序，以確保滿足所有依賴關係（順序在不同執行之間可能會改變）。在選擇了有效的順序後，它會按照該順序開始執行 $n$ 個作業中的每一個。當系統開始執行一個作業時，它會將該作業的 ID 列印到日誌檔案中。

不幸的是，今天是 Mike 在公司實習的第一天，他不太謹慎。結果，他不小心並行執行了該系統 $k$ 次。系統開始不穩定地啟動作業並列印到日誌檔案。現在，日誌檔案包含了 $n \cdot k$ 個所有已執行作業的 ID。來自同一次執行的作業 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$)，代表日誌檔案中每個作業對應的執行 ID。具體來說，$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