题目描述

一个无限长的 $01$ 序列，初始全为 $0$，每次选择一个区间 $[l,r]$ 进行操作，有三种操作：

• 1 l r：将 $[l,r]$ 中所有元素变成 $1$；
• 2 l r：将 $[l,r]$ 中所有元素变成 $0$；
• 3 l r：将 $[l,r]$ 中所有元素异或上 $1$。

每次操作后询问最左边的 $0$ 在哪个位置。

输入格式

第一行一个整数 $m$，表示序列长度和操作数量。

接下来 $m$ 行，每行三个整数 $op,l,r$，描述一次操作。

输出格式

输出共 $m$ 行，第 $i$ 行输出一个数表示第 $i$ 次操作后的答案。

样例

3
1 3 4
3 1 6
2 1 3

1
3
1

数据范围

令 $n$ 为 $\max(r)$。

• 对于测试点 $1\sim 4$，$n,m\le 10^3$。
• 对于测试点 $5\sim 6$，只有 $1$ 操作。
• 对于测试点 $7\sim 10$，只有 $1,2$ 操作。
• 对于测试点 $11\sim 15$，$n\le 10^5$。
• 对于测试点 $16\sim 20$，无特殊限制。

对于全部数据，$1\le n\le 10^{18}$，$1\le m\le 10^5$。