색칠하기

신욱이는 $10^9 \times 10^9$ 크기의 커다란 격자판으로 놀이를 한다. 처음에는 격자판에 칠해진 칸이 없다.

신욱이는 다음 행동을 $Q$번 반복한다.

1. $1$ 이상 $10^9$ 이하의 정수 $x$, $y$를 고른다.
2. $1 \le i \le x$, $1 \le j \le y$를 만족하는 모든 격자점 $(i, j)$를 검게 칠한다. 이미 검게 칠해진 격자점에 다시 칠해도 색은 변하지 않는다.
3. 현재 검게 칠해진 격자점의 수를 외친다.

신욱이가 $Q$번에 걸쳐 고른 정수 $x$, $y$가 주어질 때, 각 행동에서 외친 수를 구하시오.

첫째 줄에 정수 $Q$가 주어진다. ($1 \le Q \le 300\,000$)

둘째 줄부터 $Q$개의 줄에 걸쳐 정수 $x_i$와 $y_i$가 공백으로 구분되어 주어진다. ($1 \le x_i, y_i \le 10^9$)

$x_i$와 $y_i$는 신욱이가 $i$번째 행동에서 고른 $x$와 $y$를 each 나타낸다.

신욱이가 외친 수들을 순서대로 $Q$개의 줄에 걸쳐 출력한다.