Given $n$ points in $d$-dimensional space. The Hamming distance between two points is defined as the number of dimensions in which their coordinates differ. For each point, find an approximately nearest other point such that the distance to the found point is no more than 20 times the distance to the actual nearest point.

Input

The first line contains two integers $n$ and $d$. Following this are $n$ lines, where the $i$-th line contains $d$ integers, representing the $d$-dimensional coordinates of the point with index $i$.

Output

Output $n$ lines, where the $i$-th line contains one integer, the index of the approximately nearest point to the point with index $i$.

Constraints

$2 \le n \le 10\,000$, $1 \le d \le 100$.

Subtasks

The score for each test case is distributed equally among the $n$ points. That is, if $m$ of the approximately nearest points you provide meet the requirement, you will receive $m/n$ of the total score for that test case.

Note

• wtm_in.txt and wtm_ans.txt are provided as an example, where wtm_in.txt is the sample input and wtm_ans.txt is the answer file. The first line of the answer file contains $n$, and the subsequent lines indicate the Hamming distance between each point and its actual nearest point.
• wtm_check.cpp is a checker program, which can be used as follows:

g++ wtm_chck.cpp -o wtm_chk
./wtm_chk wtm_in.txt wtm_ans.txt wtm_out.txt

Where wtm_in.txt and wtm_ans.txt are as described above, and wtm_out.txt is the standard output of your program after reading wtm_in.txt. The first line of the output from wtm_chk contains a number in $[0, 1]$, representing the proportion of the score your output achieves.