운전 연습

장롱 면허를 보유한 시은이는 수직선 위에서 운전 연습을 하려고 한다. 시은이는 원점에서 출발하여 항상 양의 방향으로 이동할 것이다. 자동차는 단위 거리 1만큼 이동할 때마다 전기 1kWh를 소모하며, 전기를 소모하는 방법은 이동하는 것뿐이다. 처음 자동차에는 전기가 없으며, 전기가 없는 자동차는 충전하기 전까지 이동할 수 없다.

수직선 위에는 0번부터 $N$번까지 총 $N + 1$개의 충전소가 있다. $i$번 충전소는 수직선 위의 점 $A_i$에 있으며, 방문하면 $F_i$kWh의 전기를 충전할 수 있다. 0번 충전소를 제외한 충전소 중 하나에는 장난꾸러기 마법사가 숨어 있다. 시은이가 그 충전소에 도착하면, 마법사는 그보다 이전에 있는(즉, 원점에 더 가까운) 충전소 중 하나로 시은이를 순간이동시킨다. 순간이동할 충전소는 시은이가 고를 수 있다. 순간이동에는 전기가 소모되지 않으며, 마법사는 한 번 장난을 치면 다시는 장난을 치지 않는다.

마법사가 장난을 칠 때에는 충전할 수 없으며, 순간이동 후 다시 만난 충전소에서는 충전할 수 있다. 예를 들어 시은이가 3번 충전소에서 마법사를 만나고 1번 충전소로 순간이동하기로 했다면, 0 → 1 → 2 → (마법사의 장난으로 3번에서는 충전하지 못함) → 1 → 2 → 3 → … 순서로 충전할 수 있다.

시은이가 각 충전소에서 마법사를 만났다고 가정할 때, 자동차가 원점으로부터 가장 먼 위치에서 방전되려면 몇 번 충전소를 선택해야 하는지 알아보자.

첫째 줄에 0번 충전소를 제외한 충전소의 수 $N$이 주어진다.

다음 $N + 1$개의 줄에는 0번 충전소부터 번호 순서대로 각 충전소의 정보가 한 줄에 하나씩 주어진다. $i$번 충전소의 정보는 $A_i$와 $F_i$이며, 공백으로 구분된다.

총 $N$줄을 출력한다. $i$번째 줄에는 두 정수 $x_i$와 $y_i$를 공백으로 구분하여 출력한다. ($1 \le i \le N$)

마법사를 만나지 않은 채로 $i$번 충전소에 도달할 수 없다면

• $x_i$와 $y_i$는 모두 -1이다.

그 밖의 경우

• $x_i$는 $i$번 충전소에서 마법사를 만났을 때 시은이가 선택해야 할 충전소의 번호이다.
• $y_i$는 $x_i$번 충전소로 순간이동한 뒤 다시 $i$번 충전소로 돌아왔을 때, 자동차에 충전된 전기의 변화량이다.
• 조건을 만족하는 $x_i$가 여러 개라면 가장 큰 값을 출력한다.

• $1 \le N \le 200{,}000$
• $A_0 = 0$
• $A_0 < A_1 < A_2 < \cdots < A_N \le 10^{12}$
• $1 \le F_i \le 10^6$ ($0 \le i \le N$)
• 자동차에는 무한히 많은 전기를 충전할 수 있다.
• 입력으로 주어지는 수는 모두 정수다.