The exhibition of arithmetical progressions will be opened in Berland soon. Each of N presented progressions is characterized by two integer numbers A_i and B_i. These numbers mean that all numbers X belong to the i-th progression if X = A_i*K+B_i 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; N≤ M≤ 10⁹). Each of the following N lines contains the pair of numbers A_i and B_i (-10⁹≤ A_i, B_i≤ 10⁹).

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