Indian Computing Olympiad Archives 2011

Related:

Zonal Computing Olympiad 2011, 4 Dec 2010

2:00 pm–5:00 pm IST

Problem 1 : Suitcase swappers

Tπ, the all new international terminal at Siruseri's international airport, has recently been opened for service. One of its marvels is its baggage delivery system.

There are N conveyor belts that run in parallel from the plane's parking position into the building, carrying bags from the plane to the baggage delivery hall. The loaders place one bag on each of these N belts at the plane and these bags move along the belt at the same rate and eventually emerge in the baggage hall at the same time.

Unfortunately, there are some mischievous monkeys who have sneaked into the airport and positioned themselves in between some of the conveyor belts. When a monkey sees bags pass by on the two belts on either side of it, it swaps the bags. As a result, the order in which the bags reach the end of the line is different from the order in which they were placed originally. That is, if b_j is the bag that was originally placed on conveyor belt j, it may arrive at the other end on a different belt k, where k ≠ j.

There are a number of such monkeys positioned at various places along the route. Each monkey swaps bags between a pair of adjacent belts, but no two monkeys are at the same distance along the route from the plane to the baggage hall.

Here is picture showing 5 conveyor belts and 5 monkeys positioned along the route, and the effect that they have on the flow of the bags. The belts move from left to right. The monkeys are M1, M2, M3, M4 and M5, located at distances 10, 20, 30, 40 and 50, respectively. Monkey M1 swaps bags 2 and 3. Monkey M2 swaps bags 4 and 5. Monkey M3 swaps bags 1 and 3. Monkey M4 swaps bags 2 and 5 and Monkey M5 swaps the same two bags back.

You will be given information about the locations of the monkeys along the conveyor belts. Assume that the bags placed on the N belts are originally numbered 1,2,…,N, with bag j placed on belt j. Your task is to compute the order of the bags in the output. For instance, in the example above, the final order of the bags is 3 1 2 5 4.

Input format

The first line of input contains two integers N and M, where N is the number of conveyor belts and M is the number of monkeys. The next M lines describe the location of the monkeys. Each of the lines has two integers D and B where D is the distance in metres of the monkey from the start of the belts and 1 ≤ B ≤ N-1 is a belt number, indicating that this monkey is standing between belts B and B+1. The monkeys need not be listed in the same order as their distance from the start of the belts.

Output format

A single line with N numbers, describing the order in which bags 1,2,…N emerge in the baggage hall.

Testdata

You may assume that 1 ≤ M ≤ 1000, 1 ≤ N ≤ 20000 and for each monkey, its distance D is is in the range [1,10⁹]. No two monkeys are located at the same distance D.

Sample Input

Sample Output

3 1 2 5 4

Time and memory limits

The time limit for this task is 1 second. The memory limit is 32MB.