Problem Description

W University Street, which stretches straight from east to west, is a fiercely competitive area for ramen shops. There are many shops, some of which close down immediately after opening, while others continue to thrive.

Yamada, a big fan of ramen, found a record about these shops. The record includes all \(N\\) shops on W University Street from the past to the present, with the following information for each ramen shop \(i\\):

• Position on W Street \(d\_i\\)
• Opening date (first business day) \(o\_i\\)
• Closing date (last business day) \(c\_i\\)
• If ramen shop \(i\\) is still in business, \(c\_i = -1\\).
• Deliciousness index of the ramen sold \(x\_i\\)

However, the information about the selling price \(p\_i\\) of ramen at all shops was missing. For students with little money, the selling price is very important. Struggling, Yamada consulted Kato, who is knowledgeable about ramen, and learned that there are rules for the selling prices of ramen on W University Street:

• The selling price \(p\_i\\) at ramen shop \(i\\) is the maximum value such that for any ramen shop \(j\\) that was in business on the day before the opening date of shop \(i\\), \(p\_i \\leq \\min( p\_j + |d\_i - d\_j|^2 , x\_i )\\) holds.
• If there are no shops in business on the day before the opening date, \(p\_i = x\_i\\).

Based on this information, please restore the selling prices of ramen at the \(N\\) ramen shops.

Input Format

The input is given from the standard input in the following format:

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

## Output Format

Output \\(N\\) lines. The \\(i\\)th line should contain the selling price of ramen shop \\(i\\).

## Sample Input and Output

### Sample Input #1

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

### Sample Output #1

5
9
2
10

### Sample Input #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

### Sample Output #2

662268024587
151663457616
662268765908
614802747834
117869535832
14107192103
117869627036
```

Notes/Hints

Constraints

• \(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\\) or \(c\_i = -1\\)
• \(o\_i \\leq o\_{i+1}\\)
• All input values are integers.

见题面 Input 部分

见题面 Output 部分