You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小明最近在玩一个古老的游戏祖玛。他越玩越觉得这个这个游戏像是一个蛇形数组。

我们把这个蛇形数组抽象出来，搞这么一个无穷大的数组

..... 13
5 4 3 12
6 1 2 11
7 8 9 10

这个数组的坐标原点是$(0,0)$，值是$1$。此处第一维代表行，第二维度代表列，例如数字$2$在坐标$(0,1)$。

现在，小明想对这个数组进行如下一种操作：

x y：把当前第$x$行第$y$列的数字打掉，然后比其大的数字，依次挪到恰好比它小一点的位置上。

例如，上述矩阵中，我们打掉了$(1,0)$位置上的$4$，则矩阵会变成：

..... 14
6 5 3 13
7 1 2 12
8 9 10 11

小明的问题很简单，告诉你$Q$次操作，请告诉小明，每次操作打掉了数字几。

输入格式

第一行输入$Q$。

接下来$Q$行，每行输入两个整数$x,y$。

输出格式

对于每一行，输出一个答案。

5
0 0
0 0
0 0
0 0
0 0

1
2
3
4
5

10
0 1
1 0
1 1
2 0
3 0
4 0
5 5
10 10
15 25
-25 0

2
5
4
18
38
66
97
388
2449
2585

数据范围

对于30%的数据：$|x,y|\leq 20$。

对于另25%的数据：$Q\leq 5000$。

对于另10%的数据：保证询问的$\max(|x|,|y|)$单调递增。

对于100%的数据：$Q\leq 2\times 10^5,|x,y|\leq 10^8$。