The squirrel nation is setting up an acorn delivery system. There are ~N~ squirrels numbered from ~1~ to ~N~ and each squirrel has a single acorn that they want to deliver to the head squirrel (who is squirrel number ~N~). Specifically, they have designed a system where squirrel ~i~ will always pass their acorn, and any acorns they receive from other squirrels, to a single squirrel ~j_i~ where ~i < j_i \le N~ (with the exception of the head squirrel who will never pass an acorn to anyone).

The squirrels have scattered themselves randomly around their nation, independent of who they pass their acorns to, with the ~i^{th}~ squirrel being located at the point ~(x_i, y_i)~. The additional cost of passing an acorn from squirrel ~i~ to squirrel ~j~ is equal to the Euclidean distance squared between their locations ~(x_i - x_j)^2 + (y_i - y_j)^2~. In addition, if squirrel ~i~ receives an acorn (including the head squirrel), an additional cost of ~c_i~, chosen randomly and independent of who any squirrel passes their acorns to, is added.

The acorn originating from each squirrel will pass through a number of squirrels before reaching the head squirrel. In order to minimize the cost, for each acorn, you can choose for it to skip over a subset of the squirrels and move directly to the next unskipped squirrel, without modifying the original order. Of course, you cannot skip the head squirrel as they will be receiving the acorn, or the originating squirrel. For each squirrel, can you determine the minimum cost to deliver their acorn to the head squirrel?

For this problem, Python users are recommended to use PyPy over CPython.

Constraints

For this problem, NONE of the samples will appear in the actual test cases. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

For all subtasks:

~1 \le N \le 200\,000~
~0 \le x_i, y_i \le 10^6~ for all ~1 \le i \le N~
~0 \le c_i \le 10^{12}~ for all ~1 \le i \le N~
~c_i~ is selected uniformly at random from the range ~[0, 10^{12}]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.
~i < j_i \le N~ for all ~1 \le i < N~
~j_N = 0~

Subtask 1 [8%]

~1 \le N \le 16~
~x_i~ is selected uniformly at random from the range ~[0, 10^6]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.
~y_i~ is selected uniformly at random from the range ~[0, 10^6]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.

Subtask 2 [12%]

~1 \le N \le 300~
~x_i~ is selected uniformly at random from the range ~[0, 10^6]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.
~y_i~ is selected uniformly at random from the range ~[0, 10^6]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.

Subtask 3 [6%]

~1 \le N \le 5\,000~
~x_i~ is selected uniformly at random from the range ~[0, 10^6]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.
~y_i~ is selected uniformly at random from the range ~[0, 10^6]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.
~j_i = i+1~ for all ~1 \le i < N~

Subtask 4 [4%]

~1 \le N \le 5\,000~
~x_i~ is selected uniformly at random from the range ~[0, 10^6]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.
~y_i~ is selected uniformly at random from the range ~[0, 10^6]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.

Subtask 5 [16%]

~1 \le N \le 200\,000~
~x_i = 0~ for all ~1 \le i \le N~
~y_i~ is selected uniformly at random from the range ~[0, 10^6]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.
~j_i = i+1~ for all ~1 \le i < N~

Subtask 6 [15%]

~1 \le N \le 200\,000~
~x_i = 0~ for all ~1 \le i \le N~
~y_i~ is selected uniformly at random from the range ~[0, 10^6]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.

Subtask 7 [17%]

~1 \le N \le 200\,000~
~x_i~ is selected uniformly at random from the range ~[0, 10^6]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.
~y_i~ is selected uniformly at random from the range ~[0, 10^6]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.
~j_i = i+1~ for all ~1 \le i < N~

Subtask 8 [22%]

~1 \le N \le 200\,000~
~x_i~ is selected uniformly at random from the range ~[0, 10^6]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.
~y_i~ is selected uniformly at random from the range ~[0, 10^6]~ for all ~1 \le i \le N~, independent of who any squirrel passes their acorns to.

Input Specification

The first line of input contains a single integer ~N~, representing the number of squirrels in the squirrel nation.

The next ~N~ lines describe the squirrels. Each contains ~4~ integers, ~x_i~, ~y_i~, ~c_i~, ~j_i~, indicating that the ~i^{th}~ squirrel is located at ~(x_i, y_i)~, incurs an additional cost of ~c_i~ for every acorn that the ~i^{th}~ squirrel receives, and passes their acorn to squirrel ~j_i~ in the current system. Only input where ~j_N = 0~ is allowed, which indicates that the head squirrel will not pass the acorn to any other squirrel.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output ~N~ lines. The ~i^{th}~ line should contain a single integer equal to the minimum cost to deliver the ~i^{th}~ squirrel's acorn to the head squirrel after skipping over a subset of the original squirrel.

Sample Input 1

5
0 1 3 2
0 3 1 3
0 7 2 4
0 5 10 5
0 4 3 0

Sample Output 1

9
4
12
4
0

Sample Explanation 1

Squirrel ~1~ can pass their acorn to squirrel ~2~, who can then pass the acorn to squirrel ~5~ for a cost of ~2^2 + 1 + 1^2 + 3 = 9~.
Squirrel ~2~ can pass their acorn to squirrel ~5~ (skipping squirrels ~3~ and ~4~) for a cost of ~1^2 + 3 = 4~.
Squirrel ~3~ can pass their acorn to squirrel ~5~ (skipping squirrel ~4~) for a cost of ~3^2 + 3 = 12~.
Squirrel ~4~ can pass their acorn to squirrel ~5~ for a cost of ~1^2 + 3 = 4~.
Squirrel ~5~ does not need to pass their acorn to anyone else, and thus incurs a cost of ~0~.

Sample Input 2

5
0 7 8 2
0 1 5 5
0 9 2 4
0 8 4 5
0 5 10 0

Sample Output 2

14
26
24
19
0

Sample Input 3

4
1 2 2 2
2 6 3 3
4 3 10 4
5 7 4 0

Sample Output 3

34
14
21
0

Sample Input 4

6
10 4 2 2
8 6 1 6
1 2 3 4
8 9 4 5
3 2 9 6
6 7 10 0

Sample Output 4

24
15
57
18
44
0