Problem 1077 --妹妹与食堂

1077: 妹妹与食堂

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 123  Solved: 20
[Submit][Status][Web Board][Creator:]

Description

在这个由妹妹组成的城市的中心,有一家妹妹食堂,每个从食堂出来的妹妹都皱着眉头。

负责盛饭的妹妹10086号永远也不知道当前服务的妹妹需要多少粒米饭,负责吃饭的妹妹吃得很不开心。由于妹妹数量众多,而且长得都一样,靠人力记住妹妹的信息基本是不可能的。

程序员妹妹95533号注意到了这种情况,决定做些什么来应对当前的局面。首先,她为这个城市所有的妹妹制定了一个编号,从1-N依次递增。然后,将每个妹妹一次需要吃多少粒米饭录入了数据库。接着,95533开发出了一台机器,对于每个编号,都能立即回答该编号对应的妹妹需要多少粒米饭。

情况有所好转。但是10086号现在感到十分苦恼,虽然她能知道每个妹妹需要多少粒米,但是估计要打多少米是个困难的事情,她希望每次盛饭的时候能有一个参照。因此,10086向95533提出了一个请求。在任意时刻,希望机器能告诉她,当前排队的所有妹妹中,需求数量最多的妹妹和最少的妹妹的需求量是多少。这样她可以使用机器预先将最多的需求量和最少的需求量先精确盛出作为参照,同时这些参照也不会浪费。

妹妹们都很懂礼貌,从来不会插队。每当一个妹妹加入队列时,会通过脑电波告诉机器自己的编号。离开时,10086会告诉机器离开的妹妹的编号。 

现在,每个妹妹都很开心。

Input

第一行两个整数N, M。分别表示妹妹的数量和进队离队操作的次数。

第二行有N个整数,第i个整数表示妹妹i需要的米饭的数量。

接下来M行,首先是一个整数q,若q为1,则后面跟着一个整数id,表示该id对应的妹妹加入了队列。若q为2,则表示当前队首位置的妹妹拿走了自己的饭离开了队伍。


1 <= n, m <= 3000000

1 <= id <= n

x <= 1000000000


Output

对于每个入队操作,10086号需要知道当前队伍中妹妹需要的最多的饭和最少的饭。

对于每个出队操作,10086号需要知道准备离开的妹妹需要多少饭。

95533已经知道该怎么做了,所以你不需要输出每一个结果,你只需要输出所有结果的异或和。这样95533只需要比较她答案的异或和与你答案的异或和就可以了。

Sample Input

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

Sample Output

6

HINT


2 2
2 3
2 4
2
3

出题人保证每个出队操作都是合法的。

Source

[Submit][Status]