No tags yet

No tag edit access

time limit per test: 0.25 sec.

memory limit per test: 4096 KB

memory limit per test: 4096 KB

input: standard input

output: standard output

output: standard output

A well-known sharper I*** invented a new way to swindle people. There are N thimbles on the table, and there is a small ball with the number under each of them. The balls are numbered with numbers from 1 to N from left to right. At one operation I*** changes the order of some subsequence of successive thimbles to the opposite. Your task is to find the order of numbers (from left to right) in sequence after all of his manipulations. The total number of manipulations is M.

The first line contains two integer numbers N and M (1<=N<=130000, 1<=M<=2000) separated by a space. Each of the following M lines contains two integer numbers Pi, Qi (1<=Pi<=Qi<=N) - positions of the leftmost and rightmost thimbles in rotated sequence.

Output the sequence of N numbers - the numbers of balls in the thimbles from left to right.

Input

Test #1

5 2

1 3

4 5

Test #2

5 2

1 4

2 5

5 2

1 3

4 5

Test #2

5 2

1 4

2 5

Output

Test #1

3 2 1 5 4

Test #2

4 5 1 2 3

3 2 1 5 4

Test #2

4 5 1 2 3

Author: | Michael R. Mirzayanov |

Resource: | ACM International Collegiate Programming Contest 2003-2004 North-Eastern European Region, Southern Subregion |

Date: | 2003 October, 9 |

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/10/2020 02:36:26 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|