#P9605. 联

    ID: 6220 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF1900普及+/提高-离散化懒标记线段树标记复合线段树上二分半开区间统一添加哨兵

联

题目描述

一个无限长的 0101 序列,初始全为 00,每次选择一个区间 [l,r][l,r] 进行操作,有三种操作:

  • 1 l r:将 [l,r][l,r] 中所有元素变成 11;
  • 2 l r:将 [l,r][l,r] 中所有元素变成 00;
  • 3 l r:将 [l,r][l,r] 中所有元素异或上 11。

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

输入格式

第一行一个整数 mm,表示序列长度和操作数量。

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

输出格式

输出共 mm 行,第 ii 行输出一个数表示第 ii 次操作后的答案。

样例

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

数据范围

令 nn 为 max⁡(r)\max(r)。

  • 对于测试点 1∼41\sim 4,n,m≤103n,m\le 10^3。
  • 对于测试点 5∼65\sim 6,只有 11 操作。
  • 对于测试点 7∼107\sim 10,只有 1,21,2 操作。
  • 对于测试点 11∼1511\sim 15,n≤105n\le 10^5。
  • 对于测试点 16∼2016\sim 20,无特殊限制。

对于全部数据,1≤n≤10181\le n\le 10^{18},1≤m≤1051\le m\le 10^5。