시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 133 59 55 58.511%

문제

준원이는 여자친구를 만들 시나리오를 진지하게 세우고 있다.

먼저, 지나가던 아름다운 여성 분이 준원이에게 길이가 N인 수열 arr을 정렬해달라고 부탁한다. 그리고 준원이는 #include <algorithm>을 선언한 뒤 std::sort(arr, arr+N);을 사용해 시간복잡도 O(N log N)으로 멋지게 정렬해준다. 그리고, 사랑에 빠진다.

준원이는 실제로 이 상황에 마주친다. 하지만 그가 받은 수열은... 수열의 원소가 정해져 있지 않았다!

314 ± 25, 255 ± 140, ...

실제 수열의 각 원소는 받은 수열의 오차범위 내의 어떤 실수든 될 수 있다. 예를 들어, 첫번째 수인 314 ± 25는 314 - 25 = 289 이상 314 + 25 = 339 이하의 임의의 실수가 될 수 있다.

그녀는 길이 N의 수열 a1 ± b1, ..., aN ± bN을 준원이에게 주고, 수열을 정렬한 이후 각각의 수가 몇 번째에 가 있을지를 알고 싶다. 물론, 수열이 범위 안에서 어느 수로 결정되는가에 따라 답이 바뀔 수 있기 때문에, 각각의 수가 있을 수 있는 인덱스의 범위를 구하고 싶다. 만약 같은 수가 여러 개 있다면, 그 수들은 어떤 순서로 있든 무관하다. 준원이가 연애를 할 수 있도록, 여러분이 대신 그녀의 문제를 해결해 주자.

입력

첫째 줄에는 준원이가 받은 수열의 길이 N이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 준원이가 받은 수열이 주어진다. i번째 줄에는 준원이가 받은 수열의 i번째 원소 ai ± bi를 나타내는 두 정수 ai와 bi가 공백을 사이에 두고 주어진다.

출력

총 N개의 줄에 걸쳐서 출력한다. i번째 줄에는 수열을 정렬한 후, 수열의 i번째 원소가 있을 수 있는 인덱스의 최솟값과 최댓값을 공백을 사이에 두고 출력한다. 

수열의 인덱스는 1부터 시작한다.

제한

  • 2 ≤ N ≤ 500,000
  • 각 1 ≤ i ≤ N에 대해, ai, bi는 정수이고, -109 ≤ ai ≤ 109, 0 ≤ bi ≤ 109.

예제 입력 1

3
10 20
40 15
70 15

예제 출력 1

1 2
1 3
2 3

예제에서, 수열의 수들을 차례로 x1, x2, x3이라 하자. -10 ≤ x1 ≤ 30, 25 ≤ x2 ≤ 55, 55 ≤ x3 ≤ 85이다. 만약 (x1, x2, x3) = (28, 25, 70)이라면, x2가 첫번째, x1이 두번째, x3이 세 번째 수가 된다. 또, (x1, x2, x3) = (15, 55, 55)라면 x1이 첫번째 수이고, x2, x3은 차례대로 두번째, 세번째 수이거나 차례대로 세번째, 두번째 수가 된다. 이밖의 어떤 경우에도, x1은 1, 2번째 수이고, x2는 1, 2, 3번째 수이고, x3은 2, 3번째 수이다.