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.
Input
The first line of the input contains two integer numbers N and M (1≤ N≤ 300; N≤ M≤ 109). Each of the following N lines contains the pair of numbers Ai and Bi (-109≤ Ai, Bi≤ 109).
Output
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.