题目描述

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

• 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。

格式

输入格式

每组数据第一行为盒子个数 \(n\) 和指令条数 \(m\)，以下 \(m\) 行每行包含一条指令。

输出格式

每组数据输出一行，即所有奇数位置的盒子编号之和。格式注意样例。

样例1

输入样例1

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

输出样例1

Case 1: 12
Case 2: 9
Case 3: 2500050000

限制

时间：\(1s\) 空间：\(128M\)

对于 \(100\%\) 的数据：\(1<=n,m<=100,000\)

来源

地址:\(zloj,J2021\)域
作者：\(jialiang2509\)
模拟赛\(T3\)