점프하는 주니퍼

Jack과 Jill은 숲속에 집을 가지고 있다. 그들은 집에서 곧게 뻗은 일직선을 따라 주니퍼 나무 몇 그루를 심었다. 각 나무는 집에서 이 선을 따라 정수 거리만큼 떨어진 곳에 심어져 있다. 두 나무가 같은 위치에 있는 경우는 없다.

Jack과 Jill은 나무들을 집에 더 가까이 옮기고 싶어한다. 나무가 무겁기 때문에, 그들은 나무를 양쪽 방향으로 일정 거리만큼만 옮길 수 있다 (나무마다 그 거리는 다를 수 있다). 나무들은 결국 집에서 이 선을 따라 양의 정수 거리만큼 떨어진 곳에 있어야 하고, 두 나무가 같은 곳에 있으면 안 된다. Jack과 Jill은 나무들의 집으로부터의 거리 합을 최소화하고 싶어한다. 그들이 어떻게 하면 되는지 알려주자.

첫 번째 줄에는 나무의 수를 나타내는 정수 n (1 ≤ n ≤ 200 000)이 주어진다.

다음 n개의 줄은 나무들을 설명한다. 이 줄들 각각에는 이 나무의 집으로부터의 거리인 정수 d (1 ≤ d ≤ 109)와, 이 나무가 양쪽 방향으로 옮겨질 수 있는 최대 거리인 정수 t (0 ≤ t ≤ 109)가 주어진다.

Jack과 Jill의 집으로부터의 거리 합을 최소화하는 n그루 나무의 새 위치를 (입력에서 주어진 것과 같은 순서로) 출력한다.

여러 해가 존재하면 아무거나 출력해도 된다.