TWIST  Twist and whirl  want to cheat
English  Vietnamese 
A wellknown 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 test(s)
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
Note: A naive solution would result in TLE. Have fun! :D
hide comments
Dusan Zivanovic:
20160512 12:58:03
Don't be confused by the sample tests. Test #1 and Test #2 are separate test cases


Buda IM (retired):
20120508 17:31:28
Block array O( n sqrt n ) can pass the time limit. 

Badr:
20110302 23:32:19
it seems that test data is not fixed .. im getting WA and im sure of my code 

Race with time:
20101106 03:39:12
There was an error on test data. Apology for this. All fixed now. 
Added by:  Race with time 
Date:  20101104 
Time limit:  0.460s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  NEERC Southern Subregion 2003  2004 