1146 : 一行盒子

Description

你有一行盒子，从左到右依次编号为1, 2, 3,…, n。你可以执行四种指令：

• 1 X Y表示把盒子X移动到盒子Y左边（如果X已经在Y的左边则忽略此指令）。
• 2 X Y表示把盒子X移动到盒子Y右边（如果X已经在Y的右边则忽略此指令）。
• 3 X Y表示交换盒子X和Y的位置。
• 4 表示反转整条链。

指令保证合法，即X不等于Y。例如，当n=6时在初始状态下执行1 1 4后，盒子序列为2 3 1 4 5 6。接下来执行2 3 5，盒子序列变成2 1 4 5 3 6。再执行3 1 6，得到2 6 4 5 3 1。最终执行4，得到1 3 5 4 6 2。

Input

输入包含不超过10组数据，每组数据第一行为盒子个数n和指令条数m（1<=n,m<=100,000），以下m行每行包含一条指令。

Output

每组数据输出一行，即所有奇数位置的盒子编号之和。位置从左到右编号为1~n。

Sample

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

Hint

Source

Author

SRbGa