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) $。