낙하 데미지

메이플스토리의 맵은 2차원 평면에 x축에 평행인 여러 선분들이 공중에 떠 있는 형태로 이루어져 있다.

맵에 선분 $N$ 개가 있고, 각 선분에는 $1$부터 $N$까지 번호가 매겨져 있다. 선분 $i$의 높이는 $y_i$이며, 양 끝 점의 x좌표는 $s_i$와 $e_i$다.

$N$ 개의 선분 외에 땅이 있다. 땅은 $y = 0$인 직선이며, 편의상 선분 $0$으로 볼 수 있다. 즉, $y_0 = 0$, $s_0 = -\infty$, $e_0 = \infty$이다.

게임 캐릭터는 한 선분에서 시작해서, 적절히 낙하하며 땅까지 내려가려고 한다. 캐릭터는 선분의 임의의 위치에서 낙하할 수 있다. 낙하하는 경우 캐릭터는 y축에 평행하도록 직선 낙하한다. 낙하하면서 만나는 선분 중간 혹은 양 끝 점에 착지할 수 있고, 착지하지 않고 그대로 낙하할 수도 있다. 만약, 선분 위에 착지한 경우 그 선분 위에서 좌우로 마음대로 이동할 수 있다.

캐릭터가 선분 위에 착지할 때 낙하 데미지를 받게 된다. 높이가 $y_i$인 선분 $i$에서 낙하하여, 높이가 $y_j$인 선분 $j$ 위에 착지할 경우, 받는 낙하 데미지는 $(y_i-y_j)^2 + c_j$이다. 여기서, $c_j$는 선분 $j$의 고유 추가 낙하 데미지 값이다. 땅의 고유 추가 낙하 데미지 값 $c_0$은 $0$이다.

모든 선분에 대해 그 선분의 임의의 위치에서 시작한 캐릭터가 땅까지 내려갈 때 받는 낙하 데미지의 최솟값을 구하라.

입력 형식

첫 줄에 맵에 있는 선분의 수를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 200\,000$)

둘째 줄부터 각 줄에 선분 $i$의 높이와, 양 끝 점의 x좌표, 그리고 고유 추가 낙하 데미지를 나타내는 네 정수 $y_i$, $s_i$, $e_i$, $c_i$가 공백으로 구분되어 주어진다. ($1 \le y_i, s_i, e_i \le 1\,000\,000\,000;$ $s_i \le e_i$; $0 \le c_i \le 1\,000\,000\,000$)

주어지는 모든 선분은 서로 겹치거나 끝 점에서 만나지 않게 주어진다.

출력 형식

$i$ 번째 줄에 선분 $i$의 임의의 위치에서 시작한 캐릭터가 땅까지 내려갈 때 받는 낙하 데미지의 최솟값을 출력한다.

예제

4
2 10 12 1
3 3 6 0
1 1 8 10
4 5 14 0

4
9
1
9

예제 설명

선분 $3$과 선분 $1$에서는 낙하하여 바로 땅에 착지할 경우 각각 $1$과 $4$ 만큼의 낙하 데미지를 받는다. 선분 $2$에서 낙하하여 선분 $3$에 착지 후 다시 땅으로 낙하할 경우, 총 $14 + 1 = 15$ 만큼 낙하 데미지를 받는 반면, 바로 땅으로 낙하할 경우 $9$ 만큼 낙하 데미지를 받는다. 선분 $4$에서 선분 $1$로 낙하하고, 선분 $1$에서 땅으로 낙하할 경우, 총 $5 + 4 = 9$ 만큼 낙하 데미지를 받는다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설