TWIST - Twist and whirl - want to cheat

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.

Input

The first line contains two integer numbers N and M (1 <= N <= 100000, 1 <= M <= 100000) 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

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

Sample

Input
5 2
1 3
4 5

Output
3 2 1 5 4
Input
5 2
1 4
2 5

Output
4 5 1 2 3

Note: A naive solution would result in TLE. Have fun!


Added by:Race with time
Date:2010-11-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:NEERC Southern Subregion 2003 - 2004

hide comments
2021-10-04 03:58:32
implicit Treap
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.