/如果你觉得题目描述中废话太多，可以从第十段开始看。/
    第一段。这里似乎该写几个字来着。。。。。。。。。。。字字字字字字字字字字字字字字字字。
    第二段。字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字。
    第三段。字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字。
    第四段。字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字。
    第五段。好累啊，少打几个字。。。字字字字字字字字字字字字字字字字。
    第六段。字字字字字字字字字字字字字字字字。
    第七段。字字字字字字字字字字字字字字字字。
    第八段。字字字字字字字字字字字字字字字字。
    第九段。居然已经到第九段了，我还是多打几个字吧。。。字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字字。
    第十段。按照量子力学的观点，一切事件都是以概率的形式发生，比如粒子的运动、能量的转换、信息的传递等等。从宏观上来看，将来会发生的事情都只能以概率来描述，比如几秒钟后你有一定的可能性选择做这道题、有一定的可能性选择关电脑、有一定的可能性选择开始打游戏……我们把这些事件按照先后关系联系起来，就形成了一个有向无环的网状结构，比如下面这张图描述了早上醒来到起床之间可能会发生的部分事件之间的关系，“A→B”表示A发生后B可能会发生，每个事件发生后接下来发生什么事情是按照一定的概率进行选择的。

    那么假设在一个时空分支中你醒了，事件按照“不睁眼→从床上掉下来→起床”这样的顺序发生了；但是在另一个时空分支里，事件按照“不睁眼→睁眼→赖在床上不起来→起床”这样的顺序发生了，那么这两个时空分支就被称为是相互独立的平行时空。显然任何时刻我们都只能处于唯一一个时空分支中，否则你可能会看到各种乱七八糟的景象，比图起床后正在刷牙的你和起床后正在搬砖的你打了起来，这显然是荒谬的。
    不过，现在有一群猴子就处于这样的混乱的时空中，它们那里经常发生这样的事情：处于一个时空分支的一群猴子A与处于另一个时空分支的一群猴子B（注意可能有部分猴子是相同的，也可能它们本就是同于群猴子）打了起来。既然要打架，当然是能者多劳，于是A群派出了他们中最强壮的一只猴子，B群也同样，两只猴子打了一架，于是较强的一只所属的猴群获胜，较弱的失败，且这两只猴子的战斗力都将会减小一半（除以2向下取整）；特别的，如果派出的这两只猴子战斗力相等，那么它们会直接握手言和而不打架。每次打架之后这两个猴群就会融为一体成为一个新的猴群C，而由于事件已经按照这个顺序发生，所以新猴群不再属于原来的那两个时空分支的任意一个，而是属于一个新的时空分支。注意：在此之后猴群A和猴群B仍然存在于各自的时空分支，以后有可能还会与别的猴群打架。
    打架总是很消耗体力的，恰好有时会有一些补给品出现在某个时空分支，每一份补给品可以给一只猴子增加1个单位的强壮值。这个时空分支的猴群都会去争抢这些补给品，而往往只有一只猴子能够抢到补给——最强壮的一只。注意，即使有超过一只猴子同时最强壮，补给品也会被其中一只抢走。原因很简单，当某一只猴子抢到了第一份补给品，它的强壮值立即增加一个单位，于是其他的猴子就抢不过它了。同样的，由于补给事件已经发生，所以新的猴群已经不再是原来的猴群了，他们属于一个新的时空分支。
    如此混乱的时空，就需要一个优秀的程序员来进行管理和记录。可惜猴子都很任性，所以管理是没希望了，程序员只有记录的份。一开始有n个时空分支（编号1,2,...,n），每个时空分支里有一个由一只猴子组成的猴群（第i个时空分支里的猴群记为S_i）。接下来发生了m次事件，分为打架事件和补给事件两种。如果第k个事件是打架事件，那么第i个时空分支中的猴群S_i与第j个时空分支中的猴群S_j发生了冲突要打架，打架后合并得到的新猴群为S_n+k，处于第n+k个时空分支，保证1<=i,j<=n+k-1。如果第k个事件是补给事件，那么第i个时空分支中出现了j份补给品，猴群S_i的猴子获得补给，新的猴群S_n+k处于第n+k个时空分支，同样保证1<=i<=n+k-1。
    现在问题来了——每次打架，你要说出派出的两只猴子打架前的强壮值分别是多少；每次补给，你要说出得到补给的猴子在变得更强壮之前强壮值是多少。题目会采取措施强制在线。

简化版题意

$n$群猴子$k$次事件，强制在线：

• 打架事件：两群猴子各选最强的一只，如果这两只战斗力不相等就会减半。打完架合并为另一个平行时空的一群猴子，而原来两群仍然存在且保持不变。
• 补给事件：某群猴子最强的一只战斗力增加。

第一行两个数n,m，表示一开始的猴群数量和事件数量。
第二行n个正整数，第i个数表示猴群S_i的那一只猴子的强壮值。
接下来m行，每行三个整数op,i',j'，表示一个事件：
·若op=1，表示发生了一次打架事件。
·若op=2，表示发生了一次补给事件。
对于每次事件，设上一次事件的输出是lastans（一开始lastans=0），则真正的i = i' xor lastans; j = j' xor lastans.

每次事件，输出答案。

样例解释：
解密后的输入数据是这样的：
1 8
10
2 1 10
1 1 2
1 1 3
2 4 5
1 3 5
2 6 8
2 6 6
1 7 8
一开始，S₁={10}, lastans=0;
第一个事件输出10，然后S₂={20}, lastans=10;
第二个事件输出10 20，然后S₃={10,5}, lastans=20;
第三个事件输出10 10，然后S₄={10,10,5}, lastans=10;
第四个事件输出10，然后S₅={15,10,5}, lastans=10;
第五个事件输出10 15，然后S₆={10,7,5,5,5}, lastans=15;
第六个事件输出10，然后S₇={18,7,5,5,5}, lastans=10;
第七个事件输出10，然后S₈={16,7,5,5,5}, lastans=10;
第八个事件输出18 16，然后S₉={9,8,7,7,5,5,5,5,5,5}, lastans=16;

数据范围：
1<=n<=100000
1<=m<=100000
保证每个时空分支中不超过2¹⁰⁰个猴子（其实可能略大于2¹⁰⁰，生成数据是用double记录每群猴子的个数，精度你懂的）
每个猴子的战斗力始终不超过10⁹。