测试数据来自 system/2424

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　你有一行盒子，从左到右依次编号为 \(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 2 3 4 5 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。

【输入格式】

　　输入包含不超过10组数据，每组数据第一行为盒子数 \(n\) 和指令 \(m\)，以下 \(m\) 行每行包含一条指令。

【输出格式】

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

【输入输出样例】

　Input

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

　Output

12
9
2500050000

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤n,m≤100000\)。

【来源】

　　Mr.he