23090번 - 난민

문제

A나라에서 내전이 일어났다!

이 때문에 많은 내전 난민들이 B나라로 오게 되었고, B나라는 이들을 위해 난민촌을 건설해 주었다.

다음은 난민촌을 좌표평면으로 나타낸 그림이다. 파란색 선은 강, 빨간색 점은 난민의 거주 위치를 나타낸다.

난민촌에는 직선 \(x=0\)을 따라 흐르는 강이 하나 있다.

물을 얻기 위해서는 이 강을 이용해야만 하는데, 수질이 좋지 않아 정수시설을 설치하려고 한다.

하지만 예산 문제로 정수시설은 강의 한 지점에만 설치할 수 있기 때문에, 각 난민들이 정수시설에 도착하기 위한 이동거리의 합이 최소가 되는 위치에 정수시설을 설치하려고 한다.

지금 이 순간에도 난민들이 이주해 오고 있다. 난민촌에 사람들이 이주해 올 때마다, 정수시설을 설치해야 하는 위치와 그 때의 이동거리의 합을 갱신해 알려주자.

두 좌표 \((x_1, y_1)\)와 \((x_2, y_2)\)사이의 거리는 \(|x_1 - x_2| + |y_1 - y_2|\)로 계산한다.

입력

첫째 줄에 난민의 수 \(N\)이 주어진다.

이어서 \(N\)개의 줄에, \(i\)번째로 이주해온 난민의 위치 \((x_i, y_i)\)가 공백으로 구분되어 주어진다.

출력

문제의 답을 공백으로 구분하여 \(N\)줄에 걸쳐 출력한다.

\(i\)번째 줄에, \(1\)번째 부터 \(i\)번째까지 이주해온 난민들이 정수시설까지 이동하는 거리의 합이 최소가 되도록 하는 정수시설의 \(y\)좌표와, 그 때의 이동거리의 합을 공백으로 구분하여 출력한다.

만약 이를 만족하는 정수시설의 위치가 여러 곳이라면, \(y\)좌표가 가장 작은 지점을 출력한다.

제한

• 1 ≤ \(N\) ≤ 10⁵
• -10⁹ ≤ \(x_i\), \(y_i\) ≤ 10⁹, 모든 좌표는 정수이다.

힌트