時間制限 : sec, メモリ制限 : KB
English / Japanese  

Problem E: Legend of Storia

ストーリア王国にはその昔にいたという偉大な工匠エスによって作られた「 Perfect Sphere "完全な球"」という作品が宝として代々王宮に伝わってきた。エスはこの作品に関する説明として謎の数値を記録した紙を残していた。多くの研究の成果として、それが座標値であることがわかったが一体何の座標なのか結論は出なかった。

さて、あなたはエスがまだ生きていた時代の人間である。工匠エスが残した数値とは以下に述べるようなものだ。エスは球の中に、そこで運動し続ける物体を入れた。驚くべきことにこれは永久に止まらずに運動しつづける剛体である。その物体は常に球面に接しつつ回転を行う。この数値はその物体と球面の接点の座標値なのだ。しかし3次元ではない。物体はプレート状になっており、単純な多角形だ。ここで単純な多角形とは自己交差しない多角形をいう。これはつねに球の大円に接しながら反時計回りに回転している。今その大円を xy 平面(二次元直交座標系で、x軸の正方向が右向きで、y軸の正方向が上向き)において原点を中心とする円 O として考えよう。このプレートは一連の運動のはじめ、一点で円 O に接している。そしてその一点を支点として反時計回りの方向に回転する。このとき円 O に新たに接する点 X ができる。するとこのプレートは、今度はその点Xを新たな支点として先と同様な反時計回りの回転を行うのだ。もし同時に複数の点が新たに接する場合は、今接している点から円周上を時計回りにたどったとき最も遠い接点が新たな支点 X となる。

エスは優秀なアシスタントであるあなたにこのプレートが運動を始めてから新たに円 O 上で支点となる点の x 座標と y 座標を順番に Q 個列挙する仕事を頼んだ。以下の図はプレートが円内を運動する様子を順に示す。
1

2

3

4

Input

入力は複数のデータセットからなる。
ひとつのデータセットは以下の形式で与えられる。

N R Q
x1 y1
x2 y2
...
xN yN

N, R, Q はそれぞれ整数で、多角形の頂点の数と半径の大きさと座標の列挙数を表す。
続くN行に、2N 個の整数が与えられる。 これは座標( xk , yk )であり、円内の多角形の頂点を示す。(1≤kN)

    入力において以下のことを仮定して構わない。
  • 頂点は反時計回りで与えられる。
  • 3つの点は一直線上に存在しない。
  • N-1 個の頂点は原点から距離 R 未満の円内に与えられる。それ以外の1個の頂点は必ず原点から距離 R に与えられる。
  • N=R=Q=0のとき入力の終了を示す。

Constraints

データセットの数は400以下である。
3≤N≤25
1≤R≤1000
0≤Q≤100

Output

それぞれのデータセットにつき、以下の形式で Q 行に(Px Py:実数)を出力せよ。

Px1 Px1
Px2 Py2
...
PxN+1 PyN+1

この値はPxi, Pyi(1≤iQ)に対するジャッジ出力の値Txi,Tyi(1≤iQ)があり、 |Txi-Pxi|≤0.0001 と |Tyi-Pyi|≤0.0001 を満たせば良い。

Sample Input

4 10 8
0 -10
3 -7
0 -4
-3 -7
0 0 0

Output for the Sample Input

-4.146082488326 -9.100000000000
-7.545870128753 -6.562000000000
-9.587401146004 -2.842840000000
-9.903199956975 1.388031200000
-8.436422775690 5.369056784000
-5.451089494781 8.383652146880
-1.484560104812 9.889190123322
2.749190104024 9.614673877565