Background

Xi Yue has recently learned about quick sort, but she quickly thought of how to dynamically sort if needed.

Problem Description

To study this issue, Xi Yue proposed a very simple problem.

Xi Yue wants to maintain a collection \( S \) that allows duplicates and supports:

• Inserting the interval \([L, R]\), which means inserting the numbers \( L, L + 1, \ldots, R \), a total of \( R - L + 1 \) numbers.
• Querying \( Sort(S) \).

The definition of \( Sort(S) \) is:

We sort the elements in the collection \( S \) in ascending order using quick sort, denoted as \( a_1, a_2, \ldots, a_n \).

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

For the definition of XOR, please refer to relevant sources.

Input Format

The first line contains a number \( q \).

The next \( q \) lines are either \( 1 \ l \ r \), indicating an insertion of the interval \([l, r]\), or \( 2 \), indicating a query.

Output Format

For each query, output one line with the answer.

Sample Input and Output

Sample Input #1

2
1 1 1
2

Sample Output #1

0

Sample Input #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

Sample Output #2

2515
2141

Notes

For the explanation of Sample #1:

\( S \) contains only one number, so the result is \( 0 \).

For 30% of the data, \( q \leq 100 \).

For 50% of the data, \( q \leq 5 \times 10^4 \).

For another 20% of the data, \( L = R \).

For 100% of the data, \( q \leq 3 \times 10^5 \), \( 1 \leq L \leq R \leq 10^9 \).

The data is designed with a gradient and may slightly challenge the efficiency of the solution, so optimize your constants to the maximum.

见题面 Input 部分

见题面 Output 部分