As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
In an ancient country, there are $n \times m$ cities. The coordinate of the $(x-1)m+y$th city is $(x,y)(1 \leq x \leq n,1 \leq y \leq m)$. There are $q$ tourists. Initially, the $i$th tourist is at city $(x_i,y_i)$ and all of them want to go out and play in other cities.
Unfortunately, $K$ of the $n \times m$ cities has been controlled by terrorists, so these $K$ cities became unsafe. For safety, the tourist whose initial coordinate is $(x1,y1)$ can go to the city $(x2,y2)$ if and only if all of the city $(x,y)(\min(x1,x2) \leq x \leq \max(x1,x2),\min(y1,y2) \leq y \leq \max(y1,y2))$ is safe.
Now, for each tourist, Yuta wants to know the number of cities he can reach safely (including the initial city he stayed).
It is too difficult for Rikka. Can you help her?
In the sample, the third tourist can reach $(1,4),(2,4),(3,4),(4,4),(1,3),(2,3),(2,2),(2,1)$.