Country A and Country B each have $n$ airports, and there are $m$ flight routes between the two countries.

Each route has $k$ different alternative colors. It is guaranteed that the number of routes departing from any airport does not exceed $k$.

The $i$-th route connects airport $u_i$ in Country A and airport $v_i$ in Country B, and its $j$-th alternative color is $c_{i, j}$.

Assign one alternative color to each route such that all routes departing from the same airport have distinct colors.

Input

The first line contains three integers $n, m, k$.

The next $m$ lines each contain $k + 2$ integers $u_i, v_i, c_{i, 1}, c_{i, 2}, \cdots, c_{i, k}$.

Output

A single line containing $m$ integers $a_1, a_2, \cdots, a_m$, representing the color assigned to the $i$-th route.

If there are multiple solutions, any one is acceptable. It is guaranteed that at least one valid solution exists.

Examples

Input 1

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

Output 1

2 3 3 2

Constraints

It is guaranteed that $1 \leq n, k \leq 150$, $1 \leq m \leq n^2$, $1 \leq c_{i, j} \leq \min(10^6, mk)$, and $1 \leq u_i, v_i \leq n$.

It is guaranteed that no two routes are identical, i.e., there are no $i \neq j$ such that $(u_i, v_i) = (u_j, v_j)$.

Subtasks