[HDU-3487]Play with Chain

F - Play with Chain

Time Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%I64d
& %I64u


YaoYao is fond of playing his chains. He has a chain containing n diamonds on it. Diamonds are numbered from 1 to n. 
At first, the diamonds on the chain is a sequence: 1, 2, 3, …, n. 
He will perform two types of operations: 
CUT a b c: He will first cut down the chain from the ath diamond to the
bth diamond. And then insert it after the cth diamond on the remaining
For example, if n=8, the chain is: 1 2 3 4 5 6 7 8; We perform “CUT 3 5
4”, Then we first cut down 3 4 5, and the remaining chain would be: 1 2 6
7 8. Then we insert “3 4 5” into the chain before 5th diamond, the
chain turns out to be: 1 2 6 7 3 4 5 8. 

FLIP a b: We first cut down the chain from the ath diamond to the bth
diamond. Then reverse the chain and put them back to the original
For example, if we perform “FLIP 2 6” on the chain: 1 2 6 7 3 4 5 8. The chain will turn out to be: 1 4 3 7 6 2 5 8 

He wants to know what the chain looks like after perform m operations. Could you help him? 



There will be multiple test cases in a test data. 
For each test case, the first line contains two numbers: n and m (1≤n,
m≤3*100000), indicating the total number of diamonds on the chain and
the number of operations respectively. 
Then m lines follow, each line contains one operation. The command is like this: 
CUT a b c // Means a CUT operation, 1 ≤ a ≤ b ≤ n, 0≤ c ≤ n-(b-a+1). 
FLIP a b    // Means a FLIP operation, 1 ≤ a < b ≤ n. 
The input ends up with two negative numbers, which should not be processed as a case. 


For each test case, you should print a line with n numbers. The ith number is the number of the ith diamond on the chain.

Sample Input


Sample Output



You May Also Like

About the Author: zhuyeye