問題文

ギガコード君は家を買いました．この家は，左右に $H$ 分割，前後に $W$ 分割された合計 $H \times W$ 個の区画に分かれています．そのうち左から $i$ 番目，前から $j$ 番目のマスを $(i, j)$ で表します．

そのうち $N$ 個の区画には物が置かれています．$i$ 個目の物は，区画 $(r_i, c_i)$ 全体を占めています．また，これらの物が動くことはありません．

ギガコード君は，この家にクローゼットを $1$ つ設置することにしました．クローゼットは家の外壁に平行な長方形でなければならず，クローゼットのある区画に物が置かれていてはなりません．しかし，地震が起きた時にクローゼットが動くと良くないので，次の条件を満たす置き方のうち $1$ つを選ぶことにしました．

• クローゼットを向きを変えずにどんな方向に動かそうとしても，物や家の外壁に当たって動かせない．

例えば，次のようなクローゼットの配置ができます．

しかし，条件を満たさないクローゼットの配置はできません．

条件を満たすようなクローゼットの配置はいくつあるか求めてください．

制約

• $1 \leq H \leq 5 \ 000$
• $1 \leq W \leq 5 \ 000$
• $0 \leq N \leq 201 \ 900$
• $1 \leq r_i \leq H$
• $1 \leq c_i \leq W$
• $N$ 個の物はすべて異なる区画に置かれている
• 入力はすべて整数

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

1. (2 点) $H = 1, W = 1$
2. (11 点) $H = 1, W \leq 25$
3. (11 点) $H \leq 25, W \leq 25$
4. (19 点) $N \leq 10$
5. (16 点) $H \leq 100, W \leq 100$
6. (17 点) $H \leq 350, W \leq 350$
7. (19 点) $H \leq 1500, W \leq 1500$
8. (5 点) 追加の制約はない．

注意

入力のサイズが大きいので、高速な入出力（C++ の場合 scanf/printf など）を使うことが推奨されています．