問題

背景

イクタ君は一列に並んだ看板の色がすべて同じ色になるように塗り替えようとしている。 一方、ビッグブリッジ伯爵はイクタ君の邪魔をするために、次々と看板を増やしたり減らしたりする。 それぞれの邪魔が行われた時点で塗り替えを始めると、すべての看板を同じ色にするのにどれだけ時間がかかるか求めよ。

課題

N(1 ≤ N ≤ 100,000) 個の看板が x 軸上に並んでいる。 i 番目の看板は x_i(-10^9 ≤ x_i ≤ 10^9) の位置にあり、a_i(1 ≤ a_i ≤ 200,000) の色で塗られている。 ビッグブリッジ伯爵は Q(1 ≤ Q ≤ 100,000) 回の看板の追加や削除を行う。 各追加と削除が行われた後にイクタ君が塗り替えを始めると、すべての看板を同じ色に塗り替えるのにどれだけ時間がかかるか求めよ。 イクタ君は最初 x = 0 の位置におり、x_p から x_q に移動するのには |x_p - x_q| の時間がかかる。 また、a_p の色の看板を a_q の色に塗り替えるのには |a_p - a_q| の時間がかかる。

配点

300

入力

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

N
x_1 a_1
:
x_N a_N
Q
c_1 y_1 b_1
:
c_Q y_Q b_Q

1 行目には、はじめから並んでいる看板の数を表す整数 N が与えられる。 続く N 行には、はじめから並んでいる看板の位置と色を表す整数 x_i 、a_i が与えられる。 N+2 行目には、看板の追加・削除の回数を表す整数 Q が与えられる。 続く Q 行には、看板の追加・削除を表す整数 c_i 、y_i 、b_i が与えられる。 c_i はクエリの種類を表す。 c_i = 1 のとき看板の追加を意味し、y_i の位置に b_i の色の看板が追加される。 c_i = 2 のとき看板の削除を意味し、y_i の位置にある b_i の色の看板が削除される。

制約

• 1 ≤ N ≤ 100,000
• -10^9 ≤ x_i ≤ 10^9
• 1 ≤ a_i ≤ 200,000
• 1 ≤ Q ≤ 100,000
• 1 ≤ c_i ≤ 2
• -10^9 ≤ y_i ≤ 10^9
• 1 ≤ b_i ≤ 200,000
• 削除のクエリに対して削除される看板は必ず存在する。
• 任意の時点で看板の個数が 0 になることはない。
• 任意の時点で同じ位置に複数の看板が存在することはない。

部分点

この問題には部分点が設定されている。この問題のテストケースのうち 30 点分は追加で以下の制約を満たす。

• 1 ≤ N ≤ 2,000
• 1 ≤ Q ≤ 2,000

出力

各追加と削除が行われた後の看板の列に対して、イクタ君がすべての看板を同じ色に塗り替えるのに必要な最小の時間を 1 行づつ出力せよ。

入力例1

1
10 1
3
1 2 2
1 -2 3
2 10 1

出力例1

3
9
3

1 つめのクエリで看板が追加された時点では、位置 x=2 に色 a=2 の看板が、位置 x=10 に色 a=1 の看板があるので、 x=2 の看板を色 a=1 で塗り替えると時間 3 ですべての看板が同じ色になる。

2 つめのクエリで看板が追加された時点では、位置 x=-2 に色 a=3 の看板が、位置 x=2 に色 a=2 の看板が、位置 x=10 に色 a=1 の看板があるので、 x=-2 の看板を色 a=1 で塗り替えたあと、x=2 の看板を色 a=1 で塗り替えると時間 9 ですべての看板が同じ色になる。

3 つめのクエリで看板が削除された時点では、位置 x=-2 に色 a=3 の看板が、位置 x=2 に色 a=2 の看板があるので、どちらかの看板をもう一方の看板の色に塗り替えると時間 3 ですべての看板が同じ色になる。