003 - タイルふたたび (Tile2)

時間制限 8 秒 / メモリ制限 256 MB / 得点 100 / x 5 /

TLE
8sec
MLE
256MB
得点
100

問題

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

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

問 3 説明図 1

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

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

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

問 3 説明図 2

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

入力

入力は N + 1 行からなる.
1 行目には, 整数 H, W, N ( 1 ≤ H, W ≤ 109, 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 個のタイルのうちいくつのタイルが青色で, いくつのタイルが赤色かを, 空白区切りで出力せよ.

入出力例

入力例 1

2 2 4
1 1
1 2
2 1
2 2

出力例 1

2 2

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

問 3 説明図 3

入力例 2

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

出力例 2

4 3