낙하 데미지

NYPC 2021 · 예선

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

맵에 선분 NN 개가 있고, 각 선분에는 11부터 NN까지 번호가 매겨져 있다. 선분 ii의 높이는 yiy_i이며, 양 끝 점의 x좌표는 sis_ieie_i다.

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

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

캐릭터가 선분 위에 착지할 때 낙하 데미지를 받게 된다. 높이가 yiy_i인 선분 ii에서 낙하하여, 높이가 yjy_j인 선분 jj 위에 착지할 경우, 받는 낙하 데미지는 (yiyj)2+cj(y_i-y_j)^2 + c_j이다. 여기서, cjc_j는 선분 jj의 고유 추가 낙하 데미지 값이다. 땅의 고유 추가 낙하 데미지 값 c0c_000이다.

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

입력 형식

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

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

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

출력 형식

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

예제

입력

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

출력

4 9 1 9

예제 설명

<그림 1> 입력 예제
<그림 1> 입력 예제

선분 33과 선분 11에서는 낙하하여 바로 땅에 착지할 경우 각각 1144 만큼의 낙하 데미지를 받는다. 선분 22에서 낙하하여 선분 33에 착지 후 다시 땅으로 낙하할 경우, 총 14+1=1514 + 1 = 15 만큼 낙하 데미지를 받는 반면, 바로 땅으로 낙하할 경우 99 만큼 낙하 데미지를 받는다. 선분 44에서 선분 11로 낙하하고, 선분 11에서 땅으로 낙하할 경우, 총 5+4=95 + 4 = 9 만큼 낙하 데미지를 받는다.

채점 방식

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

종류 1: 14

N2000N \le 2\,000

종류 2: 23

모든 ii에 대해 ci=0c_i = 0

종류 3: 44

N50000N \le 50\,000

종류 4: 19

추가적인 제한 조건이 없음.

해설