1463: 移动盒子

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:6 Solved:4

Description

给定n个盒子,分别标号为1~n(即位置从左到右编号为1~n)。现有下面4种操作:

1  x  y 表示将x移到y的左边;

2  x  y 表示将x移到Y的右边;

3  x  y 表示交换x与y的位置;

4       表示将1~n所有的盒子反序。

现要你求经过m次操作之后,求所有奇数位置的盒子标号之和。

Input

第一行为盒子个数n和指令条数m1<=n,m<=100000,以下m行每行包含一条指令。

Output

输出一行,即所有奇数位置的盒子编号之和。

Sample Input Copy

6  4
1  1  4
2  3  5
3  1  6
4

Sample Output Copy

12

HINT

【样例输入2】

6  3

1  1  4

2  3  5

3  1  6

【样例输出2】

9