Example

Sample input 1

5 3
1 0
2 0
3 0
4 0
5 0

Sample output 1

1 2 3 1 2

Sample input 2

4 2
0 5
5 0
5 5
0 0

Sample output 2

1 1 2 2