芸無町の奇妙な風習のひとつは，次期町長の選出までもがゲームの結果によることだろう. 町長の任期満了が近づいてくると，現職の町長を含む少なくとも3人の候補者が小石のゲームを競い，勝者が次期町長となる.

小石のゲームのルールは次の通りである. 以下で，nは候補者の人数である.

使うもの

円卓と碗と十分な個数の小石.

ゲームの開始

最初に碗に入れるのは管理委員会が秘密の確率的手段で決めた数の小石である. 0からn-1と番号を振った全候補者は，反時計回りの番号順に円卓を囲んで座る. 碗はまず現職の町長 (候補者0) に渡す.

ゲームのステップ

碗を渡された候補者は，碗に小石が入っている場合は，そのうち1個を取り（すでに持っている小石があればそれらと共に）手許に置く. 碗が空の場合は，手許に小石があればその全部を碗に入れる. どちらの場合も，その後で碗を右隣の候補者に渡す. 勝者が決まるまでこのステップを繰り返す.

ゲームの終了

ある候補者が碗に残った最後の小石を取り出したとき，他のどの候補者の手元にも小石がなければ，ゲームは終わりで，全部の小石を持っているその候補者が勝者となる.

芸無高校の数学教員の解析によると，このゲームは必ず有限のステップで終わるが，必要なステップ数は非常に多くなることもある.

入力はデータセットの並びである. 各データセットは一文字の空白で分けられたふたつの整数 n とp からなる一行である. 整数 n は現町長を含む候補者の人数であり，整数 p は最初に碗に入れる小石の総数である. 3 ≤ n ≤ 50, 2 ≤ p ≤ 50 である.

入力データセットに含まれる設定では，ゲームは1000000(百万)ステップ以内に終了する.

入力の終わりは，ふたつの0が一文字の空白で区切られる一行で示される.

出力は，入力の各データセットの表すゲームの勝者の候補者番号を示す整数ひとつからなる行を，入力データセットの順序どおりにならべたものである. それ以外の文字が出力にあってはならない.

3 2
3 3
3 50
10 29
31 32
50 2
50 50
0 0

1
0
1
5
30
1
13

この問題では，同じ大きさの正方形に区切られたメッシュ状の地図が与えられる．この地図は，ある海域を表しており，各正方形の領域が陸または海に対応する．図B-1は地図の一例である．

図B-1：ある海域の地図

陸に対応する二つの正方形領域が，地図上で縦，横または斜め方向に隣接しているなら，一方から他方へ歩いて行くことができる．陸に対応する二つの領域が同じ島に属するのは，一方から他方へ（一般には別の陸地を経由して）歩いて行ける時であり，またその時のみである．なお，この地図の海域は海で囲まれており，その外側へ歩いて出ることはできない．

与えられた地図を読み取り，この海域に島がいくつあるか数えるプログラムを作成して欲しい．たとえば，図B-1の地図には，全部で三つの島がある．

入力はデータセットの列であり，各データセットは次のような形式で与えられる．

w h
c_1,1 c_1,2 ... c_1,w
c_2,1 c_2,2 ... c_2,w
...
c_h,1 c_h,2 ... c_h,w

w と h は地図の幅と高さを表す50以下の正の整数であり，地図は w×h 個の同じ大きさの正方形から構成される． w と h の間は空白文字1個で区切られる．

c_{i, j} は，0 または 1 であり，空白文字1個で区切られる． c_{i, j} = 0 なら，地図上で左から i 番目，上から j 番目の正方形は海であり，c_{i, j} = 1 なら陸である．

入力の終わりは，空白文字1個で区切られた2個のゼロのみからなる行で表される．

各データセットに対し，島の個数を1行に出力せよ．それ以外の余計な文字を含んではいけない．

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

0
1
1
3
1
9

覆面算を考えよう．

このパズルでは，たとえば以下のような十進表現の非負整数の足し算を扱う．

    905 +  125 = 1030

覆面算では等式の中の全ての数字はアルファベットの文字で隠されている．たとえば，上で示した等式を答の一つに持つ問題には次のものがある．

    ACM + IBM = ICPC

このパズルを解くということは，与えられた覆面算において各文字が隠している数字を見つけることである．

パズルの規則は以下のとおりである．

• 整数の各桁は10種類の数字'0'〜'9'で表されるが，すべての数字はアルファベット文字'A'〜'Z'で隠されている．
• 等式の複数箇所に現れる同一のアルファベット文字は，同じ数字を隠している．また，同じ数字はすべて，同じアルファベット文字で隠されている．すなわち，等式中の異なるアルファベット文字は異なる数字を表している．
• ゼロが'0'という一文字で表される場合を除いて，最上位の桁の数字は0になってはいけない．つまり，"00"や"0123"などの表現は許されない．

上の覆面算における可能な数字の割り当ては，表に示す通り4種類ある．

このパズルを解くプログラムを作成せよ．

入力は複数のデータセットからなる．入力の終わりはゼロをひとつだけ含む行で表される．

データセットの個数は100以下である．各データセットは次の形式で表される．

N
STRING ₁
STRING ₂
...
STRING _N

データセットの最初の行は，等式に現れる整数の数 N を表している．

それに続く N 行はそれぞれ，'A' 〜 'Z'というアルファベット大文字から成る1個の文字列を含む．これらのアルファベット文字が隠された数字を表している．

各データセットが表しているのは次の等式である．

STRING ₁ + STRING ₂ + ... + STRING _{N -1} = STRING _N

N は 3 以上 12以下の整数，各STRING _i の長さは 1 以上 8 以下である．各データセットに現れるアルファベット文字の種類は 1以上10以下である．

等式を満たすような数字の割り当てが何通りあるかを，各データセットに対してそれぞれ1行で出力しなさい．

それ以外の余計な文字を出力してはいけない．

3
ACM
IBM
ICPC
3
GAME
BEST
GAMER
4
A
B
C
AB
3
A
B
CD
3
ONE
TWO
THREE
3
TWO
THREE
FIVE
3
MOV
POP
DIV
9
A
B
C
D
E
F
G
H
IJ
0

4
1
8
30
0
0
0
40320

摩擦のない国での自動車旅行を考える．この国の自動車にはエンジンがない．ある速さで動き出したら，その速さをずっと維持する（摩擦がないから）．道路上の固定設備として加減速装置が設置してあって，ここを通る時に速さを1だけ増やしたり，減らしたりすることができる．速さを変えないことも可能である．このような世界で，出発地から目的地まで最短の時間で移動するルートを決定するプログラムを書くことがあなたの仕事である．

この国には複数の都市があり，それらの間を結ぶ道路網が整備されている．加減速装置はそれぞれの都市に設置してある．上に述べたとおり，ある都市に速さv で到着した場合，その都市から次の都市に移動する時の速さはv - 1，v ，v + 1 のいずれかである．出発地を出た直後の道路を走る速さは1に限られる．同様に目的地に到着する直前の道路を走る速さも1でなければならない．

出発地と目的地（それぞれ都市である）が与えられる．いくつかの都市を経由しながら目的地に到達する最善のルートを求めることが問題である．ある都市に到着した直後に，今来たばかりの道路を引き返すことはできない（Uターン禁止）．この制限を除けば，経路の選び方は自由である．同じ都市や同じ道路を何度も通ってよいし，出発地や目的地を途中で通過してもかまわない．

都市と都市を結ぶ道路のそれぞれに対して，その距離と制限速度が与えられる．その道路を走る時の速さは制限速度以下でなければならない．道路を通り抜ける所要時間は，距離÷速さである．都市の通過や加減速に要する時間は無視する．

入力は複数のデータセットから構成される．各データセットの形式は次に示すとおりである．

n m
s g
x ₁ y ₁ d ₁ c ₁
...
x_m y_m d_m c_m

データセットの中の入力項目は，すべて非負の整数である．行中の入力項目の区切りは空白1個である．

最初の行は，道路網の大きさを規定する． n は，都市の数である． 2以上30以下と仮定してよい． m は，都市間道路の本数である．道路の本数が0のこともある．

2行目は，実現したい旅行の記述である． s は，出発地の都市番号である． g は，目的地の都市番号である． s はg と等しくない．この二つを含めて，データセット中に現れる都市番号は1以上n 以下と仮定してよい．

これに続くm 行が都市間道路の記述である． x_i とy_i が両端の都市番号， d_i がその道路に沿った距離である（1 ≤ i ≤ m ）．距離は1以上100以下と仮定してよい． c_i は道路の制限速度である．制限速度は1以上30以下と仮定してよい．

ある二つの都市を直接結ぶ道路が2本以上存在することはない． 1本の道路の両端が同じ都市であることはない．それぞれの道路は，どちら向きの移動にも使うことができる．

最後のデータセットの直後に，空白で区切られた二つのゼロからなる行がある．

入力の各データセットに対して，以下に規定する結果を一つの行として出力しなさい．出力行の中に，結果を表す文字以外のもの（たとえば空白）が含まれていてはならない．

目的地に到達できる場合は，最も所要時間の短いルートを選んだ時の所要時間を出力すること．答には，0.001を越える誤差があってはいけない．この条件を守る限り，小数点以下に何個の数字を出力してもよい．

目的地に到達できない場合は，unreachableと出力すること． unreachableの文字はすべて小文字であることに注意．

2 0
1 2
5 4
1 5
1 2 1 1
2 3 2 2
3 4 2 2
4 5 1 1
6 6
1 6
1 2 2 1
2 3 2 1
3 6 2 1
1 4 2 30
4 5 3 30
5 6 2 30
6 7
1 6
1 2 1 30
2 3 1 30
3 1 1 30
3 4 100 30
4 5 1 30
5 6 1 30
6 4 1 30
0 0

unreachable
4.00000
5.50000
11.25664

たくさんの青いカードと赤いカードがテーブルの上にある．各カードの表面には1より大きい整数がひとつ印刷されている．同じ整数値がいくつかのカードに印刷されていることがある．

青いカードの数値と赤いカードの数値が1より大きい同じ整数値で割りきれるとき，その青いカードと赤いカードはペアにすることができる． 1枚の青いカードとペアにできる複数の赤いカードがありうる．また，1枚の赤いカードとペアにできる複数の青いカードがありうる．青いカードと赤いカードを1枚ずつ選んでペアにしたら，その2枚のカードをテーブル上の全体のカードから取り除く．

図 E-1: 青いカード4枚と赤いカード3枚

たとえば，図E-1には，青のカードが4枚，赤のカードが3枚ある． 4枚の青のカードに 2, 6, 6, 15 が印刷され， 3枚の赤のカードに 2, 3, 35 が印刷されている．ここで，青と赤のカードのペアを以下のようにして作ることができる．最初に，「青の2」と「赤の2」をペアにして取り除くことができる．次に，「青の6」のうちのひとつと「赤の3」をペアにして取り除くことができる．そして，「青の15」と「赤の35」をペアにして取り除くことができる．この場合，取り除いたペアは3組である．

ペアの個数はペアを作るカードの選び方によって変化することに注意せよ．最初に「青の15」と「赤の3」というペアを作ってこれを取り除くこともできる．この場合，もうひと組しかペアを作れず，合わせて2組のペアしか取り除けない．

あなたの仕事は，テーブル上のカードから最大何組のペアが取り除けるかを求めることである．

入力は複数のデータセットからなる．データセットの総数は100以下である．各データセットは，次の形式をしている．

m n
b₁ ... b_k ... b_m
r₁ ... r_k ... r_n

m と n はそれぞれ青いカードと赤いカードの枚数を示す． 1 ≤ m ≤ 500 および 1≤ n ≤ 500 と仮定してよい． b_k (1 ≤ k ≤ m) およびr_k (1 ≤ k ≤ n) は，それぞれ青と赤のカードに印刷された数であり，それらは2以上10000000 (=10⁷)未満の整数である．入力データの整数は1個のスペースまたは改行で区切られている． b_m と r_n の各々の直後は改行である．データセットには他に余計な文字は無い．

入力の終わりはスペースで区切られた2個のゼロからなる行である．

各データセットに対し，ペアの組数の最大値を表す整数を1行に出力せよ．

4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 15 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 952 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 318 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 755 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 217 846 193 416 525
69 115 489 355 256 654 49 439 118 961
0 0

3
1
0
4
9
18
85

平らな板に2つの穴が開けられている．板の表側には何本もの針が刺してある．1本のひもが裏側から穴の1つを通して表側に出ており，板の表面を折れ線状に曲がりながら，もう1つの穴に達し，そこから裏側に抜けている．この時点では，ひもは針に触れていない．

図F-1, F-2, F-3は穴，針およびひもの配置の例をそれぞれ示している．白い四角と円はそれぞれ穴と針を表している．ひもは実線で表された折れ線である．

図F-1: 穴，針，ひもの配置例

図F-2: 穴，針，ひもの配置例

図F-3: 穴，針，ひもの配置例

いま，ひもの両端に同じ重さの石を取り付けたところ，ひもはゆっくりと変形して緩みのない状態になった．このとき，いくつかの針にひっかかり，最初とは異なる折れ線状になった．(ただし，1つの針にもひっかからないこともある．)

変形の際，ひもはそれ自身にひっかかることはないものとする．つまり，ひもの緩みがなくなったとき，ひもはいくつかの針の位置を頂点，2つの穴の位置を端点とするような折れ線を板の表面上に描く．例えば図F-1, F-2, F-3の配置からは，それぞれ図F-4, F-5, F-6の折れ線が得られる．この折れ線の全長を求めるプログラムを作成せよ．

図F-4: 図F-1の配置からひもの緩みをなくした状態

図F-5: 図F-2の配置からひもの緩みをなくした状態

図F-6: 図F-3の配置からひもの緩みをなくした状態

ただし，ひも，針，穴の直径は無視できるほど小さいものとする．

入力は複数のデータセットから成り，最後に2つのゼロが空白で区切られた行が続く．1つのデータセットは以下の形式でひもの初期形状(穴および頂点の位置)と針の位置を与える．

m n
x₁ y₁
...
x_l y_l

1行目は2つの整数 m, n (2 ≤ m ≤ 100, 0 ≤ n ≤ 100)で，ひもの初期形状を表す両端の穴を含む頂点数(m)と針の本数(n)とを表している．続く l = m + n 行の各行は2つの整数 x_i , y_i (0 ≤ x_i ≤ 1000, 0 ≤ y_i ≤ 1000) によって平面上の座標 P_i = (x_i , y_i ) を表している．

• P₁ から P_m まではひもの初期形状を表す．つまり，P₁ と P_m にはひもが通っている穴があいており，ひもは P_i (i = 1, ..., m)を順に通る折れ線状になっている．
• P_m+1 から P_m+n まではn本の針の位置を表している．

ただし，2つの座標が同じ位置にあることはない．また，3つの座標が直線上に並ぶことはないとする．

各データセットについて，ひもの緩みがなくなったときの板の表面上に残されたひもの部分の長さが書かれた1行を出力せよ．1つの出力行は余計な文字を含んではならない．

出力される長さは 0.001 より大きな誤差を持ってはならない．

6 16
5 4
11 988
474 975
459 16
985 12
984 982
242 227
140 266
45 410
92 570
237 644
370 567
406 424
336 290
756 220
634 251
511 404
575 554
726 643
868 571
907 403
845 283
10 4
261 196
943 289
859 925
56 822
112 383
514 0
1000 457
514 1000
0 485
233 224
710 242
850 654
485 915
140 663
26 5
0 953
180 0
299 501
37 301
325 124
162 507
84 140
913 409
635 157
645 555
894 229
598 223
783 514
765 137
599 445
695 126
859 462
599 312
838 167
708 563
565 258
945 283
251 454
125 111
28 469
1000 1000
185 319
717 296
9 315
372 249
203 528
15 15
200 247
859 597
340 134
967 247
421 623
1000 427
751 1000
102 737
448 0
978 510
556 907
0 582
627 201
697 963
616 608
345 819
810 809
437 706
702 695
448 474
605 474
329 355
691 350
816 231
313 216
864 360
772 278
756 747
529 639
513 525
0 0

2257.0518296609
3609.92159564177
2195.83727086364
3619.77160684813