不强制在线的动态快速排序

题目背景

曦月最近学会了快速排序,但是她很快地想到了,如果要动态地排序,那要怎么办呢?

题目描述

为了研究这个问题,曦月提出了一个十分简单的问题 曦月希望维护一个允许重复的集合$S$,支持: * 插入$[L, R]$,也就是插入$L, L + 1 ... , R$,这$R - L + 1$个数 * 询问$Sort(S)$ --- $Sort(S)$的定义为: 我们将集合$S$中的元素**从小到大按照快速排序**排好序,记为$a_1, a_2 ... a_n$ 那么,$Sort(S) = \bigoplus \limits_{i = 2}^n (a_i^2 - a_{i - 1}^2)$,其中$\bigoplus$表示异或和 关于异或的定义,请咨询度娘

输入输出格式

输入格式


第一行,一个数$q$ 后$q$行,或者是$1\;l\;r$,表示插入$[l, r]$,或者是$2$,表示一次询问

输出格式


对于每个询问,一行一个答案

输入输出样例

输入样例 #1

2
1 1 1
2

输出样例 #1

0

输入样例 #2

10
1 22 27
1 50 55
1 82 87
1 2 7
2
1 47 52
1 62 67
1 61 66
1 41 46
2

输出样例 #2

2515
2141

说明

对于样例一的解释: $S$中只有一个数,因此返回$0$ --- 对于$30$分的数据,$q \leqslant 100$ 对于$50$分的数据,$q \leqslant 5 * 10^4$ 对于另外的$20$分的数据,满足$L = R$ 对于$100$分的数据,$q \leqslant 3 * 10^5$,$1 \leqslant L \leqslant R \leqslant 10^9$ 保证数据有梯度,可能略微地有卡常,请把自己的常数优化到极致 也许你需要在代码前面加上这一句话,来手动开启$O2$~~(可能加了也没啥用)~~ ```cpp %:pragma GCC optimize(2) ```