#P17963. Watering System

Watering System

Watering System

有 nn 个花盆排成一行,编号为 11 到 nn。可以在这行花盆上放置浇水机。每台浇水机有一个位置 xx(1≤x≤n1\le x\le n),以及向左或向右的方向。

所有浇水机使用相同的浇水范围 LL,其中 LL 是非负整数:

  • 位于 xx、方向向右的机器,浇灌编号在 [x,x+L][x,x+L] 内的花盆。
  • 位于 xx、方向向左的机器,浇灌编号在 [x−L,x][x-L,x] 内的花盆。

只有编号在 11 到 nn 之间的花盆实际存在。

初始没有任何浇水机。按时间顺序处理 qq 次操作:

  • 操作 “1 d x”:在位置 xx 新增一台机器。d=0d=0 表示向左,d=1d=1 表示向右。同一位置允许有多台机器,机器不会被删除。
  • 操作 “2 l r”:对于当前所有机器,求一个最小的非负整数 LL,使区间 [l,r][l,r] 内每个花盆都至少被一台机器浇灌。区间外的机器也可以浇灌区间内的花盆。 若无论 LL 多大都不能覆盖全部目标花盆,输出 −1-1。

每次询问独立选择范围 LL,不会改变机器的位置和方向。

输入格式

第一行两个整数 n,qn,q(1≤n,q≤3⋅1051\le n,q\le3\cdot10^5)。

接下来 qq 行,每行描述一次操作:

  • “1 d x”,其中 d∈{0,1}d\in\{0,1\},1≤x≤n1\le x\le n;
  • “2 l r”,其中 1≤l≤r≤n1\le l\le r\le n。

输出格式

对于每次第二类操作,输出一行一个整数:所需的最小 LL;若不存在则输出 −1-1。

样例 1

输入

10 11
1 0 6
2 5 8
1 1 3
2 9 10
2 3 9
1 1 8
2 1 9
2 1 8
1 0 4
2 3 7
2 2 9

输出

-1
7
6
5
5
4
4