I - Ramen

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : \(300\) 点

問題文

東西に一直線に広がる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}\)
  • 入力される値はすべて整数である。

入力

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

\(N\)
\(o_1\) \(c_1\) \(d_1\) \(x_1\)
\(\vdots\)
\(o_N\) \(c_N\) \(d_N\) \(x_N\)

出力

\(N\) 行出力してください。 \(i\) 行目には、ラーメン店 \(i\) の販売価格を出力してください。


入力例 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

入出力の値は非常に大きい場合があるので注意してください。