mex and Queries

Time limit2sMemory limit512 MB

Summary

Maintain a set of natural numbers under range add, range remove, and range toggle queries, then output the mex after each of up to 100000 queries with values up to 1e18.

Level: Hard9 of 10
Topics: Segment tree, Intervals, Implementation
Solved: No attempts yet

Problem

mex is the function that finds the smallest natural number not contained in a sequence. For example, mex([1,2,3]) = 4, mex([5,3,1,1,4]) = 2, and mex([1,5,2,1,5,2,1,2]) = 3.

Given an empty array A and N queries, perform the queries. There are 3 types of queries, as follows.

1 l r: Add every natural number in the interval [l, r] to array A. A natural number that is already in the array is not added again.
2 l r: Remove every natural number in the interval [l, r] from array A.
3 l r: For every natural number x in the interval [l, r], do the following.
- If x is in array A, remove it from the array.
- If x is not in array A, add it to the array.

After performing each query, find mex(A).

Input

The first line gives the number of queries N (1 ≤ N ≤ 100,000). Each of the next N lines gives a query q, l, r (1 ≤ q ≤ 3, 1 ≤ l ≤ r ≤ 1018).

Output

After performing each query, output mex(A).

Examples2

Example 1
Input
```
3
1 3 4
3 1 6
2 1 3
```
Expected output
```
1
3
1
```
Example 2
Input
```
4
1 1 3
3 5 6
2 4 4
3 1 6
```
Expected output
```
4
4
4
1
```