问题陈述

对于一组非负整数对的集合$S$，以及一个非负整数$x$，定义函数$f_S(x)$为$\\displaystyle f_S(x)=\\min_{(a, b) \\in S} \\left| \\left| x-a \\right| - b \\right|$。

我们有一组非负整数对的集合$T$。最初，$T=\\lbrace (A, B)\\rbrace$。

进行$Q$次查询。第$i$个查询给出三个非负整数$t_i$、$a_i$和$b_i$，并要求你执行以下操作：

• 如果$t_i=1$，则将非负整数对$(a_i, b_i)$添加到$T$中。
• 如果$t_i=2$，则计算满足$a_i \\leq x \\leq b_i$的非负整数$x$的$f_{T}(x)$的最小值。

约束条件

• $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$的查询。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$Q$ $A$ $B$ $t_1$ $a_1$ $b_1$ $t_2$ $a_2$ $b_2$ $\\vdots$ $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

示例输出1

2
1

在第二个查询中，$T=\\lbrace(0, 5), (3, 11) \\rbrace$。对于$x=7$，我们有$f_T(7)=\\min \\lbrace \\left| \\left|7-0\\right|-5\\right|, \\left| \\left|7-3\\right|-11\\right| \\rbrace=\\min \\lbrace 2, 7 \\rbrace=2$。类似地，$f_T(8)=3$。因此，答案是$\min \\lbrace 2, 3 \\rbrace =2$。

在第四个查询中，$T=\\lbrace(0, 5), (3, 11), (8, 2) \\rbrace$。在$8 \\leq x \\leq 9$范围内，$f_T(x)$在$x=9$处取得最小值$f_T(9)=1$。

示例输入2

2 1 2
1 2 3
2 2 6

示例输出2

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

示例输出3

26468090
3491640
25280111
9543684
0
22804896
20649370
19245624
4849993
484865