Snowstorm

Time limit1sMemory limit128 MB

Summary

Simulate plows clearing road intervals in order of smallest remaining uncovered length and print the clearing order.

Level: Medium6 of 10
Topics: Intervals, Simulation, Heap, Sorting
Solved: No attempts yet

Problem

A snowstorm hit the main road. There are $m$ plows; plow $i$ covers interval $[a_i, b_i]$ . Intervals may overlap but none lies entirely inside another. They need not cover the whole road.

One operator runs every plow. Each time, pick the plow whose assigned interval still has the least uncovered length. Tie-break by smaller index. A road point needs clearing only once.

Input

Line 1: $n$ , $m$ . Next $m$ lines: $a_i$ , $b_i$ with increasing $a_i$ .

Output

Print $m$ lines: plow numbers in clearing order.

Examples1

Example 1
Input
```
15 4
1 6
3 7
6 11
10 14
```
Expected output
```
2
1
3
4
```