题目描述

有 $n$ 个单调栈，每个栈中的元素均严格单调递减。

向某个单调栈中加入一个数 $x$ 时，需要先将栈顶所有小于等于 $x$ 的元素全部弹出，再把 $x$ 压入栈中。

现在需要执行以下操作：

1. 1 l r x：向编号位于区间 $[l,r]$ 内的每个单调栈中加入数 $x$。
2. 2 x：查询第 $x$ 个单调栈中所有元素的权值之和。
3. 3 x：弹出第 $x$ 个单调栈的栈顶元素；若该栈为空，则不进行任何操作。
4. 4 x：这是一次查询操作，并保证 $x\ne n$。将第 $n$ 个单调栈中的元素依次真正弹出。每弹出一个数 $a$，查询：如果把 $a$ 加入第 $x$ 个单调栈中（仅模拟，不真正加入），需要弹出多少个元素，并将该数量记作本次贡献。第 $n$ 个单调栈被全部弹空后，输出所有贡献的按位异或和。

落尘需要执行 $m$ 次操作。对于每次查询操作，请输出对应答案。

全部操作结束后，还需要输出所有单调栈内元素的权值总和。

部分测试数据强制在线。

输入格式

第一行输入三个整数 $n,m,t$。

接下来 $m$ 行，每行首先输入一个整数 $tp$，表示操作类型，再按照题目描述输入该操作所需的参数。

当 $t=1$ 时，输入中的 $x$ 需要与上一次查询操作的答案进行按位异或；若此前尚未发生查询，则不进行异或。

输出格式

对于每次查询操作，输出一行一个整数。

全部操作完成后，再输出所有单调栈中元素的权值总和。

样例输入

8 9 0
1 1 3 5
1 1 3 2
1 4 8 3
4 1
1 4 8 8
1 4 8 4
4 2
3 5
2 5

样例输出

1
3
8
65

数据范围

对于全部数据：

• $n,m\le 10^5$；
• 任意时刻，任意单调栈中的元素 $x$ 均满足 $0\le x\le 10^9$。