29335번 - Coloring

문제

신욱이는 10ドル^9 \times 10^9$ 크기의 커다란 격자판을 가지고 재밌는 놀이를 하고 있다.

신욱이는 처음에 색이 칠해져 있지 않은 격자판으로 놀이를 시작하며, 다음과 같은 행동을 $Q$회 반복한다.

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

신욱이가 $Q$회에 걸쳐 고른 정수 $x, y$가 주어질 때, $Q$회에 걸쳐 외친 수가 각각 무엇이었는지 알아내 보자.

입력

첫째 줄에 정수 $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$를 나타낸다.

출력

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

제한

힌트