014 - Nafmo、家を買う。2

もう一回Nafmo君に家を買ってもらうことになりました()　　　　　ykonのをコピペすると痛い目に遭う可能性が微レ存

問題:

Nafmo君は家を買うために情報を集めています。$q$行に渡り次の2種類のクエリが与えられるので、それを処理しなさい。

1. 1 size price

2. 2 desire

クエリ1はNafmo君が大きさ$size$、価格$price$の物件についての情報を得たことを示します。

クエリ2はNafmo君が大きさが$desire$の家を買いたがっていることを示します。
Nafmo君はなによりも家の大きさのちょうど良さを重視します。価格は二の次です。
このときNafmo君は、ここまでで得た情報に基づき、大きさと$desire$の差が最も小さく、その上で最も安い家を1つ購入します。
###追記###　家を購入しても物件の情報は無くなりません(分譲的な(?))

出力

Nafmo君が購入した家の金額の合計を$10^9+7$で割った値を出力しなさい。

入力

q
Query1
Query2
⋮
Queryq

制約・部分点

• $2≤q≤100000$
• $1≤|size|,|desire|≤10^{18}$
• $1≤price≤10^4$
• 1つ目のクエリの形式は(1)である。

部分点1

サンプルケース
10%

部分点2

追加制約: $1≤|size|,|desire|≤10^5$
70%

部分点3

追加制約無し
20%(ここまでで満点)

入出力例

入力

6
1 1 100
1 5 400
2 4
2 3
1 3 50000
2 3

出力

50500

1行目より、6個のクエリが与えられます。

1,2個目のクエリを処理した時点で、Nafmo君は
大きさ 1 価格 100 の家...(1)と
大きさ 5 価格 400 の家...(2)についての情報を持っています。

3個目のクエリではNafmo君は大きさが 4 の家を欲しがっているので、大きさが 4 に最も近い、家(2)を購入します。

4個目のクエリではNafmo君は大きさが 3 の家を欲しがっています。家(1)の大きさと希望の差、家(2)の大きさと希望の差はそれぞれ等しいので、安い方を購入します。

5個目のクエリではNafmo君は新たに
大きさ 3 価格 50000 の家...(3)についての情報を得ます。

6個目のクエリではNafmo君は大きさが 3 の家を欲しがっているので、大きさが 3 である、家(3)を購入します。