Nộp bài  Các bài nộp  Làm tốt nhất  Về danh sách bài 
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
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!
Được gửi lên bởi:  Race with time 
Ngày:  20101104 
Thời gian chạy:  1s 
Giới hạn mã nguồn:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Ngôn ngữ cho phép:  Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED 
Nguồn bài:  NEERC Southern Subregion 2003  2004 
hide comments
20150904 17:27:15 [Nghien] Le Long
splay tree rồi 

20101106 03:42:23 Race with time
Cam on thay a. Dung la co mot so test bi sai (Qi > n). Bo test da duoc sua lai. 

20101105 11:35:28 Lê Minh Hoàng
Trong các test cases có trường hợp Qi > n. Số n trong input bị sai? 