AT_wupc2019_i Ramen

[problemUrl]: https://atcoder.jp/contests/wupc2019/tasks/wupc2019_i 東西に一直線に広がる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\\) 件のラーメン店でのラーメンの販売価格を復元してください。

入力は以下の形式で標準入力から与えられる。 ``` \(N\) \(o_1\) \(c_1\) \(d_1\) \(x_1\) \(\vdots\) \(o_N\) \(c_N\) \(d_N\) \(x_N\) ```

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

### 制約 - \\(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}\\) - 入力される値はすべて整数である。