마법 막대

벨라에게는 번호가 매겨진 마법 막대 $n$개가 있다. 마법 에너지를 얻기 위해 벨라는 각 막대의 양 끝에 불을 붙인다. 두 끝에 불을 붙이는 시각은 같을 수도, 다를 수도 있다. 불은 초당 1cm의 속도로 번진다. 불이 막대 전체를 덮는 순간 그 막대의 에너지가 방출된다.

막대 $i$의 길이는 $l_i$cm이다. 모든 막대의 에너지가 같은 시각에 방출되도록 각 막대 양 끝의 점화 시각을 정한다. 또한 막대 $i$에서 불이 마지막으로 닿는 지점은 그 막대의 첫 번째 끝에서 $d_i$만큼 떨어진 곳이어야 한다.

모든 점화 시각은 양의 정수여야 한다. 가능한 답 중에서 모든 에너지가 방출되는 시각이 가장 이른 답을 고른다.

첫 줄에 막대의 개수 $n$ ($1 \le n \le 10,000$)이 주어진다. 다음 $n$개의 줄에는 정수 $l_i$와 $d_i$ ($2 \le l_i \le 1,000,000$, $0 < d_i < l_i$)가 한 줄에 하나씩 주어진다. $l_i$는 막대 $i$의 길이이고, $d_i$는 첫 번째 끝에서 마지막으로 불이 닿아야 하는 지점까지의 거리이다.

$i$번째 줄에 양의 정수 $t_{i1}$과 $t_{i2}$를 출력한다. 이는 막대 $i$의 첫 번째 끝과 두 번째 끝에 불을 붙이는 시각이다.