题目背景

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

题目描述

为了研究这个问题，曦月提出了一个十分简单的问题

曦月希望维护一个允许重复的集合 $S$，支持：

• 插入 $[L, R]$，也就是插入 $L, L + 1 ... , R$，这 $R - L + 1$ 个数

• 询问 $\mathrm{Sort}(S)$

---

$\mathrm{Sort}(S)$ 的定义为：

我们将集合 $S$ 中的元素从小到大按照快速排序排好序，记为 $a_1, a_2 ... a_n$

那么，$\mathrm{Sort} = \bigoplus \limits_{i = 2}^n (a_i^2 - a_{i - 1}^2)$，其中$\bigoplus$表示异或和

关于异或的定义，请咨询度娘

输入格式

第一行，一个数 $q$

后 $q$ 行，或者是 1 l r，表示插入$[l, r]$，或者是 2，表示一次询问

输出格式

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

2
1 1 1
2

0

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

2515
2141

提示

对于样例一的解释：

$S$ 中只有一个数，因此返回 $0$

---

对于 $30$ 分的数据，$q \leqslant 100$

对于 $50$ 分的数据，$q \leqslant 5 \times 10^4$

对于另外 $20$ 分的数据，满足$L = R$

对于 $100$ 分的数据，$q \leqslant 3 \times 10^5$，$1 \leqslant L \leqslant R \leqslant 10^9$

保证数据有梯度，可能略微地有卡常，请把自己的常数优化到极致