Artem is a fan of Yekaterinburg Metro. He is now renovating his room. According
to his design, one of the walls of the room will be covered with white
wallpaper and a green straight line will stretch across the wall from left to
right. This line will remind him of the only metro line in Yekaterinburg.
Artem has prepared n wallpaper strips and drawn a green line on each strip
from its left edge to its right edge. In which order should he put these strips
onto the wall so that the green lines form one segment of a straight line
stretching from the left edge of the wall to its right edge?
For each strip the distance from its lower edge to the left and right endpoints
of the segment drawn on it is known. All the strips are of the same width and
their height is equal to the height of the wall. The strips may be turned
upside down before being pasted to the wall.
Input
The first line contains integers h and n (1 ≤ h ≤ 100000;
1 ≤ n ≤ 50000), which are the height of Artem's room and the number of
prepared wallpaper strips. The i-th of the following n lines contains
integers l and r (0 ≤ l, r ≤ h), which are the distances from the lower edge of the strip to the left and right endpoints of the green segment drawn on it.
Output
Output n integers separated with a space. These should be numbers
of the strips as they should be pasted to the wall from left to right. If a
strip should be turned upside down before pasting, then its number should be
preceded with a minus. The strips are numbered from 1 to n as they are given
in the input. If there are several possible answers, output any of them. If it
is impossible to put the wallpaper as required, output “0”.
Samples
input | output |
---|
5 3
3 2
2 1
2 1
| -3 1 2
|
5 3
3 2
2 1
3 2
| 0
|
Problem Author: Alexander Ipatov (prepared by Marina Mukhacheva)
Problem Source: The 14th Urals Collegiate Programing Championship, April 10, 2010