Problem: 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 

Solution (in JAVA):

Solution:
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
What do you think? What do you think?
1st on Billboard, what do you think of it
Next is a Grammy, what do you think of it
However you think, I’m sorry, but shit, I have no fcking interest
*******************************
I'm standing on top of my Monopoly board
That means I'm on top of my game and it don't stop
til my hip don't hop anymore
https://www.a2oj.com/Ladder16.html
*******************************
300iq as writer = Sad!
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x817F3
   {
      static HashMap<Integer, Long> answer = new HashMap<Integer, Long>();
      public static void main(String hi[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(infile.readLine());
         StringBuilder sb = new StringBuilder();
         int T = Integer.parseInt(st.nextToken());
         long[][] vals = new long[T][3];
         for(int i=0; i < T; i++)
         {
            st = new StringTokenizer(infile.readLine());
            int a = Integer.parseInt(st.nextToken());
            long b = Long.parseLong(st.nextToken());
            long c = Long.parseLong(st.nextToken());
            vals[i][0] = a;
            vals[i][1] = b;
            vals[i][2] = c;
         }
         //mex after each query is either L or R+1
         //L can be turned off in a query
         //everything <= R can be turned on (leaves R+1)
         Thing[] updates = compress(vals);
         LazySegTree segtree = new LazySegTree(answer.size()+1);
         for(int qw=0; qw < T; qw++)
         {
            int type = updates[qw].type;
            int L = updates[qw].left;
            int R = updates[qw].right;
            segtree.update(L, R-1, type);
            int low = 0;
            int high = answer.size()-1;
            while(low != high)
            {
               int mid = (low+high)/2;
               if(segtree.query(0, mid) == mid+1)
                  low = mid+1;
               else
                  high = mid;
            }
            /*
            //debug
            for(int i=0; i < answer.size(); i++)
               System.out.print(segtree.query(i,i)+" ");
            System.out.println();*/
            sb.append(answer.get(low)+"\n");
         }
         System.out.print(sb);
      }
      public static Thing[] compress(long[][] vals)
      {
         ArrayList<Long> ls = new ArrayList<Long>();
         ls.add(1L);
         for(int i=0; i < vals.length; i++)
         {
            ls.add(vals[i][1]);
            ls.add(vals[i][2]+1);
         }
         Collections.sort(ls);
         HashMap<Long, Integer> map = new HashMap<Long, Integer>();
         int boof = 0;
         for(long x: ls)
            if(!map.containsKey(x))
            {
               answer.put(boof, x);
               map.put(x, boof++);
            }
         Thing[] arr = new Thing[vals.length];
         for(int i=0; i < arr.length; i++)
            arr[i] = new Thing((int)vals[i][0], map.get(vals[i][1]), map.get(vals[i][2]+1));
         return arr;
      }
   }
   class Thing
   {
      public int type;
      public int left;
      public int right;
      
      public Thing(int a, int b, int c)
      {
         type = a;
         left = b;
         right = c;
      }
   }
   class LazySegTree
   {
      //definitions
      private int NULL = 0;
      //ds stuff
      private int[] tree;
      private int[] lazy;
      private int length;
      
      public LazySegTree(int N)
      {
         length = N;   int b;
         for(b=0; (1<<b) < length; b++);
         tree = new int[1<<(b+1)];
         lazy = new int[1<<(b+1)];
      }
      public int query(int left, int right)
      {
         //left and right are 0-indexed
         return get(1, 0, length-1, left, right);  
      }
      private int get(int v, int currL, int currR, int L, int R)
      {
         if(L > R)
            return NULL;
         if(L <= currL && currR <= R)
            return tree[v];
         propagate(v, currL, currR);
         int mid = (currL+currR)/2;
         return comb(get(v*2, currL, mid, L, Math.min(R, mid)),
            get(v*2+1, mid+1, currR, Math.max(L, mid+1), R));
      }
      public void update(int left, int right, int type)
      {
         add(1, 0, length-1, left, right, type);
      }
      private void add(int v, int currL, int currR, int L, int R, int type)
      {
         if(L > R)
            return;
         if(currL == L && currR == R)
         {
            //exact covering
            if(type == 1)
            {
               tree[v] = R-L+1;
               lazy[v] = 1;
            }
            else if(type == 2)
            {
               tree[v] = 0;
               lazy[v] = -1;
            }
            else
            {
               tree[v] = (R-L+1)-tree[v];
               if(Math.abs(lazy[v]) == 1)
                  lazy[v] *= -1;
               else
                  lazy[v] = Math.abs(lazy[v]-2);
            }
            return;
         }
         propagate(v, currL, currR);
         int mid = (currL+currR)/2;
         add(v*2, currL, mid, L, Math.min(R, mid), type);
         add(v*2+1, mid+1, currR, Math.max(L, mid+1), R, type);
         tree[v] = comb(tree[v*2], tree[v*2+1]);
      }
      private void propagate(int v, int L, int R)
      {
         //tree[v] already has lazy[v]
         if(lazy[v] == 1)
         {
            int length = tree[v];
            tree[v*2] = length/2+length%2;
            lazy[v*2] = 1;
            tree[v*2+1] = length/2;
            lazy[v*2+1] = 1;
         }
         else if(lazy[v] == -1)
         {
            tree[v*2] = 0;
            lazy[v*2] = -1;
            tree[v*2+1] = 0;
            lazy[v*2+1] = -1;
         }
         else if(lazy[v] == 2)
         {
            int mid = (L+R)/2;
            tree[v*2] = mid-L+1-tree[v*2];
            lazy[v*2] = lol(lazy[v*2]);
            tree[v*2+1] = R-mid-tree[v*2+1];
            lazy[v*2+1] = lol(lazy[v*2+1]);
         }
         lazy[v] = 0;
      }
      private int lol(int x)
      {
          if(Math.abs(x) == 1)
            return -1*x;
          return 2-x;
      }
      private int comb(int a, int b)
      {
         return a+b;
      }
   }