题目描述

为了在经历了艰难的信息学和数学题之后放松一下，Elena 去玩了 Minecraft —— 一款基本单位为 $1\times1\times1$ 米方块的三维游戏。今天她想给自己的房子装一个会发光的地板。

她的地板是一个由灯块铺成的 $N\times M$ 平面。她可以手动开启某一盏灯 $(x,y)$，但当她这样做时，会同时激活所有满足

的灯 $(x',y')$。

你对 Elena 的游戏中当前一共亮着多少盏灯很感兴趣，但你只知道她手动开启了哪些灯，以及这些操作的顺序。请编写程序 redstone，在每次手动开启一盏灯之后，输出此时总共有多少盏灯被点亮。

输入格式

第一行输入四个整数 $N,M,K,Q$，表示地板的大小、灯会被联动点亮的距离，以及 Elena 手动开启灯的次数。

接下来的 $Q$ 行中，第 $i$ 行给出两个整数 $x_i,y_i$，表示 Elena 在第 $i$ 次操作中手动开启的灯的位置。

输出格式

输出 $Q$ 行，每行一个整数，表示第 $i$ 次操作结束后，被点亮的灯的总数。

数据范围

• $1\le N,M,K\le 500$
• $1\le Q\le 3\times 10^5$
• 对每个 $i$，都有 $1\le x_i\le N$，$1\le y_i\le M$

测试点

各测试点独立计分，按最佳解计分。

样例 #1

输入 #1

7 8 2 5
2 2
4 3
1 8
5 6
2 2

输出 #1

11
20
26
37
37

样例说明 #1

原题在此处配有一张示意图，展示该样例中地板上各位置灯的点亮情况。你后续补图时，可将原图插入这里。

原题中的图示对应这个样例：红色、绿色、橙色和蓝色的灯分别是在第 $1,2,3,4$ 次操作中被点亮的。注意，第 $5$ 次操作与第 $1$ 次操作完全重合，因此不会点亮任何新的灯。