Description

一行有$n$个盒子，从左到右编号为$1～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

最多有$10$个测试用例。每个测试用例的第$1$行都包含两个整数$n$和$m$$（1≤n , m ≤100 000）$，下面的$m$行，每行都包含一个命令。

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