题目描述

给定一个由两个非负整数组成的二元组集合 $S$，以及一个非负整数 $x$，定义 $f_S(x)$ 为

$$f\_S(x)=\min\_{(a,\,b)\in S} \left|\,|x-a|-b\,\right|$$

有一个由两个非负整数组成的二元组集合 $T$。初始时 $T=\lbrace (A,\,B)\rbrace$。

请处理 $Q$ 个查询。对于第 $i$ 个查询，给出三个非负整数 $t_i,\,a_i,\,b_i$，请按如下方式处理：

• 当 $t_i=1$ 时，向 $T$ 中添加二元组 $(a_i,\,b_i)$。
• 当 $t_i=2$ 时，输出满足 $a_i\leq x\leq b_i$ 的所有非负整数 $x$ 中 $f_T(x)$ 的最小值。

输入格式

输入按以下格式从标准输入读入。

$Q\ A\ B\ t\_1\ a\_1\ b\_1\ t\_2\ a\_2\ b\_2\ \cdots\ t\_Q\ a\_Q\ b\_Q$

输出格式

对于每个 $t_i=2$ 的查询，按顺序每行输出一个答案。

样例 1

输入

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

输出

2
1

样例 2

输入

2 1 2
1 2 3
2 2 6

输出

0

样例 3

输入

20 795629912 123625148
2 860243184 892786970
2 645778367 668513124
1 531411849 174630323
1 635062977 195695960
2 382061637 411843651
1 585964296 589553566
1 310118888 68936560
1 525351160 858166280
2 395304415 429823333
2 583145399 703645715
2 97768492 218377432
1 707220749 459967102
1 210842017 363390878
2 489541834 553583525
2 731279777 811513313
1 549864943 493384741
1 815378318 826084592
2 369622093 374205455
1 78240781 821999998
2 241667193 243982581

输出

26468090
3491640
25280111
9543684
0
22804896
20649370
19245624
4849993
484865

说明/提示

数据范围

• $1\leq Q\leq 2\times 10^5$
• $0\leq A,B\leq 10^9$
• $t_i$ 为 $1$ 或 $2$
• $0\leq a_i,b_i\leq 10^9$
• 当 $t_i=2$ 时，$a_i\leq b_i$
• 至少存在一个 $t_i=2$ 的查询
• 所有输入的值均为整数

样例解释 1

执行第 2 个查询时，$T=\lbrace(0,\,5),\ (3,\,11)\rbrace$，例如 $x=7$ 时，$f\_T(7)=\min\lbrace\,|\ |7-0|-5|,\ |\ |7-3|-11|\,\rbrace=\min\lbrace 2,\,7\rbrace=2$。同理，$f_T(8)=3$。因此，第 2 个查询的答案为 $\min\lbrace 2,\,3\rbrace=2$。执行第 4 个查询时，$T=\lbrace(0,\,5),\ (3,\,11),\ (8,\,2)\rbrace$，在 $8\leq x\leq 9$ 时，$f_T(x)$ 在 $x=9$ 取得最小值 $f_T(9)=1$。

由 ChatGPT 4.1 翻译