A 国和 B 国各有 $n$ 个机场，两国间有 $m$ 条航线。

每条航线都有 $k$ 种不同的备选颜色。保证所有机场起飞的航线数量不超过 $k$。

第 $i$ 条航线往返于 A 国的机场 $u_i$ 和 B 国的机场 $v_i$，其第 $j$ 种备选颜色为 $c_{i, j}$。

给每条航线选择一种备选颜色，使得同一个机场起飞的航线的颜色互不相同。

输入格式

第一行三个整数 $n, m, k$。

接下来 $m$ 行，第 $i$ 行 $k + 2$ 个整数 $u_i, v_i, c_{i, 1}, c_{i, 2}, \cdots, c_{i, k}$。

输出格式

一行 $m$ 个整数 $a_1, a_2, \cdots, a_m$，表示第 $i$ 条航线的颜色为 $a_i$。

如果有多种方案，给出任意一种即可。保证存在至少一种合法方案。

样例输入

2 4 2
1 1 1 2 
1 2 2 3
2 1 1 3
2 2 2 3

样例输出

2 3 3 2

数据范围

保证 $1 \leq n, k \leq 150, 1 \leq m \leq n^2, 1 \leq c_{i, j} \leq \min(10^6, mk), 1 \leq u_i, v_i \leq n$。

保证不存在两条航线重合的情况，即不存在 $i \neq j$ 满足 $(u_i, v_i) = (u_j, v_j)$。