Given a $d$-regular bipartite graph $G=(X,Y,E)$, where $|X|=|Y|=n$ and every vertex has degree $d$, find a perfect matching.

Input

The first line contains two positive integers $n$ and $d$, as described in the problem statement.

The next $n$ lines each contain $d$ positive integers. If the $j$-th integer in the $(i+1)$-th line is $k$, it means there is an edge between $x_i$ and $y_k$. There may be multiple edges between the same pair of vertices.

It is guaranteed that the given graph is a $d$-regular graph.

Output

Output a single line containing $n$ integers, which is a permutation of $1, \dots, n$, representing a perfect matching. If $p_i = j$, it means the edge between $x_i$ and $y_j$ is part of the matching.

Examples

Input 1

4 2
3 4
1 3
2 2
1 4

Output 1

4 3 2 1

Subtasks

For $30\%$ of the data, it is guaranteed that $n \times d \le 2 \times 10^5$.

For another $30\%$ of the data, it is guaranteed that $d$ is a power of $2$.

For $100\%$ of the data, it is guaranteed that $n \times d \le 2 \times 10^6$.