#2400. 移动盒子

移动盒子

Description

一行有nn个盒子,从左到右编号为1n1~n。模拟以下4种命令。

• 1 X Y :将盒子X 移动到Y 的左侧(如果X 已经在Y 的左侧,则忽略此项)。

• 2 X Y :将盒子X 移动到Y 的右侧(如果X 已经在Y 的右侧,则忽略此项)。

• 3 X Y :交换盒子X 和Y 的位置。

• 4:翻转整行盒子序列。

以上命令保证有效,即X 不等于Y 。举例说明:有6个盒子,执行1 1 4,即1移动到4的左侧,变成2 3 1 4 5 6。然后执行2 3 5,即3移动到5的右侧,变成2 1 4 5 3 6。接着执行3 1 6,即交换1和6的位置,变成2 6 4 5 3 1。最后执行4,即翻转整行序列,变成1 3 5 4 6 2。

Format

Input

最多有1010个测试用例。每个测试用例的第11行都包含两个整数nn mm1n,m100000(1≤n , m ≤100 000),下面的mm行,每行都包含一个命令。

Output

对于每个测试用例,都单行输出奇数索引位置的数字总和。

Samples

6 4
1 1 4
2 3 5
3 1 6
4
6 3
1 1 4
2 3 5
3 1 6
100000 1
4
Case 1: 12
Case 2: 9
Case 3: 2500050000

来源

UVA12657