보안이 강화된 감옥 (Basic)

에디와 베놈의 문제는 카니지가 숙주와 함께 감옥을 탈출하면서 시작된다. 감옥이 더 안전했다면 나쁜 일은 아무것도 일어나지 않았을 것이고, 모두가 오래오래 행복하게 살았을 것이다.

경험을 바탕으로 샌퀜틴 감옥의 새 교도소장은 감옥을 재건할 때 다른 방 안에 놓이는 방, 즉 최고 보안 감방을 짓기로 했다. 샌프란시스코 법은 $n$가지 유형 중 정확히 한 가지 유형의 방만 짓도록 허용한다. $i$번째 유형은 동서 방향 변이 $a_i$, 남북 방향 변이 $b_i$인 직사각형이다(반대로는 안 된다). 방 $a_i \times b_i$는 $a_i \leqslant a_j$이고 $b_i \leqslant b_j$일 때에만 방 $a_j \times b_j$ 안에 들어갈 수 있다. 안전을 위해 외부 방과 내부 방은 반드시 서로 다른 유형이어야 한다.

안타깝게도 허용된 방 유형 중 어느 것도 다른 방 안에 들어가지 않는다. 예를 들어 $4 \times 6$, $5 \times 3$, $7 \times 1$ 크기의 방 두 개는 어느 쪽도 서로 안에 넣을 수 없다. 그래서 소장은 내부 방의 유형 $i$를 자유롭게 고를 수 있고, 외부 방에 대해서는 규칙을 조금 완화할 수 있다. 외부 방으로 유형 $j \neq i$를 고르고 $a_j \times b_j$ 방을 $a \times b$로 넓힐 수 있다($a \geqslant a_j$, $b \geqslant b_j$인 임의의 $a$, $b$를 고른다). 이때 도시에 $(a + b) - (a_j + b_j)$만큼의 돈을 내면, 유형 $i$의 방이 그 안에 들어간다.

소장은 안전을 해치지 않으면서 돈을 가능한 한 적게 쓰고 싶어 한다. 그래서 최종 선택을 하기 전에, 내부 방이 유형 $i$일 때 정부에 최소한 얼마를 내야 하는지를 $i$가 $1$부터 $n$까지인 각 경우에 대해 알고 싶어 한다.

첫 줄에 샌프란시스코에서 공식적으로 허용된 방 유형의 개수 $n$이 주어진다 ($2 \leqslant n \leqslant 2 \cdot 10^5$). 이어지는 $n$개 줄의 $i$번째 줄에는 $i$번째 유형 방의 크기를 나타내는 정수 $a_i$와 $b_i$가 공백으로 구분되어 주어진다 ($1 \leqslant a_i, b_i \leqslant 10^9$). 서로 다른 두 유형의 방은 어느 쪽도 다른 방 안에 들어갈 수 없다는 것이 보장된다.

공백으로 구분된 $n$개의 정수를 출력한다. $i$번째 정수는 내부 방이 유형 $i$일 때 최고 보안 감방을 짓는 데 필요한 최소 금액이다.