问题

高桥君正在玩一个游戏。这个游戏在一个无限扩展的方格上进行，可以在水平和垂直方向上移动。每个方格是一个正方形，每条边都平行于东西或南北方向。每个方格都有一个分配的数字对 ($0$, $0$)，并且在从该方格向东移动 $x$ 格（当 $x < 0$ 时向西移动 $-x$ 格）并向北移动 $y$ 格（当 $y < 0$ 时向南移动 $-y$ 格）之后的方格中有一个数字对 ($x$, $y$)。

方格上有 $W$ × $H$ 个金块。这些金块分别放置在满足 $1$ ≦ $p$ ≦ $W$ 和 $1$ ≦ $q$ ≦ $H$ 的所有方格 ($p$, $q$) 中，每个方格有 $1$ 个金块。此外，其中恰好有 $N$ 个金块回收装置。装置被编号为 $1$ 到 $N$。对于任意两个方格 ($a$, $b$) 和 ($c$, $d$)，如果两个方格都有装置，则 $a≠c$ 且 $b≠d$。此外，多个装置不会位于同一个方格中。最开始，没有金块回收装置正在运行。

一旦金块回收装置开始运行，它将首先回收装置所在方格中的金块。然后，它可以通过向东、向西、向南和向北四个方向伸展起重机来进一步回收金块。由于起重机的特性，放下起重机的位置没有金块，并且回收区域中必须连续存在金块。换句话说，如果方格 ($x$, $y$) 有起重机，则只有在满足以下条件时才能放下起重机并回收金块。

• 向东回收：选择满足以下条件的整数 $p$。然后回收满足 $x+1$ ≦ $i$ ≦ $p-1$ 的所有方格 ($i$, $y$) 中的金块。

  • 条件：$p$ > $x+1$，对于满足 $x+1$ ≦ $i$ ≦ $p-1$ 的所有方格 ($i$, $y$)，方格中有金块，并且方格 ($p$, $y$) 中没有金块。

• 向西回收：选择满足以下条件的整数 $p$。然后回收满足 $p+1$ ≦ $i$ ≦ $x-1$ 的所有方格 ($i$, $y$) 中的金块。

  • 条件：$p$ < $x-1$，对于满足 $p+1$ ≦ $i$ ≦ $x-1$ 的所有方格 ($i$, $y$)，方格中有金块，并且方格 ($p$, $y$) 中没有金块。

• 向南回收：选择满足以下条件的整数 $q$。然后回收满足 $q+1$ ≦ $j$ ≦ $y-1$ 的所有方格 ($x$, $j$) 中的金块。

  • 条件：$q$ < $y-1$，对于满足 $q+1$ ≦ $j$ ≦ $y-1$ 的所有方格 ($x$, $j$)，方格中有金块，并且方格 ($x$, $q$) 中没有金块。

• 向北回收：选择满足以下条件的整数 $q$。然后回收满足 $y+1$ ≦ $j$ ≦ $q-1$ 的所有方格 ($x$, $j$) 中的金块。

  • 条件：$q$ > $y+1$，对于满足 $y+1$ ≦ $j$ ≦ $q-1$ 的所有方格 ($x$, $j$)，方格中有金块，并且方格 ($x$, $q$) 中没有金块。

对于每个方向，如果不存在满足条件的 $p$ 或 $q$，则无法伸展起重机。

此外，对于每个方向，如果可以回收金块，则必须回收。下面是满足条件的回收方法的一个示例。注意，在以下图示中，用 M 符号表示装置，并用粗框表示可回收范围。

![](http://abc008.contest.atcoder.jp/img/abc/008