問題文

東西に一直線に広がるW大学通りは、ラーメン店の激戦区です。 多数の出店があり、出店後すぐに潰れる店もあれば、長続きする店もあります。

ラーメン大好きヤマダ君は、これらのお店についての記録を見つけました。 記録内はW大学通りの過去から現在に至るまでの全店舗 \(N\) 店を網羅しており、ラーメン店 \(i\) それぞれについて、以下の情報が記載されていました。

• W通り上での位置 \(d_i\)
• 開店日（最初の営業日） \(o_i\)
• 閉店日（最後の営業日） \(c_i\)
  • ラーメン店 \(i\) が現在も営業を続けている場合、 \(c_i = -1\) です。
• 販売しているラーメンの美味しさ指数 \(x_i\)

しかし、全てのお店でのラーメンの販売価格 \(p_i\) の情報が欠けていました。 お金の少ない学生にとって、販売価格は非常に重要です。 困ったヤマダ君は、ラーメンに詳しいカトー君に相談すると、W大学通りでのラーメンの販売価格には以下のルールがあることを知りました。

• ラーメン店 \(i\) での販売価格 \(p_i\) は、そのお店の開店日の前日にW大学通りで営業している任意のラーメン店 \(j\) について、 \(p_i \leq \min( p_j + |d_i - d_j|^2 , x_i )\) が成り立つような \(p_i\) の最大値である。
• 開店日前日に、W大学通りで営業しているお店がないときは \(p_i = x_i\)。

この情報を基に、\(N\) 件のラーメン店でのラーメンの販売価格を復元してください。

制約

• \(1 \leq N \leq 10^5\)
• \(0 \leq d_i \leq 10^6\)
• \(1 \leq x_i \leq 10^{12}\)
• \(1 \leq o_i \leq c_i \leq 10^5\) または \(c_i = -1\)
• \(o_i \leq o_{i+1}\)
• 入力される値はすべて整数である。

入力例 1

4
1 6 1 5
2 11 3 10
3 6 4 2
8 11 4 15

出力例 1

5
9
2
10

入力例 2

7
1 5 106 662268024587
2 -1 131 151663457616
2 5 967 750705741256
2 6 95 614802747834
6 8 690 117869535832
7 7 644 14107192103
9 10 992 767668177628

出力例 2

662268024587
151663457616
662268765908
614802747834
117869535832
14107192103
117869627036