ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

K. Metro to Every Home

Time limit: 1.0 second
Memory limit: 64 MB
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.
Problem illustration

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, rh), 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

inputoutput
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
To submit the solution for this problem go to the Problem set: 1773. Metro to Every Home