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
A_{i} and
B_{i}. These numbers mean that all numbers
X belong to the
ith progression if
X =
A_{i}*
K+
B_{i} for some nonnegative 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≤ 10
^{9}). Each of the following
N lines contains the pair of numbers
A_{i} and
B_{i} (10
^{9}≤
A_{i},
B_{i}≤ 10
^{9}).
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.
Example(s)
sample input

sample output

5 6
1 1
2 1
3 1
3 1
6 4

2 3 1 6 4
