小P最近在玩一个叫R6的游戏，在游戏地图相当于一个n*m的矩阵。游戏中玩家需要击杀他所在的行和列中最高的NPC。

不过这种玩法显然难不倒聪明的小P，于是他开始想计算有多少人是他所在排第x高并在他所在列是第y高的。

小P为了腾出更多时间玩R6，所以他请你帮他算这个问题。但是小P太皮了，他可能在矩阵的任何一个点上出现，所以你要对每一组询问计算小P可能出现的所有点的答案。

他可能有很多询问，你需要快速回答所有的询问。 

输出共q行，每行一个整数，表示第i组询问的答案。

对于第一组询问，(1,1),(2,2),(3,3)是符合条件的。
对于第二组询问，(2,1),(3,2)是符合条件的。

身高保证在[1,n∗m]中，并且每个整数出现且仅出现一次。

对于20%的数据，n,m,q≤100。

对于另外10%的数据，n,m≤100,q≤100000。

对于另外20%的数据，n,m,q,≤400。

对于全部的数据，n,m≤1000,q≤500000。