第 15 回 日本情報オリンピック　模擬予選 ３

2015年12月12日
kagamiz

問題

ミズゴロウのゴロウくんが通う JOI 高校は, ちょうど文化祭の時期である. ゴロウくんは, 今年は大きな美術作品を展示しようと頑張って作業を進めている.

ゴロウくんは, 文化祭で大きさ H × W のタイルの集まりに色を塗ったものを展示する予定である. このタイルの集まりは 1 × 1 のタイルを H × W 個集めて作られている. それぞれのタイルには, 下図に示すように, 左上が (1, 1), 右下が (H, W) という 2 組の数からなる番号が付くように順に番号付けがされている.

ゴロウくんは, 次の順序でパネルを歩きながら, 足元のパネルを塗っていく.

1. はじめに (1, 1) のタイルに右を向きながら立つ. (1, 1) のタイルを青色に塗る.
2. もし, 向いている先にタイルがあり, まだ色が塗られていなければその向きに進む. その後, 下記の手順で移動先のパネルに色を塗ったあと, 再び 2. の手順を取る. そうでなければ, 3. の手順を取る.
   • このとき, 移動前のタイルが青色なら, 移動先のタイルを赤色に塗る.
   • 移動前のタイルが赤色なら, 移動先のタイルを青色に塗る.
3. 90 度時計回りに向きを回転して 2. の手順を取る. この手順を連続で 4 回繰り返した場合, そこで移動を終了する.

上記の手順でゴロウくんが移動すると, 彼の移動した跡は下図の様に渦巻き状になる.

文化祭の前日になって, ゴロウくんは N 箇所のタイルの塗装がはがれてしまっていることに気が付いた. しかし, それぞれのタイルを何色で塗れば良いのかを忘れてしまった. ゴロウくんのために, N 箇所のタイルのうちいくつが青色のタイルで, いくつが赤色のタイルかを出力するプログラムを作成せよ.

入力

入力は N + 1 行からなる.
1 行目には, 整数 H, W, N ( 1 ≦ H, W ≦ 10⁹, 1 ≦ N ≦ 1000 ) が空白区切りで書かれている.
1 + i ( 1 ≦ i ≦ N ) 行目には, 整数 Ri, Ci ( 1 ≦ Ri ≦ H, 1 ≦ Ci ≦ W ) が空白区切りで書かれている. これは, ゴロウくんが位置 (Ri, Ci) のタイルの色を忘れてしまったということを表す. ここで i ≠ j なら Ri ≠ Rj または Ci ≠ Cj が保証されている.

出力

1 行に, N 個のタイルのうちいくつのタイルが青色で, いくつのタイルが赤色かを, 空白区切りで出力せよ.

入出力例

2 2 4
1 1
1 2
2 1
2 2



  

64 19 7
37 8
11 9
44 18
21 15
12 21
55 3
64 19
  

2 2
   

4 3
   

入出力例 1 で与えられるタイルに正しく色を塗った場合, 下図の様になる.

※各入出力例のデータは，右クリック等によりファイルに保存して利用可能です．