配点 : $600$ 点

問題文

関数 $f(x)$ があります。 はじめ、これは定数関数 $f(x) = 0$ です。

$Q$ 個のクエリが与えられるので、順番に処理してください。クエリは $2$ 種類あり、入力形式とクエリの内容は以下の通りです。

• 更新クエリ 1 a b:　2整数 $a$, $b$ が与えられるので、$g(x) = f(x) + |x - a| + b$ として $f(x)$ を $g(x)$ で置き換える。
• 求値クエリ 2:　$f(x)$ の最小値を与える $x$、および $f(x)$ の最小値を出力する。ただし、そのような $x$ が複数存在する場合には最小の $x$ を答える。

この時、求値クエリにおいて出力すべき値は常に整数となることが示せます。 したがって、出力する際は小数点を用いず、整数で出力してください。

制約

• 入力は全て整数
• $1 \leq Q \leq 2 \times 10^5$
• $-10^9 \leq a, b \leq 10^9$
• $1$ 番目のクエリは更新クエリである

入力

入力は以下の形式で標準入力から与えられる。

$Q$

$Query_1$

$:$

$Query_Q$

実例は入出力例 1 を参照せよ。

出力

求値クエリに対する応答を、クエリが与えられた順にそれぞれ 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 \leq x \leq 4$ を満たすならば最小値 $-3$ を与えます。この時、最小値を与える $x$ が複数存在していますが、その中で最小の値である $1$ を出力してください。

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

-1000000000 3000000000