アルゴリズム愛好家の見習いであるMikeが、過度に複雑なシステムに苦戦するのは驚くことではありません。残念なことに、これが現在インターンをしている会社で大きな問題となってしまいました。

Mikeに割り当てられたプロジェクトは、会社の「Intelligent Cluster for Parallel Computation（並列計算用インテリジェント・クラスター）」をいじることでした。これは単なる大げさな名前に過ぎず、実際には合計 $n$ 個のジョブを処理する単純なジョブスケジューラーです。ジョブの中には、実行される前に他のジョブの実行が完了していなければならないものがあります。合計で $m$ 個の依存関係が存在します。

ジョブ間に（直接的または間接的な）循環依存関係がないことが保証されています。

実行が開始されると、システムはすべての依存関係が満たされるようにジョブを実行する順序をインテリジェントに選択します（順序は実行ごとに変わる可能性があります）。有効な順序を選択した後、システムはその順序で $n$ 個の各ジョブの実行を開始します。システムがジョブの実行を開始すると、そのジョブのIDがログファイルに出力されます。

あいにく今日はMikeのインターン初日であり、彼はあまり注意深くありませんでした。その結果、彼は誤ってシステムを $k$ 回並列に実行してしまいました。システムは不規則にジョブを開始し、ログファイルへの出力を始めました。現在、ログファイルには実行されたすべてのジョブのIDが合計 $n \cdot k$ 個含まれています。同じ実行からのジョブIDは実行された順序で出力されていますが、異なる実行からの出力は任意に混ざり合っている可能性があります。

あなたのタスクは、ログファイル内の情報から、各ジョブが $k$ 回の実行のうちのどれに属していたかを特定することです。

入力

入力の最初の行には、3つの整数 $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$ より前に実行されなければならない」という依存関係を表しています。

最後に、入力の最後の行には、ログファイルに順番に出力されたジョブIDである $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$ に対して) を1行で出力してください。具体的には、$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