问题描述

问题陈述

有一个函数 $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$

参见示例输入 1。

输出

对于每个求值查询，按查询给出的顺序打印一行响应。

每个求值查询的响应应包括使 $f(x)$ 最小的 $x$ 的最小值和 $f(x)$ 的最小值，以此顺序，并以空格分隔。

示例输入 1

4
1 4 2
2
1 1 -8
2

示例输出 1

4 2
1 -3

在第一个求值查询中，$f(x) = |x - 4| + 2$，它在 $x=4$ 时达到最小值 $2$。

在第二个求值查询中，$f(x) = |x - 1| + |x - 4| - 6$，它在 $1 \leq x \leq 4$ 时取得最小值 $-3$。在使 $f(x)$ 最小的多个 $x$ 值中，我们要求打印最小值，即 $1$。

示例输入 2

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

示例输出 2

-1000000000 3000000000