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.
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
Ai and
Bi (-10
9≤
Ai,
Bi≤ 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
|