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.

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 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”.