赌神AZY

题目描述

不知道你们看过赌神没有？

AZY为了成为千王之王，便向赌神高进拜师学艺，然而他必须先学会基本的扑克洗牌才有那么点希望。

现在桌子上有一排扑克，从左到右点数依次为1.....n（假设点数可以无限增长），对这些牌有以下操作：

• 1 X Y表示将X牌移动到Y牌的左边（如果X已经在Y左边则无视该操作）
• 2 X Y表示将X移动到Y的右边（如果X已经在Y右边则无视该操作）
• 3 X Y表示交换X和Y的位置
• 4 表示将全部这排扑克反转

保证操作合法，X不等于Y。以上X,Y代表点数。左边右边表示相邻的左右位置。

输入

多组数据（不超过20组），每组数据第一行为牌的个数n，和操作个数m，1<=n<=1000010, 0=<m<=100

接下来m行，每行一个操作。

输出

每组数据输出一行，为操作结束后所有奇数位置的牌的点数之和。位置序号从左到右设为1~n.

输入样例

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

输出样例

12

Warning

本题不强求具体做法，只是说明链表不一定是指针实现的。其实数据很弱的Orz