绝对值函数最小值

题目描述

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

给定 $Q$ 个查询，请按顺序处理。查询有两种，输入格式和内容如下。

• 更新查询 1 a b：给定两个整数 $a$, $b$，令 $g(x) = f(x) + |x - a| + b$，用 $g(x)$ 替换 $f(x)$。
• 求值查询 2：输出使得 $f(x)$ 取最小值的 $x$，以及 $f(x)$ 的最小值。但是，如果这样的 $x$ 存在多个，则回答最小的 $x$。

可以证明，此时求值查询中应输出的值总是整数。 因此，输出时不要使用小数点，请以整数输出。

输入格式

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

$Q$
$Query_1$
$:$
$Query_Q$

具体示例参见样例输入输出 1。

输出格式

按查询给出的顺序，对每个求值查询输出一行应答。

每个求值查询的应答中，用空格分隔输出使 $f(x)$ 取最小值的最小的 $x$，以及 $f(x)$ 的最小值。

样例

4
1 4 2
2
1 1 -8
2

4 2
1 -3

第 $1$ 个求值查询时，$f(x) = |x - 4| + 2$。因此在 $x = 4$ 处取最小值 $2$。

第 $2$ 个求值查询时，$f(x) = |x - 1| + |x - 4| - 6$，当 $x$ 满足 $1 \le x \le 4$ 时取最小值 $-3$。此时使最小值成立的 $x$ 存在多个，请输出其中最小的值 $1$。

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

-1000000000 3000000000

数据范围

• 输入均为整数
• $1 \le Q \le 2 \times 10^5$
• $-10^9 \le a, b \le 10^9$
• 第 $1$ 个查询是更新查询