Background

Xiyue recently learned quicksort, but she soon thought: if we need to sort dynamically, what should we do?

Problem Description

To study this problem, Xiyue proposed a very simple question.

Xiyue wants to maintain a multiset $S$ that allows duplicates, supporting:

• Insert $[L, R]$, i.e., insert $L, L + 1 ... , R$, these $R - L + 1$ numbers.

• Query $Sort(S)$.

The definition of $Sort(S)$ is:

We sort the elements in $S$ from small to large using quicksort, denoted as $a_1, a_2 ... a_n$.

Then, $Sort(S) = \bigoplus \limits_{i = 2}^n (a_i^2 - a_{i - 1}^2)$, where $\bigoplus$ denotes XOR.

For the definition of XOR, please consult Baidu.

Input Format

The first line contains an integer $q$.

The next $q$ lines are either $1\;l\;r$, meaning insert $[l, r]$, or $2$, meaning one query.

Output Format

For each query, output one line with one answer.

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

Hint

Explanation for Sample 1:

$S$ contains only one number, so return $0$.

Constraints:

For the $30$ points testdata, $q \leqslant 100$.

For the $50$ points testdata, $q \leqslant 5 * 10^4$.

For the other $20$ points testdata, $L = R$.

For the $100$ points testdata, $q \leqslant 3 * 10^5$, $1 \leqslant L \leqslant R \leqslant 10^9$.

The testdata is guaranteed to have gradients. It may be slightly sensitive to constants, so please optimize your constants as much as possible.

Translated by ChatGPT 5