問題１

テニス

（６点）

ジョウ君とヤエさんは昼休みにテニスをします。ただし、昼休みは時間が限られているので、短い時間で終わるように、得点について以下の３つのルールで行います。
 相手が３点以下のときに先に５点とれば勝ち。
 ４対４の同点になったときは、その直後に連続して２点とった方が勝ち。
４対４の後に双方が１点ずつとったときは引き分け。

以下の図は、ジョウ君とヤエさんの試合で起こり得るすべての状況を表しています。丸の中の左の数がジョウ君の得点、右がヤエさんの得点です。Ａと書いた矢印はジョウ君が１点とったことを、Ｂと書いた矢印はヤエさんが１点とったことを表します。

ジョウ君とヤエさんの得点が与えられたとき、試合開始からその得点状況になるまでに、上の図で通り得るすべての経路を列挙するプログラムを作成してください。

入力
入力は１つのデータセットからなる。入力データは以下の形式で与えられる。
j yj(0≦j≦6)がジョウ君の得点、y(0≦y≦6)がヤエさんの得点である。ただし、j と y がともに 0 であることはない。また、j が 6 のときは y は 4、y が 6 のときは j は 4 である。

出力
上の図で、試合開始（0-0 と書かれた丸）から与えられた得点が書かれた丸までのすべての経路を出力する。経路は図の矢印に添えられた英字(A,B)の列で表し、辞書式順序（英和辞書で単語が並んでいる順番）になるように並べる。１つの経路を１行に出力する。経路の前後には空白を出力しない。
1/2

入出力例
入力例 12 2

出力例 1
AABB
ABAB
ABBA
BAAB
BABA
BBAA

入力例 25 1

出力例 2
AAAABA
AAABAAAABAAAABAAAABAAAAA

2/2

問題２

親方の給料計算（６点）

ワシはパイプつなぎ組合の親方じゃ。職人を工事現場に派遣し、現場でパイプをつながせておる。去年
は工事が増えて大儲けするかと思ったのじゃが、ちょっと給料の出し方がまずくてのぅ。ウチとしては大赤字になってしまったのじゃよ…。そこで、今年は職人たちへの給料の出し方を工夫したいのじゃ。
職人たちの給料は、工事の種類とこなした回数で決めておる。つまり、職人の給料 ＝ 種類 1 の単価×種類 1 をこなした回数＋種類 2 の単価×種類 2 をこなした回数
・・・・＋種類 M の単価×種類 M をこなした回数となるのじゃ。これを計算するために、ウチでは、どの職人がどの種類の工事を何回こなしたかを次のような表に記録しておる。

職人の番号

工事の種類の番号12345102010254041301110403000501003例えば、上の表では、職人１が工事２を２回、工事４を１回こなしたことを示しておる。
職人たちがこなした仕事の回数はもう変えられんが、やつらは工事の単価を知らんので、単価をいろいろと変えながら皆の不満が出ぬよう給料を調整しようと思うておる。じゃが、ワシがこしらえたプログ
ラムが今もって動かなくてのぅ。ちょっとみてくれんかね。
//省略
int i, j;for ( i = 0; i < N; i++ ){c[i] = 0;
for ( j = 0; j < M; j++ ){c[i] = c[i] + a[i][j]*b[j];}}//省略

N は職人の数で M は工事の種類の数じゃ。変数 a[i][j]に職人 i が工事 j をこなした回数を、b[j]に工事 j の単価をいれて、c[i]に職人 i の給料を格納しておる。合っているはずなのに、うんともすんとも言わん！そろそろ今年の給料を職人たちに払わないとまずいのじゃが・・・・・なんとかならんかのぅ。
それでは、職人のこなした仕事の回数と各工事の単価の情報が与えられたとき、各職人の給料を計算するプログラムを作成してください。

入力
入力は 1 つのデータセットからなる。入力データは以下の形式で与えられる。
1/2

N M
s1 t1 e1s2 t2 e2:0 0 0Lb 11 b 12 ... b 1M
b 21 b 22 ... b 2M:
b L1 b L2 ... b LM

1 行目は職人の数 N(1≦N≦10000)と工事の種類の数 M(1≦M≦10000)。



続いて、工事の記録として、職人の番号 s i (1≦s i ≦N)と工事の種類の番号 t i (1≦t i ≦M)、および職人 s i が工事 t i をこなした回数 e i (1≦e i ≦50000)からなる行が１行以上与えられる。工事の記録はゼロ３つの行で終わる。ただし、e i の合計は 1 以上 50000 以下である。また、工事の記録には、どの職人と工事の種類の組も２度以上現れない。工事をこなした回数が 0 である職人と工事の種類の組は与えられない。
続く 1 行は給料の算出を行う回数 L(1≦L≦100)。
続くL行は、i回目の給料の算出に必要な、工事jの単価b ij (0≦b ij ≦10000)の並び。

出力
以下の形式で、i 回目の給料の算出によって得られた職人 j の給料 c ij を順番に出力する。各給料の間は空白１つで区切る。
c 11 c 12 ... c 1N
c 21 c 22 ... c 2N:
c L1 c L2 ... c LN

入出力例
入力例
4 6
1 2 1
2 3 2
2 4 3
3 1 5
4 2 4
4 3 2
4 6 100 0 031 3 2 4 0 10
6 5 4 3 2 15 1 1 5 5 1

出力例
3 16 5 116
5 17 30 38
1 17 25 162/2

問題３じんこうき（６点）

塵劫記

大きな数を表そうとすると、文字数も多くなるし、位取りがわからなくなってしまうので、なかなか面倒です。大きな数をわかりやすく表すために、人々は数の単位を使ってきました。江戸時代に書かれた「塵劫記」という本の中では、数の単位が次のように書かれています。
まん単位
大きさ単位
大きさ

おく

万AE

4ちょう億EE兆AE

8けいE12AE

京がいEAE

16垓

201010101010せいさい

ごく

ごうがしゃ

あ そ う ぎ

PAE正P

E4010PAE載PE

4410PAE

極PE

4810PAE

恒河沙

E

10PAE

じょうAE

AE

E

24

阿僧祇

E

AE

たふ

E

AE

6010か溝かんE10E10Pぎ

不可思議澗

36Pし

むりょうたいすう
EAE

無量大数E6810PAE

326410PAEP

ゆ那由他

56

こうE10Pな穣

2810P52じょ𥝱𥝱
E10PP

たとえば、２の１００乗のようなとても大きな数は、１２６穣７６５０𥝱𥝱６００２垓２８２２京９４０
１兆４９６７億３２０万５３７６と表せます。それでは、正の整数mとnが与えられたとき、mのn乗を塵劫記の単位を使って上のように表すプログラムを作成してください。

入力
入力は複数のデータセットからなる。入力の終わりはゼロ２つの行で示される。各データセットは以下の形式で与えられる。
m nm(2≦m≦20)が基数、n(1≦n＜240)が指数を表す。ただし、mnは1072未満である。
P

PPP

データセットの数は100を超えない。

出力
データセットごとに、mnを塵劫記の単位で表した文字列を 1 行に出力する。ただし、各単位は以下の表記で出力する。
単位

万億兆京垓𥝱𥝱穣溝澗表記

ManOkuChoKei

Gai

JoJou

KoKan

単位

正載

極

恒河沙阿僧祇

表記

Sei

Sai

GokGgsAsg

那由他 不可思議 無量大数
NytFksMts

mnを表す文字列は、1 から 9999 までの数と上の表に現れる単位を表す文字列からなる。文字列には、余分な 0 や単位を含めない。

入出力例
入力例
2 105 2010 8
20 170 0

出力例
1024
95Cho3674Oku3164Man625
1Oku
131Gai720Kei

1/1

問題４

巨樹の刻み手（７点）

あなたは N 種類の道具を使って、目の前の巨樹を切り倒そうとしています。はじめは、樹の耐久力は D、あなたの経験値は 0 ですが、道具 i で１回樹を叩くと樹の耐久力は a i 減り、あなたは e i の経験値を得ます。ただし、道具 i を使うためには、あなたは r i 以上の経験値を持っていなければなりません。樹の耐久力が 0 以下になると樹は倒れます。
樹の耐久力と道具についての情報が与えられたとき、樹を切り倒すには最低何回樹を叩かなければいけないかを求めるプログラムを作成してください。

入力
入力は複数のデータセットからなる。入力の終わりはゼロ２つの行で示される。各データセットは以下の形式で与えられる。
D N
a1 e1 r1
a2 e2 r2:
aN eN rN
1行目に樹の耐久力を表す整数D(1≦D≦100)と道具の種類の数N(1≦N≦100)が与えられる。続くN行に道具1からNまでの情報が与えられる。a i (0≦a i ≦100)とe i (0≦e i ≦100)は、道具iを１回使うことで減る樹の耐久力とあなたが得ることのできる経験値をそれぞれ表す。r i (0≦r i ≦100)は道具を使うために必要な経験値を表す。a i , e i , r i はすべて整数である。
データセットの数は50を超えない。

出力
樹を切り倒すのに必要な、樹を叩く最小の回数を１行に出力する。ただし、樹を切り倒すことが不可能な場合は NA と出力する。

入出力例
入力例
15 41 1 0
1 2 25 10 58 1 1560 4
5 2 08 8 2
3 5 049 0 18100 1
1 1 10 0

出力例
64NA1/1

問題５

無限急行（８点）

ムゲン鉄道のムゲン線には無限個の駅があります。駅には …, -3, -2, -1, 0, 1, 2, 3, … と番号が振られていて、各駅は数直線上の整数と同じ順番で隣り合っています。あなたはいま、ある番号の駅から電車に乗り、それより大きな番号の駅に向かおうとしています。
ムゲン線には無限種類の快速電車が走っています。それらは 0 級快速、1 級快速、2 級快速、3 級快速、… のように番号で呼ばれています。n 級快速の電車は、2n の倍数の番号の駅に停車します。たとえば、1 級快速は駅 …, -4, -2, 0, 2, 4, … に、3 級快速は駅 …, -24, -16, -8, 0, 8, 16, 24, … に停車するといった具合です。0 級快速はすべての駅に停車するので、本当は各駅停車ですがムゲン鉄道は「快速」と呼んでいます。
どの級の快速電車も、ある停車駅から次の停車駅まで移動するのに 1 単位時間かかります。また、快速電車間の乗り換えにかかる時間は無視できるものとします。乗車駅 s と降車駅 d が与えられたとき、sから d へ移動するのに必要な最小の時間を求めるプログラムを作成してください。ただし、s から d へ移動する間に、大きな番号から小さな番号の駅に向かっての移動は認められないものとします。

入力
入力は 1 つのデータセットからなる。入力データは以下の形式で与えられる。
N
s1 d1
s2 d2
:
sN dN
１行目に移動の回数を表す N(1≦N≦100)が与えられる。続く N 行に、乗車駅の番号 s i と降車駅の番号d i (-1,000,000,000≦s i ＜d i ≦1,000,000,000)が与えられる。

出力与えられた乗車駅と降車駅ごとに、移動に必要な最小の時間を１行に出力する。

入出力例
入力例
30 7-1048576 0-3 5

出力例3141/1問題６微生物発電（９点）

飯沼博士は磐梯山の噴気孔でふしぎな微生物を見つけました。この微生物の雄と雌１体ずつが合体すると、電気エネルギーを放出します。この微生物を研究すれば、将来のエネルギー危機から我々を救えるかもしれません。
観察を続けると、微生物は合体したときだけ電気エネルギーを発生させることと、合体した微生物のさらなる合体はないことがわかりました。さらに観察を続けると、合体で放出される電気エネルギーは、微生物が体内に持つ未知の粒子（博士はこれを磐梯山にちなんでＢ粒子と名づけました）の量で決まることがわかりました。合体する雄と雌が体内に持つＢ粒子の量をそれぞれ bm と bw とすると、合体により放出される電気エネルギーは |bm - bw|×(|bm - bw| - 30)2 という式で計算できます。
この発見により、微生物の集団から得られる最大の電気エネルギーが計算できるようになりました。それでは、微生物の集団に含まれる雄と雌の数と、各個体が持つＢ粒子の量が与えられたとき、この微生物の集団から得られる最大の電気エネルギーを計算するプログラムを作成してください。

入力
入力は複数のデータセットからなる。入力の終わりはゼロ 2 つの行で示される。入力データは以下の形式で与えられる。
M W
bm 1 bm 2 ... bm M
bw 1 bw 2 ... bw W
１行目のMとW(1≦M,W≦12)はそれぞれ雄と雌の微生物の数である。２行目に、i番目の雄が体内に持つＢ粒子の量bm i (0≦bm i ≦50)が与えられる。３行目に、i番目の雌が体内に持つＢ粒子の量bw i (0≦bw i ≦50)が与えられる。
データセットの数は20を超えない。

出力
データセットごとに、微生物の集団から得られる電気エネルギーの最大値を 1 行に出力する。

入出力例
入力例
3 30 20 30
10 20 30
10 1032 10 15 8 20 10 6 45 50 41
18 0 37 25 45 11 25 21 32 27
7 323 14 39 6 47 16 23
19 37 80 0

出力例
12000
53906
11629

1/1

問題７

古代遺跡の謎（１１点）

古代遺跡から超大型あみだくじが発見された。学者達はこれをVLA(Very Long Amidakuji)と命名した。分析の結果、VLAはN本の縦棒を持ついくつかの部品の組み合わせで構成され、多くの場合繰り返しを含んでいることがわかった。例えば、右図のVLAは２種類の部品AとBを使った４つの部品から構成されている。
このVLAの上端に左から順番に1,2,3,4,5と番号をつけ、それぞれの番号からVLAをたどり（あみだくじのたどり方については問題文最後の補足を参照してください)、下端にたどり着いた場所の縦棒にその番号を振る。すべての番号についてたどり終えた後で、下端に振られた番号を左から読むと4,2,5,1,3になる。このように、1,2,3,4,5という番号の列が4,2,5,1,3という列に変換される。
彼らはVLAによって1からNまでの番号の列がどのように変換されるのかを知りたいが、手作業でたどるのは大変そうだ。そこでパソコン甲子園出場者である優秀なプログラマーの君たちに、VLAのシミュレーションを依頼した。
VLAはとても長いため、そのままの状態ではプログラマーたちに情報を伝えることができない。そこで学者たちは、部品の種類を英大文字１つで表し、VLAを式で表現することにした。
部品は同じ位置関係である縦棒が一致するように、左から順番に＋演算子で接続される。たとえば、上からA,B,C,D という順番で連結された部品の列は A+B+C+D という式で表記される。
部品の列を表す式 seq の m回の繰り返しは、m(seq)と表記できる。たとえば、A+B の2回の繰り返しは2(A+B)と表せ、これは A+B+A+B と同じである。また、seq が１つの部品 a の場合は、aを囲むかっこを省略しても構わない。4(A+B)と3(X+Y)を、この順番で連結したVLAは4(A+B)+3(X+Y)と表せる。また、かっこは 2(4(A+B)+3(X+Y))+10C のように入れ子にしても構わない。
それでは、縦棒の数N、各部品の情報、複数のVLAの式を入力とし、各式が表すVLAによって1からNまでの番号の列がどのように変換されるかを出力するプログラムを作成しなさい。
（※補足：あみだくじのたどり方について）
あみだくじのある縦棒の上端から出発して上から下へ進む。ただし、横棒がある地点ではその横棒でつながった別の縦棒に移動する。これを、縦棒の下端にたどり着くまで繰り返す。

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

1/3

N K
p1 h1
g 1 (1,1) g 1 (1,2) .. g 1 (1,N-1)
g 1 (2,1) g 1 (2,2) .. g 1 (2,N-1):
g 1 (h 1 -1,1) g 1 (h 1 -1,2) .. g 1 (h 1 -1,N-1)
p2 h2
g 2 (1,1) g 2 (1,2) .. g 2 (1,N-1)
g 2 (2,1) g 2 (2,2) .. g 2 (2,N-1):
g 2 (h 2 -1,1) g 2 (h 2 -1,2) .. g 2 (h 2 -1,N-1):
pK hK
g K (1,1) g K (1,2) .. g K (1,N-1)
g K (2,1) g K (2,2) .. g K (2,N-1):
g K (h K -1,1) g K (h K -1,2) .. g K (h K -1,N-1)
E
expression 1
expression 2:expression E
1行目に縦棒の数を表す整数N (2≦N≦12) と部品の種類の数K(1≦K≦26)が与えられる。
2行目以降にK種類の部品の情報が与えられる。各部品は以下の形式で与えられる。
 最初の行は部品名を表す１つの英大文字p i と部品iの縦棒の長さを表す整数h i (1≦h i ≦20)を含む。
 続くh i -1行で部品iの横棒の情報が与えられる。g i (r,c)は部品iの上端から長さrの位置において、左からc番目の縦棒とc+1番目の縦棒をつなぐ横棒の有無を表す。横棒があるときはg i (r,c)=1、横棒がないときはg i (r,c)=0である。
続く１行に式の数E(1≦E≦100)が与えられる。続くE行にVLAの式を表す文字列expression i （1文字以上1000文字以下）が与えられる。
入力は以下の条件を満たす。
 異なる部品に同じ名前が使われることはない。
 各部品iについて、g i (r,c)とg i (r,c+1)が同時に1となることはない。
 式に含まれる整数は1以上1,000,000,000以下である。
 式には空白は含まれない。

出力
式ごとに、VLA による 1 から N までの列の変換結果を１行に出力する。それぞれの数字の間は空白 1 つで区切る。

2/3

入出力例
入力例
5 2A 5
1 0 0 10 1 0 0
1 0 1 00 1 0 1
B 4
1 0 0 10 1 0 00 0 1 022(A+B)
1000000000(1000000000A+1000000000B)

出力例
4 2 5 1 31 2 3 4 53/3問題８ 壁（１３点）

２XXX年、突然出現した天敵の侵入を防ぐために、人類は壁を作りその中に逃げ込んだ。その結果、人類の活動領域はその壁で囲まれた範囲に限定されてしまった。この領域は、上空から見るとW×Hの長方形である。領域内部にはｘ軸あるいはｙ軸に対して平行な壁がいくつか設置されている。活動領域の例
を下図に示す。

人類は活動領域内を自由に移動することができるが、壁を越えるためには一定量の資源を消費しなければならない。ただし、壁を越えることはできるが（図中の①）、壁の交点を越えること（②）
、壁や活動領域の境界の上を移動すること（③）
、活動領域外に出ること（④）はできない。

領域内部の壁の情報といくつかの始点と終点の組を入力し、始点から終点へ移動するために越えなければならない壁の数の最小値を計算するプログラムを作成しなさい。ただし、壁は幅のない線分とします。

入力
入力は１つのデータセットからなる。入力データは以下の形式で与えられる。
W H Mpx 1 py 1 qx 1 qy 1px 2 py 2 qx 2 qy 2:
px M py M qx M qy M
Qsx 1 sy 1 gx 1 gy 1sx 2 sy 2 gx 2 gy 2:
sx Q sy Q gx Q gy Q
1/21行目に領域の横の長さと縦の長さを表す整数W, H(2≦W,H≦1,000,000,000)と壁の数M(0≦M≦100)が与えられる。
続くM行に壁を表す線分の情報が与えられる。各行に与えられる４つの整数px i , py i , qx i , qy i (0≦px i ,qx i ≦W, 0≦py i ,qy i ≦H)はそれぞれi番目の線分の端点のx座標、y座標、もうひとつの端点のx座標、y座標を表す。
続く1行に質問の数Q(1≦Q≦100)が与えられる。続くQ行に各質問が与えられる。各質問に含まれる４つの整数sx i , sy i , gx i , gy i (0＜sx i , gx i ＜W, 0＜sy i , gy i ＜H)はそれぞれ始点のx座標、y座標、終点のx座標、y座標を表す。
入力は以下の条件を満たす。
 各線分はｘ軸あるいはｙ軸に対して平行であり、長さは1以上である。


２つの互いに平行な線分が同じ点あるいは線分を共有することはない。
スタート地点、ゴール地点は壁上にあることはない。

どの線分も活動領域の境界と線分を共有することはない。

出力
質問ごとに、壁を越える回数の最小値を出力する。

入出力例
入力例 15 6 50 2 5 20 3 5 30 4 3 41 4 1 63 0 3 622 5 4 12 5 4 5出力例 131入力例 24 4 011 1 2 2

出力例 20

入力例 34 7 30 2 2 23 3 4 30 5 4 53
1 1 1 31 1 1 41 1 1 6

出力例 30012/2

問題９

アルゴリズム検定試験（１６点）

あなたはイズア地区におけるアルゴリズム検定試験を運営しており、運営費を最小にしたいと考えています。運営費は、会場使用料、バスの使用料、移動補助金の総和です。
今年はN人の受験者登録があり、それぞれc i 人まで受け入れ可能なM個の会場を確保しました。あなたは各受験者を必ずどこかの会場に割り当てなければなりません。１人以上割り当てた会場については、人数にかかわらずf i 円の会場使用料を支払う必要があります。
イズア地区は図に示すように東西方向と南北方向に１km間隔で道が走っており、受験者の家と会場は交差点上にあると考えます。各受験者は家から会場まで道に沿って徒歩で移動できます。また、この検定試験では、１人以上受験者を受け入れる各会場につき１台のシャトルバスが運行されるので、受験者はバスを利用することもできます。ただし、自分が受験する会場行きのバスにしか乗れません。

各シャトルバスは、会場からの東西方向の距離と南北方向の距離の和がD以内のすべての交差点に停車します（図はD＝3の場合）。バスの使用料はDに比例し、Dが1km増えるとB円上がります。つまり、シャトルバスを運行するには１会場あたりD×B円の費用を支払う必要があります。なお、D及びBはすべての会場で共通の値を用います。
移動補助金とは、各受験者に必要な最低限の徒歩での移動に対して運営者が受験者に支払う費用で、1㎞について1円を払う必要があります。
あなたは受験者の家と会場の位置、会場の受け入れ可能人数と使用料、Dが1km増えたときに加算される料金Bの情報を入力データとして持っており、各受験者への会場割り当てとDを決定することができます（ただし、Dは0以上の整数)。このとき、運営費の最小値を求めてください。

入力
入力は複数のデータセットからなる。入力の終わりはゼロ３つの行で示される。各データセットは以下の形式で与えられる。
N M Bax 1 ay 1
ax 2 ay 2:
ax N ay N
1/3

bx 1 by 1 c 1 f 1
bx 2 by 2 c 2 f 2:
bx M by M c M f M
1 行目は３つの整数からなる。N(1≦N≦100)は受験者の人数、M(1≦M≦5)は会場数である。B(0≦B≦1000)
はシャトルバスを運行する際に、D が 1km 増えたときに加算される料金である。続く N 行に各受験者の家の座標が与えられる。ax i ,ay i (-1000≦ax i ,ay i ≦1000)はそれぞれ受験者 i の家の x 座標と y 座標を示す。続く M 行に各会場の情報が与えられる。bx i , by i (-1000≦bx i ,by i ≦1000)はそれぞれ会場 i の x 座標と y 座標を示す。c i (1≦c i ≦100)は会場 i の受け入れ可能人数、f i (0≦f i ≦100000)は会場 i の使用料を示す。ただし、c 1 から c M までの合計は N 以上である。
入力は以下の条件を満たすと考えてよい。
 使用する会場を決めたとき、D=i におけるそれらの会場への受験者の割り当て方のうち移動補助金が最小となるときの金額を F(i)とする。このとき、F(i+2)-F(i+1)≧F(i+1)-F(i) が成立する。
データセットの数は 10 を超えない。

時間制限
入力に対して、実行時間が２０秒を超えてはならない。

出力
データセットごとに試験の運営費の最小値を 1 行に出力する。

入出力例
入力例
1 1 10 00 0 1 0
1 1 00 0-3 0 2 31 3 10 0-3 0 2 30 -5 2 0
4 0 2 14 3 10 00 00 00 0-3 0 2 30 -5 2 0
4 0 2 16 3 10 00 0

出力例03511182820382/3

0 00 00 00 0
-3 0 2 30 -5 2 0
4 0 2 16 3 20 00 00 0
0 0
0 0
0 0
-3 0 2 30 -5 2 0
4 0 2 1
10 5 10 0
2 0
4 0
8 0
100 0
100 0
100 0
100 0
100 0
100 0
-3 0 1 0
1 0 1 03 0 2 0
15 0 1 0
105 0 6 0
10 5 20 0
2 0
4 0
8 0
100 0
100 0
100 0
100 0
100 0
100 0
-3 0 1 0
1 0 1 03 0 2 0
15 0 1 0105 0 6 0
0 0 0

3/3

問題１０ アカ・ベコ捕獲作戦（１８点）

怪盗アカ・ベコは大胆にも、ツルガジョーから銀のシャチホコを盗み去った。警部であるあなたは、アカ・ベコが仲間のコボウ氏にシャチホコを渡すらしいという情報を手に入れた。ただ、コボウ氏はアカ・ベコのアジトまで出向けないので、アジトの外で渡すらしい。あなたはアカ・ベコを待ち伏せして捕まえることにした。この町は古い城下町なので、道が複雑に入り組んでいて、どの道も一方通行になっている。アカ・ベコがアジトから受け渡し場所までどの経路を通るのかはわからないが、人員不足のため、待ち伏せ場所は１つに設定しなければならない。
あなたは、アジトを含むいくつかの地点を選び、それらをつなぐ道を調べ、地図を作った。地図上の地点のどこかで受け渡しが行われるらしい。受け渡し場所が判明次第、以下のように待ち伏せ場所を選ぶ。
① アジトは危険なのでアジト以外の地点。
② アカ・ベコがアジトから受け渡し場所までどのような経路を通っても必ず通る地点。
③ ①②の両方を満たす地点のうち、受け渡し場所にたどり着くまでに通過しなければならない地点の数がより少ない地点。ただし、コボウ氏に見つからないようにするために、①②を満たす地点が他にない場合のみ、受け渡し場所を待ち伏せ場所にする。
アジトと待ち伏せ場所の候補からなる地点をつなぐ道の情報のあとに、質問として受け渡し場所が複数入力されたとき、それぞれの受け渡し場所について待ち伏せ場所を出力するプログラムを作成してください。

入力
入力は１つのデータセットからなる。入力データは以下の形式で与えられる。
N M
s1 t1:
sM tM
Qr1:
rQ
１行目は２つの整数からなる。N(3≦N≦100000)は地点の数、M(N-1≦M≦300000)は地図に書いたすべての道の数を表す。続くM行に隣り合った地点の間を直接つなぐ道が与えられる。s i とt i (1≦s i ≠t i ≦N)はi番目の道のそれぞれ始点、終点となる地点の番号を表す。ただし、アジトの番号は 1 とし、アジトからはすべての地点へ到達できる。
続く１行に質問の数Q(1≦Q＜N)が与えられる。続くQ行に質問が与えられる。i番目の質問として、受け渡し場所の番号r i (2≦r i ≦N)が与えられる。

時間制限
入力に対して、実行時間が３０秒を超えてはならない。
1/2

出力
質問ごとに、待ち伏せ場所の番号を１行に出力する。

入出力例
入力例 16 7
1 22 31 3
1 44 55 66 1
523456

出力例 123445

入力例２11 15
1 2
1 3
1 4
2 53 63 7
3 94 74 10
4 116 26 87 98 11
9 610621089351147

出力例２624693211472/2