こんばんは，選手諸君．

a と d が互いに素な正の整数ならば， a から始まり d ずつ増える 等差数列 a, a + d, a + 2d, a + 3d, a + 4d, ... には無限個の素数が含まれる． このことはディリクレの算術級数定理として知られている． ガウス(Johann Carl Friedrich Gauss, 1777 - 1855)が予想していたことを， 1837年に ディリクレ(Johann Peter Gustav Lejeune Dirichlet, 1805 - 1859)が 証明した．

たとえば， 2から始まり3ずつ増える等差数列

2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, ...

は，無限個の素数

2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, ...

を含む．

そこで君の使命だが， 与えられた正整数 a と d と n に対して， この等差数列に含まれる n 番目の素数を求める プログラムを書くことにある．

例によって，君もしくは君の仲間が疲れはて，あるいは混乱しても， 当局はいっさい関知しないからそのつもりで． なお，この審判システムは3時間で自動的に停止する． 成功を祈る．

入力はデータセットの並びである． データセットは， 1文字の空白で区切られた三つの正整数 a と d と n とからなる行である． a と d は互いに素である． a ≦ 9307 かつ d ≦ 346 かつ n ≦ 210 と仮定してよい．

入力の終わりは，1文字の空白で区切られた三つのゼロからなる行で示される． これはデータセットではない．

出力は入力データセットと同数の行で構成されなければならない． 各行は一つの整数を含まなければならない． 余計な文字を含めてはならない．

データセット a, d, n に対応する出力の整数は， a から始まり d ずつ増える 等差数列に含まれる素数のうちで n 番目のものでなくてはならない．

なお，この入力条件の下で， 結果は必ず 10⁶ (百万)より小さいことがわかっている．

367 186 151
179 10 203
271 37 39
103 230 1
27 104 185
253 50 85
1 1 1
9075 337 210
307 24 79
331 221 177
259 170 40
269 58 102
0 0 0

92809
6709
12037
103
93523
14503
2
899429
5107
412717
22699
25673

日本の鉄道会社RJ貨物は，横浜羽沢に操車場を完成させた． 操車場の配線を図B-1に示す．

図 B-1: 操車場の配線

貨物列車は2両以上72両以下の貨車を連結している．貨車の種類は26あり， その種類をa〜zの英小文字1文字で表す． 同じ種類の貨車同士は互いに区別されず， また個々の貨車の向きも区別されない． したがって，2文字以上72文字以下の英小文字の並びで1つの列車の編成が完全に表せる．

操車場に到着した列車は， (storage linesに入る直前に)任意の連結箇所で2つに分割される． 続いてそれぞれの部分は，その必要があれば(reversal lineを使って)前後反転される． 最後にこれら2つの部分を任意の順序で再び連結することで， 最終的な編成を作る．前後反転は，部分ごとに行っても行わなくてもよい．

たとえば，到着時の編成が「abcd」のとき， 編成の分割のしかたは3:1，2:2，1:3のいずれかである． 分割のしかたそれぞれについて， 構成可能な最終編成は次のようになる(「+」は最後の連結位置を示す):

  [3:1]
    abc+d  cba+d  d+abc  d+cba
  [2:2]
    ab+cd  ab+dc  ba+cd  ba+dc  cd+ab  cd+ba  dc+ab  dc+ba
  [1:3]
    a+bcd  a+dcb  bcd+a  dcb+a

重複を除いて数えると，12種類の編成が作り出せることになる．

到着した列車の編成が与えられたとき， 上記の操車場によって構成可能な，互いに異なる編成の数を回答せよ．

入力全体は以下の形式をしている．

データセット数 = m
データセット1
データセット2
...
データセットm

各データセットは入場してくる列車を表す， 2個以上72個以下の英小文字のみを含む1行の文字列である．

各データセットについて， 編成可能な列車の種類数をそれぞれ1行として出力しなさい． 出力は他の文字を含んではならない．

4
aa
abba
abcd
abcde

1
6
12
18

六角沼は不思議な沼で，正六角形の窪みが整然と並ぶ．この沼をゆったり這い まわる六角大蛇(ろっかくおろ ち)は，環境に適応して正六角形の節が並んだ蛇．窪み ひとつに節ひとつ．

六角大蛇が這うときには，いくつかの節を今ある窪みから隣の窪みに移す．体 を分断するわけにはいかないので，動く前に隣同士だった節は，動いた後も隣 同士でなくてはならない．ある節を動かすとき，すぐ隣の節はその動きを支え るので，一緒には動かせない．隣り合っていない節ならいくつでも同時に動か せる．

少し考えてみれば節を動せる先は，体の両端でせいぜい2箇所の窪み，体の中 間の節ではせいぜい1箇所しかないのがわかるだろう．

たとえば，障害物がないときには六角大蛇は図C-1に左から右に示すように体を よじらせながら前進できる．8個の節のうち4個ずつを一度に動かし，4ステップ かけてちょうど1コマ前進したことになる．もっともこいつらはヨコバイガラ ガラヘビみたいに，横に這う方が得意なのだが．

図 C-1: 前進する這い方

六角大蛇の皮膚はねばついていて，本来隣り合っている以外の節が隣の窪みに 来ると (図C-2) 互いに癒着してしまい，大蛇はあえない最期を遂げる．もちろ んひとつの窪みに節をふたつ入れることはできない．だからますます大蛇の動 きはままならない．腹ペコでも，頭のすぐ隣の窪みにある食べ物にありつくの に苦労することもある．

図 C-2: 死んでしまう場合

六角沼には，ところどころに岩がある．岩はそれぞれ窪みひとつの中に収まっ ていて，六角大蛇は岩とは癒着しないが，岩に乗り上げることはできない．岩 のある窪みを避けるために大蛇の動きは制約されるが，やつらは沼の地形をよ くわきまえていて，一番早く行ける経路を考えて通る．

あなたは科学者チームを率いて，この沼と大蛇の学術調査にあたることとなっ た．調査を完遂することも大事だが，人的損失は許されない．あなたの仕事は， いつまでに科学者のいる窪みに人食いの大蛇が頭（先頭の節）を動かしてこら れるかを見積もることだ．頭以外の胴体の節にはまったく危険がなく，ハイテ ク非粘着スーツを着た科学者は大蛇の胴体と同じ窪みの中にいられる．

入力はいくつかのデータセットが順に並んだもので，入力の終わりはゼロひと つだけの行で示される．データセット数が10を超えることはない．

各データセットの形式は以下のようなものである．

大蛇の節の数 (=n)
x₁ y₁
x₂ y₂
...
x_n y_n
沼の岩の個数 (=k)
u₁ v₁
u₂ v₂
...
u_k v_k
X Y

各データセットの先頭行には六角大蛇の持つ節の個数 n を表す整数が 記されており，これは2以上で8を超えることはない．これに続く n 行 には各々ふたつの整数 x および y がひとつの空白を区切りと して置かれ，大蛇の各節の座標を意味する．各行は，大蛇の頭から尻尾までの 節の初期位置をこの順に示す．

データセットの次の行は沼の岩の個数 k を表し，これは100を超えない 負でない整数である． これに続く k 行には，各々岩の位置を表すふた つの整数 u および v がある．

最後にふたつの整数 X と Y の行が来て，これは大蛇のゴール 地点，すなわち科学者のいる位置を示す．最初はここには大蛇の頭はない．

座標を表す x, y, u, v, X, Y はいずれも −999999 以上 999999 以下 である．同じ行のふたつの整数は空白ひとつで区切られる．入力には数字，マ イナス記号，ふたつの整数を区切る空白以外の文字はない．位置を表す座標系 は図 C-3 に示すようなものである．

図 C-3: 座標系

各データセットについて，大蛇がゴール地点までその頭を到達させるのに最小 限必要なステップ数を表す十進数ひとつを含む1行を出力せよ．出力行には他の いかなる文字も含んではならない．

六角大蛇は20ステップ以内にゴールに到達できると仮定してよい．

3
2 -2
2 -1
1 0
1
0 2
0 0
4
2 -2
2 -1
2 0
3 0
2
1 -1
0 2
0 0
8
-6 0
-5 0
-4 0
-3 0
-2 0
-1 0
0 0
1 0
1
-1 1
0 0
6
2 -3
3 -3
3 -2
3 -1
3 0
2 1
3
1 -1
1 0
1 1
0 0
3
-8000 4996
-8000 4997
-8000 4998
2
-7999 4999
-8001 5000
-8000 5000
8
10 -8
9 -7
9 -6
9 -5
9 -4
9 -3
9 -2
9 -1
0
0 0
0

3
9
18
18
19
20

MM-21星でもオリンピック以来カーリングが流行している. しかし, そのルールは地球のものとはすこし異なっており, マス目状の氷の盤上で石を一つだけ使って行われる. スタート位置からゴール位置まで石を到達させる移動回数の少なさを競うのである.

図 D-1 に盤面の例を示す. 盤上のマス目には障害物が配置されていることがある. 盤面には, スタートとゴールという特別なマスが一つずつあり, そこには障害物はない. (スタートとゴールが一致することはない.) 滑りはじめた石は障害物がないかぎりどこまでも進んでいくので, ゴールに到達させるには, 障害物を利用していったん石を止め, あらためて滑らせてやる必要もあろう.

図 D-1: 盤面の例 (S: スタート, G: ゴール)

石の動きは以下の規則に従う:

• ゲームの開始時に, 石はスタートで止まっている.
• 石の動きは x, y 方向に限る. ななめには動けない.
• 止まっている石は, 滑らせることによって動き出す. その時の方向は, すぐ次のマスに障害物がない方向ならどちらでもよい(図 D-2(a)).
• 動き出した石は, 次のいずれかが起こるまで, 同じ方向に動き続ける.
  • 障害物にぶつかった場合(図 D-2(b), (c)).
    • 石は障害物の一つ手前のマスで止まる.
    • 障害物は消滅する.
  • 盤外に出た場合.
    • 失敗でゲームは終わる.
  • ゴールの上に来た場合.
    • そこで石は止まり, 成功でゲームは終わる.
• 1 回のゲーム中の滑らせる回数の最大は 10 である. この回数で ゴールに石を到達させることができない場合, 失敗でゲームは終わる.

図 D-2: 石の動きの例

以上の条件のもとで, スタート位置にある石をゴール位置に到達させることが できるか, できるなら最小何回滑らせればよいかを知りたい.

図 D-1 に示す初期配置では 4 回で石をスタート位置からゴール位置に動かすことができる. そのときの経路を図 D-3(a) に示す. なお, 石がゴールに到達した時点での盤面は図 D-3(b) のように変化している.

図 D-3: 図 D-1の解と終了時の盤面

入力はデータセットの並びである. 入力の終わりは, 一つの空白で区切られた二つのゼロからなる行で示される. データセット数が100を超えることはない.

各データセットは次のような形式をしている:

盤の幅(=w) 盤の高さ(=h)
盤面の1行目
...
盤面のh行目

盤の幅と高さは次の条件を満たす: 2 <= w <= 20, 1 <= h <= 20.
盤面の各行には, w個の数字が空白一つをはさんで並んでいる. その数字は対応するマス目の状態を示している.

0	何もないマス
1	障害物
2	スタート位置
3	ゴール位置

図 D-1 に対応するデータセットの記述は以下のようになる:

6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1

各データセットが指定する盤面について, スタート位置にある石をゴール位置に到達させるまでに滑らせる 回数の最小値を, 十進の整数値でそれぞれ1行に出力せよ. そのような移動ができない場合には, -1 を出力せよ. 各出力行はこの数値以外の文字を含んではならない.

2 1
3 2
6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1
6 1
1 1 2 1 1 3
6 1
1 0 2 1 1 3
12 1
2 0 1 1 1 1 1 1 1 1 1 3
13 1
2 0 1 1 1 1 1 1 1 1 1 1 3
0 0

1
4
-1
4
10
-1

西暦2300年，宇宙連邦共和国の生命科学局では，全宇宙生物のゲノム配列を解読し， ゲノムデータベースを構築する野心的なプロジェクトを開始した． 長年にわたる研究の結果，いかなる種のゲノムも高々26種類の分子(AからZで表す)からなることがわかっている．

データベースに格納したいのは．英大文字からなる単なる文字列である． ただし，宇宙生物のゲノム配列は，一般に多くの繰り返しを含んでおり， 非常に長くなりうる． そこで，ストレージの有効利用のため，文字列 seq の N 回の繰り返しを，N(seq)と圧縮して記す． ここで，N は 2 以上の自然数であり，seq の長さは 1 以上である． また，seq が 1 文字 c の場合には，さらに括弧を省略して Nc と記しても良いことにする．

たとえば，

ABABABABXYXYXYABABABABXYXYXYCCCCCCCCCC

というゲノム配列の断片なら，まず，先頭部分の ABABABAB を圧縮表現に置き換え

4(AB)XYXYXYABABABABXYXYXYCCCCCCCCCC

と記すことができる． 続く XY, AB, C の繰り返しも同様に置換すると

4(AB)3(XY)4(AB)3(XY)10C

となる． C は1文字なので括弧を省略した． 最後に，4(AB)3(XY) の繰り返しも圧縮表現に置き換えると

2(4(AB)3(XY))10C

を得る． この例からわかるように，括弧は多重にネストしてもかまわない．

あなたの仕事は，圧縮されたゲノム配列を復元するプログラムを作ることである．

入力は複数の行から構成され，各入力行には文字列 s と整数 i が含まれる． s と i は空白1個で区切られる．

s は，上で述べた方法でゲノム配列を表したものであり，最短1文字， 最長100文字と仮定してよい． しかし，もちろん，s が表現するゲノム配列の長さは， 100文字よりもはるかに長い可能性がある． s 中に出現する繰り返し回数を表す自然数は， 高々1,000と仮定してもかまわない．

i は 0 以上100万以下である．

最後の入力行の直後に，空白で区切られた 2 個の 0 からなる行が置かれ， 入力の終わりを表す．

各入力行に対して，s が表現するゲノム配列の i 番目の文字を含む行を出力しなさい． ただし，ゲノム配列の長さが不足して i 番目の文字がない場合には， 0 のみを含む行を出力すること． これら以外の文字が出力行に含まれないようにすること． なお，インデックスは 1 ではなく 0 から始まる． したがって，列の先頭の文字は，0 番目である．

ABC 3
ABC 0
2(4(AB)3(XY))10C 30
1000(1000(1000(1000(1000(1000(NM)))))) 999999
0 0

0
A
C
M

昔, 横浜近くの広場に何本かのまったく同じ大きさの円柱が垂直に立っ ていた (図 F-1). 日中, 太陽の動きに従って, 円柱の影は地面 の上を動いた. 円柱はとても高かったので, その影は長かった. 図 F-2はその様子を真上から見たものである.

これらの円柱群の影の幅を最小あるいは最大にする太陽の方向が古くからの財宝に 関する秘密を解く重要な鍵を与えると言われていた.

図 F-1: 円柱群


図 F-2: 円柱群(図 F-1)とその影を真上から見た図

一つの円柱だけを考えると, その影の幅は円柱底面の円の直径に等し い. しかし, ある円柱の影が別の円柱の影に重なることがあるので, 太陽の方向に従って, 影全体 (個々の円柱の影の合併) の幅は変化する.

図 F-2のような円柱の配置の場合, 影全体の幅が最小になるときの太陽の方向を図 F-3に示す.

図 F-3: 影全体の幅が最小になる太陽の方向

影全体の幅が最大になるときの太陽の方向を図 F-4に示す. 影全体がいくつかの部分に分かれている場合(この例では2個), 影全体の幅はそれぞれの部分の影の幅の和である.

図 F-4: 影全体の幅が最大になる太陽の方向

太陽の方向は, 図 F-5に示される角度θで指定される. 東はθ=0, 南はθ=π/2, 西はθ=π である. 太陽は東(θ=0)から昇り, 西(θ=π)に沈むと仮定してよい.

あなたの仕事は, 円柱の配置が与えられたときに, その 円柱群の影の幅が最小および最大になるときの太陽の方向 θ_min と θ_max を, それぞれ求 めるプログラムを書くことである.

各円柱底面の円の中心の位置は, (x, y) 座標値で指定される. 東西方向をx軸, 南北方向をy軸とし, xの正の方向が東, yの正の方向が北である.

広場は平面であるとみなして良い.

図 F-5: 太陽の方向を示す角度の定義

一般には, 円柱の配置に対して, 2個以上の θ_min や θ_max が存在することもある. しかし, ここでは θ_min および θ_max が 0<=θ_min<π, 0<=θ_max<π の範囲で それぞれ唯一になるような円柱の配置だけを考える.

入力は, 複数のデータセットの並び, および, 入力の終わりを示す 1行から成る. 入力の終わりを示す行は1個の0だけを含む.

各データセットは次のような形式をしている．

n
x₁ y₁
x₂ y₂
...
x_n y_n

n は広場にある円柱の本数である. 100以下の正の整数である.

x_k と y_k はk番目の円柱底面の円の中心の x座標とy座標である (k=1, ..., n). それらは30以下の正の整数である. それらは空白1個で区切られる.

なお, 各円柱底面の円の半径は 1 単位(直径は 2 単位) である. 円柱同士は接することはあっても重なることは無い.

たとえば, 次のデータセット

3
1 1
3 1
4 3

は図 F-6のような3本の円柱の配置を表す. このうち2本の円柱は互いに接している.

図 F-6: 3本の円柱の配置例

各データセットについて，2行を出力せよ. 出力行の中に結果を表す数字以外のもの(たとえば空白)が含まれていてはならない.

1行目には, 影の幅を最小にする角度 θ_min を出力せよ. 2行目には, 影の幅を最大にする角度 θ_max を出力せよ. 出力される角度θは 0以上π以下の区間([0,π]と略記する)に 含まれなければならない. ε=0.0000000001 (=10^-10) として, εを超える誤差が無いように すること.

ただし, 正解の角度θの値が[0,ε]の区間に属するときには, [0,θ+ε] および [π+θ-ε,π]の区間に属する近似値 を正解とみなす. また, 正解の角度θの値が[π-ε,π]に属するときには, [0,θ+ε-π]および[θ-ε,π]の区間に属する近似値 を正解とみなす.

上記の誤差の範囲内であれば, 小数点以下何個の数字を出力してもよい.

3
1 1
3 1
4 3
4
1 1
2 3
3 8
1 9
8
1 1
3 1
6 1
1 3
5 3
1 7
3 5
5 5
8
20 7
1 27
30 14
9 6
17 13
4 2
17 7
8 9
0

2.553590050042226
0.982793723247329
1.570796326794896
2.819842099193151
1.325817663668032
2.094395102393196
2.777613697080149
0.588002603547568