In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
As usual winter has surprised the Byteburg city's work crews. There was a blizzard and the main road requires urgent plowing.
The responsibility is on the Department of Disaster Management, equipped with plows numbered to . Each plow is associated with a connected fragment of the main road. Two fragments may intersect, however no fragment is contained in another one. The fragments do not have to cover the whole road (the road may consist also of tunnels, which clearly do not need to be plowed).
Unfortunately a strike of all the snow plow men is right about to begin. The head of the Department of Disaster Management convinced only one snow plow man not to take part in the strike. For this reason the only working snow plow man is assigned to handle all the plows. Now it is the time to determine the order in which the plows are going to be used. The Department of Disaster Management ordered the snow plow man to always select a plow, which has the least total length of yet unplowed parts of the fragment associated with it (after plowing a part of the road it is considered to be plowed till the end of the process). In case of a tie the snow plow man should select the plow of minimum number.
The first line of the input contains two integers and (, ), denoting the length of the road and the number of plows. The following lines describe subsequent plows, in the order of increasing numbers. The -th of those lines contains two integers , (), meaning that the fragment of the road associated with the -th plow starts at and ends at . You may assume that , i.e. the plows are sorted according to the leftmost point of the associated fragment of the road. Furthermore no fragment is contained in a fragment associated with another plow.
Your program should output the numbers of plows in the order they shall be used. The output should consist of lines, each containing a single integer.
For the input data:
15 4 1 6 3 7 6 11 10 14
the correct result is:
2 1 3 4