作为一名算法初学者，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