305. Exhibition

Time limit per test: 0.75 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

The exhibition of arithmetical progressions will be opened in Berland soon. Each of N presented progressions is characterized by two integer numbers Ai and Bi. These numbers mean that all numbers X belong to the i-th progression if X = Ai*K+Bi for some non-negative integer K. Organizers decided that each sequence will be given a unique number from 1 to M. The organizers want as much as possible progressions to be assigned such a number, that would be a member of this progression. They hired you to do this job.

The first line of the input contains two integer numbers N and M (1≤ N≤ 300; NM≤ 109). Each of the following N lines contains the pair of numbers Ai and Bi (-109Ai, Bi≤ 109).

Write to the output distribution of numbers among sequences — N numbers delimited by spaces. All numbers should be unique. If there are several solutions output any of them.

sample input
sample output
5 6
1 1
2 1
3 1
3 1
6 4
2 3 1 6 4