F. MEX Queries

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a set of integer numbers, initially it is empty. You should perform n queries.

There are three different types of queries:

• 1 l r — Add all missing numbers from the interval [l, r]
• 2 l r — Remove all present numbers from the interval [l, r]
• 3 l r — Invert the interval [l, r] — add all missing and remove all present numbers from the interval [l, r]

After each query you should output MEX of the set — the smallest positive (MEX  ≥ 1) integer number which is not presented in the set.

Input

The first line contains one integer number n (1 ≤ n ≤ 105).

Next n lines contain three integer numbers t, l, r (1 ≤ t ≤ 3, 1 ≤ l ≤ r ≤ 1018) — type of the query, left and right bounds.

Output

Print MEX of the set after each query.

Examples

input

3 1 3 4 3 1 6 2 1 3

output

1 3 1

input

4 1 1 3 3 5 6 2 4 4 3 1 6

output

4 4 4 1

Note

Here are contents of the set after each query in the first example:

1. {3, 4} — the interval [3, 4] is added
2. {1, 2, 5, 6} — numbers {3, 4} from the interval [1, 6] got deleted and all the others are added
3. {5, 6} — numbers {1, 2} got deleted

 

题意：给你n个区间，1操作表示把[l,r]赋值为1，2操作表示把[l,r]赋值为0，3操作表示把[l,r]异或1；

　　   求第一个不为0的正整数。

思路：对于所有区间[l,r]取出l，r，r+1三个点；

　　　离散化放入线段树中去

　　　现在需要区间修改，区间异或，查询

　　　需要两个lazy标记，一个存修改的值，一个存是否异或1.

　　　区间查询log查找即可，详见代码。

　　　小trick：需要加入最小值，即是1的情况；

#pragma comment(linker, "/STACK:1024000000,1024000000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include