보안 강화 감옥

Eddie와 Venom의 문제는 Carnage가 숙주와 함께 감옥을 탈출하면서 시작된다. 감옥이 더 안전했다면 나쁜 일은 일어나지 않았고, 모두가 오래오래 행복하게 살았을 것이다.

이 경험을 바탕으로 샌퀜틴 교도소의 새 소장은 재건하는 교도소에 특별 보안 감방을 짓기로 했다. 이 감방은 다른 방 안에 놓이는 방이다. 샌프란시스코 법은 $n$가지 종류 가운데 정확히 한 종류의 방만 짓도록 허용한다. $i$번째 종류는 동서 방향 변이 $a_i$, 남북 방향 변이 $b_i$인 직사각형이다 (방향을 뒤집을 수 없다).

방 $a_i \times b_i$는 $a_i \le a_j$이고 $b_i \le b_j$일 때에만 방 $a_j \times b_j$ 안에 넣을 수 있다. 안전을 위해 바깥 방과 안쪽 방은 반드시 서로 다른 종류여야 한다 (크기가 달라야 할 필요는 없다).

당연히 아무 두 방이나 서로 안에 넣을 수 있는 것은 아니다. 예를 들어 $4 \times 6$ 방과 $5 \times 3$ 방은 $4 < 5$이지만 $6 > 3$이므로 서로 안에 넣을 수 없다. 따라서 소장이 안쪽 방을 반드시 $i$번째 종류로 하고 싶다면, 예외적으로 $j \ne i$인 임의의 종류 $j$를 골라 방 $a_j \times b_j$를 $a \times b$로 넓힐 수 있다 (즉, $a \ge a_j$, $b \ge b_j$인 임의의 $a$, $b$를 고른다). 이때 시 정부에 $(a + b) - (a_j + b_j)$만큼 돈을 내고, 그 뒤에 $i$번째 종류의 방이 그 안에 들어가야 한다.

소장은 돈을 최대한 적게 쓰고 싶지만 안전을 위험에 빠뜨리고 싶지도 않다. 그래서 최종 선택을 하기 전에, 안쪽 방이 $i$번째 종류일 때 정부에 최소 얼마를 내야 하는지를 $i$가 1부터 $n$까지인 각 경우에 대해 알아보려 한다.

첫 줄에 샌프란시스코에서 공식적으로 허용된 방 종류의 수 $n$이 주어진다 ($2 \le n \le 2 \cdot 10^5$).

이어지는 $n$개의 줄에 $i$번째 종류 방의 크기 $a_i$와 $b_i$가 공백으로 구분되어 주어진다 ($1 \le a_i, b_i \le 10^9$). 종류마다 크기가 서로 다르다고 보장되지 않는다. 두 종류의 크기가 같으면 그 종류의 방들도 서로 안에 넣을 수 있다.

$n$개의 정수를 공백으로 구분하여 출력한다. $i$번째 정수는 안쪽 방이 $i$번째 종류인 보안 감방을 짓기 위해 내야 하는 최소 금액이다.