AT_wupc2019_i.Ramen

W大学的主干道上分布着许多拉面店，这里可是拉面店竞争的激烈战场。有的店开业后不久便黯然退场，而有的店则能长久存续。

拉面迷山田君发现了一份关于这些店铺的记录。这份记录囊括了从过去到现在在W大学街上出现过的所有 \(N\) 家拉面店。对于每家拉面店 \(i\) ，记录中包含以下信息：

• 该店在街道上的位置 \(d_i\)
• 开业日期（第一次营业的日期） \(o_i\)
• 停业日期（最后一次营业的日期） \(c_i\)
  • 如果拉面店 \(i\) 还在营业，那么 \(c_i = -1\)。
• 该店拉面的美味指数 \(x_i\)

不过，记录中缺失了所有拉面店的销售价格 \(p_i\)。而对于预算有限的学生来说，价格可是相当重要的。为了解决这个问题，拉面专家加藤君告诉山田君，W大学街上的拉面定价有以下规律：

• 对于拉面店 \(i\)，在其开业日前一天仍在营业的任何拉面店 \(j\)， \(i\) 店的销售价格 \(p_i\) 要满足 \(p_i \leq \min(p_j + |d_i - d_j|^2, x_i)\) 的最大值。
• 如果在开业日前一天没有任何店铺在营业，那么 \(p_i = x_i\)。

请根据这些信息，计算出这 \(N\) 家拉面店的销售价格。

输入通过标准输入给出，格式如下：

N
o_1 c_1 d_1 x_1
...
o_N c_N d_N x_N

输出共 \(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}\)
• 所有输入的值均为整数。

本翻译由 AI 自动生成