F - 绝对最小值

分数：$600$ 分

问题描述

有一个函数 $f(x)$，初始时它是一个常数函数 $f(x) = 0$。

我们将按顺序进行 $Q$ 个查询。查询分为两种：更新查询和求值查询，具体如下：

• 更新查询 1 a b：给定两个整数 $a$ 和 $b$，令 $g(x) = f(x) + |x - a| + b$，将 $f(x)$ 替换为 $g(x)$。
• 求值查询 2：输出使得 $f(x)$ 最小的 $x$ 值，以及 $f(x)$ 的最小值。如果存在多个这样的 $x$ 值，则选择最小的那个。

我们可以证明，求值查询的输出值始终为整数，所以请将这些值作为整数输出，不要有小数点。

约束

• 所有输入值均为整数。
• $1 \leq Q \leq 2 \times 10^5$
• $-10^9 \leq a, b \leq 10^9$
• 第一个查询为更新查询。

输入

从标准输入读入数据，格式如下：

$Q$

$Query_1$

:

$Query_Q$

示例中有详细解释。

输出

对于每个求值查询，在按照查询的顺序输出时，每行输出一次响应。

每个求值查询的响应应包含两个值，用空格隔开，分别是使得 $f(x)$ 最小的 $x$ 值以及 $f(x)$ 的最小值。

4
1 4 2
2
1 1 -8
2

4 2
1 -3

在第一个求值查询中，$f(x) = |x - 4| + 2$，使得 $f(x)$ 最小的 $x$ 值是 $4$，对应的最小值是 $2$。

在第二个求值查询中，$f(x) = |x - 1| + |x - 4| - 6$，使得 $f(x)$ 最小的 $x$ 值取值范围是 $1 \leq x \leq 4$，在这个范围内，有多个使 $f(x)$ 最小的 $x$ 值，我们要求你输出最小的那个，即 $1$。

4
1 -1000000000 1000000000
1 -1000000000 1000000000
1 -1000000000 1000000000
2

-1000000000 3000000000