B - ケーキ・カッティング (Cake Cutting) Editorial /

Time Limit: 1 sec / Memory Limit: 64 MB

問題文

E869120は, H \times Wのケーキを作った。square1001はE869120と分けるためにケーキを分割することになった。

ケーキは長方形であり, 4頂点の座標は(0, 0), (0, H), (W, 0), (W, H)である。

square1001は, 座標(0, 0)から(i, H) (1≦i≦W)または(W, i) (1≦i≦H)に向かって切る。しかし, 次の条件を満たさなければならない。

  • ケーキの上にはイチゴがN個あり, それを均等に分けなければならない。
  • ナイフがイチゴの上にくるように切るとイチゴは消えてしまうので, イチゴを1個も消滅させないように切らなければならない。
  • 整数座標に向かって切らなければならない。

そのとき, square1001が(0,0)からPに向かって切るようなPをすべて求めなさい。ただし, そのようなことができないときは-1と出力しなさい。

ただし、イチゴの面積は考えないものとします。

入力

入力は, 以下の形式で与えられる。

H W N
X_1 Y_1
X_2 Y_2
:  :
X_N Y_N

(X_i, Y_i)は, i番目のイチゴの座標である。H, W, Nについては, 問題文中に記載されている。

出力

下の出力例にしたがって辞書順で出力しなさい。解がない場合は-1と出力しなさい。ただし, 出力には余計な空白や改行を入れないこと。

制約

1≦H, W, N≦10

1≦X_i＜W, 1≦Y_i＜H

i≠j⇒(X_i,Y_i)≠(X_j,Y_j)

入力例1

5 5 2
1 3
4 2

出力例1

(2,5)
(3,5)
(4,5)
(5,3)
(5,4)
(5,5)

下のように切ることができる。

辞書式順序に従って出力する。

入力例2

5 5 5
1 1
1 3
3 3
3 4
4 3

出力例2

-1

イチゴは奇数個なので等しく分けることはできない。

入力例3

5 5 2
3 2
4 3

出力例3

-1

整数座標に向かって切ることしかできない。

問題文担当者：square1001