UVa-12657 Boxes in a Line

https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=4395

You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4

kinds of commands:

• 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y )

• 2 X Y : move box X to the right to Y (ignore this if X is already the right of Y )

• 3 X Y : swap box X and Y

• 4: reverse the whole line.

Commands are guaranteed to be valid, i.e. X will be not equal to Y .

For example, if n = 6, after executing 1 1 4, the line becomes 2 3 1 4 5 6. Then after executing 2 3 5, the line becomes 2 1 4 5 3 6. Then after executing 3 1 6, the line becomes 2 6 4 5 3 1.

Then after executing 4, then line becomes 1 3 5 4 6 2

Input

There will be at most 10 test cases. Each test case begins with a line containing 2 integers n, m (1 ≤ n, m ≤ 100, 000). Each of the following m lines contain a command.

Output

For each test case, print the sum of numbers at odd-indexed positions. Positions are numbered 1 to n from left to right.

Sample Input

6 4

1 1 4

2 3 5

3 1 6

6 3

1 1 4

2 3 5

3 1 6

100000 1

Sample Output

Case 1: 12

Case 2: 9

Case 3: 2500050000

解題策略

雙向循環鏈結串列

新增節點0表示鏈結串列的head，節點1到節點n的雙向循環鏈結串列，索引值表示數值

R[0]出發可以找到順向的所有節點

L[0]出發可以找到逆向的所有節點