全国高等学校パソコンコンクール
プログラミング部門 本選問題
２０２１年１１月１３日(土) １３時００分～１７時００分

全国高等学校パソコンコンクール実行委員会※個人の利用目的以外で、主催者に無断で転載・複製することを禁止します。

問題１切り上げ除算（２点）

正の整数 n と d について、n÷d は n が d で割り切れる場合だけ整数になりますが、割り切れない場合は小数点以下にも０でない数字が現れます。その場合、小数点以下を切り上げるか切り捨てるかすれば整数が得られます。
一方で、n÷d の小数点以下を切り上げた整数を求めるために、切り捨てを使う方法もあります。 (n＋d－1)÷d の小数点以下を切り捨てれば、n÷d の小数点以下を切り上げた整数を求めることができます。

課題
正の整数 n と d が与えられたとき、n÷d の小数点以下を切り上げて得られる整数を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
n d１行目に正の整数n(1≦n≦100)とd(1≦d≦100)が与えられる。

出力n÷d の小数点数以下を切り上げて得られる整数を 1 行に出力する。小数点や、それ以下の数値を出力してはならない。

入出力例
入力例１2 3

出力例１1入力例２5 3

出力例２2入力例３6 3

出力例３21/21

問題２

トウサ菌トウヒ菌（４点）

英世博士が発見した２種類の菌、トウサ菌とトウヒ菌は増殖に関して面白い性質を持っています。
⚫

トウサ菌は、１時間ごとに一定の数 d だけ総数が増えます。例えば、最初の総数を a0 とすると、１時間後には総数が a1＝a0 ＋ d、２時間後には総数が a2＝a1 ＋ d と増えていきます。

⚫

トウヒ菌は、１時間ごとに一定の倍率 r で総数が増えます。例えば、最初の総数を a0 とすると、１時間後には総数が a1＝a0 × r、２時間後には総数が a2＝a1 × r となります。

英世博士は、今から９時間後に手元にある菌を実験に使う予定ですが、手元にある菌のサンプルがどちらの菌のものなのか忘れてしまいました。しかし、１時間後と２時間後の菌の総数を把握することで、それがどちらの菌なのか判定できることに気づきました。

課題
手もとにある菌の最初の総数と１時間後の総数と２時間後の総数が与えられたとき、９時間後の菌の総数を出力するプログラムを作成せよ。ただし、手元の菌がトウサ菌かトウヒ菌かは与えられない。また、トウサ菌の１時間ごとの増殖数 d と、トウヒ菌の１時間ごとの増殖倍率 r は、正の整数とする。

入力
入力は以下の形式で与えられる。
a0 a1 a2１行に、手元にある菌の最初の総数 a0(1≦a0≦100)、１時間後の総数 a1(a0＜a1≦101)、２時間後の総数a2(a1＜a2≦102)が与えられる。また、どちらの菌とも判定できないような入力は与えられない。

出力
手もとにある菌の９時間後の総数を１行に出力する。

入出力例
入力例１2 6 10出力例１38

入力例１は、１時間ごとの増殖数が４のトウサ菌で、３時間後に 14、４時間後に 18、５時間後に 22、６時間後に 26、７時間後に 30、８時間後に 34、９時間後に 38 なので答えは 38。

入力例２3 6 12

出力例２1536

入力例２は、１時間ごとの増殖倍率が２のトウヒ菌で、３時間後に 24、４時間後に 48、５時間後に96、６時間後に 192、７時間後に 384、８時間後に 768、９時間後に 1536 なので答えは 1536。

2/21

問題３

ソートなぞなぞ（４点）

ソートなぞなぞとは、ある英単語に含まれる各文字をアルファベットの順に並べ直した文字列から、元の英単語を推測する遊びです。
例えば、文字列 aet が与えられた場合には、元の英単語は eat や ate などであったと推測できます。
英単語が苦手な PCK 君はこの遊びをするために、与えられた文字列と、それを並べ替えた全ての文字列を考えることにしました。

課題
並べ直した文字列が与えられる。PCK 君が考えることになる文字列の数を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
str
１行に並べ直した文字列strが与えられる。ただし、strは英小文字のみを含み、長さは1以上8以下である。また、各文字は先頭からアルファベットの順に並んでいる。

出力
PCK 君が考えることになる文字列の数を出力する。

入出力例
入力例１aet

出力例１6

入力例２eeei

出力例２4

3/21

問題４

災害対応シミュレーション（６点）

PCK 君はワールドロボットチャレンジの災害対応シミュレーション部門に参加しています。この部門のミッションは、建物の中に取り残された人達を救助することです。
建物の内部は H 行 W 列のマスに区切られた平面で表され、各マスは壁、道、障害物のいずれかです。建物には N 人が取り残されていて、N 台の救助ロボットのそれぞれが一人ずつ救出します。全てのロボットは１つの基地局からいっせいに出発し、それぞれが救出する人のもとへ向かいます。各ロボットは、現在の位置から同じ行か列にある隣接するマスに進むことができます。ただし、建物の外や壁のマスに進むことはできません。道と障害物のマスには複数のロボットが同時に入れます。また、障害物のマスに侵入すると、そのロボットはダメージ 1 を受けます。
ミッション達成のために PCK 君が行う最初のタスクは、取り残された人達全員を救助できるような基地局の適切な設置場所を選定することです。ロボットが基地局から人のいる場所に達する経路があるときは、その中からロボットが受けるダメージを最小にするような経路を必ず選ぶことができます。この前提のもとで、各ロボットが受けるダメージのうち最大の値が最も小さくなるような基地局を探すことにしました。ただし、基地局は道を表すマスに設置しなければなりませんが、そのマスに人がいても設置できます。

課題
建物内部の情報と人の位置が与えられたとき、基地局の場所を選定して、その候補をひとつ報告するプ
ログラムを作成せよ。

入力
入力は以下の形式で与えられる。
H W N
s1,1s1,2 ...s1,Ws2,1s2,2 ...s2,W:sH,1sH,2 ...sH,Wr1 c1r2 c2:
rN cN
１行目に建物内部を表す平面の行の数H(2≦H≦300)、列の数W(2≦W≦300)、人の数N (1≦N≦300)が与えられる。続くH行にi行j列目のマスを表す文字si,jが与えられる。si,jが‘.’,‘#’,‘@’のとき、それぞれ道、壁、障害物を表す。続くN行に、各人がいる場所を表す整数の組ri(1≦ri≦H), ci(1≦ci≦W)が与えられる。riとciはri行ci列目のマスに人がいることを表す。ただし、人がいるマスは道であり、一つのマスに二人以上いることはない。

4/21

出力
基地局の場所を表す整数の組を空白区切りで 1 行に出力する。複数の候補がある場合は、行番号が最小のものを出力する。そのようなものが複数ある場合は、その中で列番号が最小のものを出力する。
ただし、候補が無い場合は「-1 -1」を出力する。

入出力例
入力例１3 4 2.@.#

出力例１1 3#.@@.@..
1 13 4
入力例２2 6 2

出力例２1 2#.@@.#######
1 21 5
入力例３3 3 2...

出力例３-1 -1###...
1 13 35/21

問題５祭りのくじ引き（６点）

アイヅ祭りでは、くじ引き大会をやっています。箱の中に 1 から N までの整数が書かれたくじが一枚ずつあり、何も書かれていないはずれくじが複数枚入っています。N 人が参加し、順番にくじを引きます。
くじを引く人は、数が書かれたくじを引くまで何回でもくじを引きます。はずれくじを引いたら箱に戻し、数が書かれたくじを引いたら箱には戻さず係員に渡します。くじに書かれた数とくじを引いた回数の積が小さい順に上から順位が決まり、順位に応じて賞品がもらえます。
ヒジカタさんは、くじに参加した友人のコンドウさんがどの賞品をもらうか楽しみに見ていました。しかし、全員がくじを引き終わったところで急な呼び出しがあり、順位発表に立ち会えませんでした。ヒ
おのおのジカタさんは、各参加者がそれぞれ何回くじを引いたかはわかっていますが、各々が引いたくじに書いてある数は知りません。

課題
コンドウさんを含む参加者のそれぞれがくじを引いた回数が与えられたとき、コンドウさんがなり得る最高の順位を求めるプログラムを作成せよ。ただし、積が同じ値の人は同じ順位とする。具体的には、
A さんよりも積が小さい人が m 人いるとき、A さんの順位は m+1 になる。

入力
入力は以下の形式で与えられる。
Nrr1r2:
rN-1
１行目にくじの参加者の人数N(2≦N≦100)が与えられる。２行目にコンドウさんがくじを引いた回数r(1≦r≦200)が与えられる。続くN-1行に、他の参加者がくじを引いた回数ri(1≦ri≦200)が与えられる。

出力
コンドウさんがなり得る最高の順位を 1 行に出力する。

6/21

入出力例
入力例１5

出力例１132114
入力例２56

出力例２24182

7/21

問題６

伝言ゲーム

（８点）

PCK 君は友達の誕生日のパーティーの余興として伝言ゲームを企画しています。
パーティーへの参加者のうち５人が横一列に並び、伝言ゲームにチャレンジします。最初に左端の人にメッセージが伝えられ、それを右隣の人に順に伝えていき、右端の人に正しくメッセージが伝わればチャレンジが成功し、５人に景品が与えられます。ただし、メッセージを正しく伝えるためには、話し手と聞き手が共通の言語を使える必要があります。
パーティーには世界中から友人が集まります。PCK 君は景品の予算を見積もるために、伝言ゲームが成功する可能性のある参加者の並び方の数を計算することにしました。

課題パーティーに参加する人数、各参加者が使える言語のリストが与えられたとき、伝言ゲームが成功する可能性のある参加者の並び方の数を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N
info1
info2
:
infoN
１行目にパーティーへの参加者の数N(5≦N≦200)が与えられる。続くN行にi番目の参加者が使用できる言語の情報infoiが与えられる。infoiは以下の形式で与えられる。
k l1 l2 ... lkk(1≦k≦200)はこの参加者が使うことができる言語の数を表す。liはこの参加者が使うことができる言語を表す文字列（２文字の英小文字）である。ただし、同じ参加者が使える言語に重複は無い(i≠jならばli≠lj)。

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

出力
伝言ゲームが成功する可能性のある参加者の並び方の数を 1 行に出力する。

8/21

入出力例
入力例１5出力例１120

2 ja en
2 ja en
2 ja en
2 ja en
2 ja en
入力例２61 ja

出力例２83 ja en ch
2 en fr
2 ve fr
3 ch ve po
1 po

9/21

問題７配置ゲーム（８点）

PCK 君は秋の夜長のお供に新しいゲームを買いました。ゲームの盤面は全体が長方形で、縦に H 個、横に W 個の、同じ大きさの正方形の区画に分かれています。プレイヤーは、縦に R 個、横に C 個分の区画を使う長方形の駒を一つ、区画の境界に合わせるようにして盤面に配置します。しかし、区画にはいくつかの障害物が配置されていて、障害物がある区画を使うような駒の置き方はできません。また、駒の向きを変えて配置してはいけません。
このゲームの点数は、配置した駒の区画と同じ行または同じ列にある区画のうち、以下の条件を満たす区画の数で決まります。
⚫

駒や障害物が置かれている区画ではない。

⚫

各区画から駒に向かって、縦方向または横方向にまっすぐ移動したとき、障害物に出会わずに駒に到達できる。

たとえば、下図(a)のような H=4, W=5 の盤面があるとします。盤面の(r,c)は区画の番号を表しており、区画(2,3)と(3,5)と(4,4)に障害物があります。下図(b)のように、プレイヤーが大きさ R=1, C=2 の駒を、区画(3,2)と(3,3)を使って置くとします。このとき、置いた駒と同じ行、同じ列にある区画で、駒が置かれた区画を除いたものは(1,2),(1,3),(2,2),(2,3),(3,1),(3,4),(3,5),(4,2),(4,3)の 9 個あります。これらのうち、下図(c)の「＋」を付けた区画が、上の条件を満たします。そのような区画の数がこのゲームでの点数となり、この場合の点数は６点です。
(a)

(b)

(c)

(1,2) (1,3)＋(2,1) (2,2) (2,3) (2,4) (2,5)(2,2) (2,3)＋(3,1) (3,2) (3,3) (3,4) (3,5)(4,1) (4,2) (4,3) (4,4) (4,5)

H = 4(1,1) (1,2) (1,3) (1,4) (1,5)(3,1)

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

駒＋＋＋＋

W = 5
PCK 君は、いろいろな盤面や駒のサイズで、最大何点取れるかを考えています。

課題
ゲームの盤面の情報と配置する駒のサイズが与えられたとき、ゲームで最大何点取れるかを求めるプロ
グラムを作成せよ。

10/21

入力
入力は以下の形式で与えられる。
H W R CN
r1 c1r2 c2:
rN cN
１行目に盤面の縦方向の区画の数H(1≦H≦1000)と横方向の区画の数W(1≦W≦1000)、駒が縦方向に占める区画の数R(1≦R≦H)と横方向に占める区画の数C(1≦C≦W)が与えられる。続く１行に障害物の数N(0≦N≦10,000)が与えられる。ただし、NはH×W - R×Cを超えない。続くN行に、障害物の位置が与えられる。ri(1≦ri≦H)とci(1≦ci≦W)はそれぞれ縦方向と横方向の位置を表す整数である。ただし、左上隅の区画の位置をr=1,c=1とする。同じ位置が２回以上与えられることはない。駒を置く方法は必ず一通り以上はあると考えてよい。

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

出力
PCK 君が獲得できる得点の最大値を１行に出力する。

入出力例
入力例１4 5 1 232 3出力例１93 54 4入力例２5 4 4 3出力例２7011/21

問題８星型５角形（８点）

人里離れた森の奥深くに魔女が住んでいました。彼女の魔法は、地面に魔法陣を描くことによって発動します。この魔法陣は、地面に５つの石 A,B,C,D,E を設置し、これらを A→B→C→D→E→A の順に結ぶと星型５角形となるときに発動します。

課題
二次元平面上の相異なる５点 A, B, C, D, E が順に与えられる。ただし３点が同じ直線上に与えられることはない。線分 AB, BC, CD, DE, EA によって星型５角形が描けるかを判定するプログラムを作成せよ。
ただし、星型５角形とは、隣り合う頂点の内角の和が 180 度より大きくなる凸５角形において、各辺を片側に延長した際、交わる点どうしを直線で結んで描かれる図形である。このようにして、凸５角形から星型５角形を作る様子の例を図(a)に示す。図(b)に示すように、この星型５角形は点 A,B,C,D,E をA→B→C→D→E→A の順に結ぶことで描ける。

入力
入力は以下の形式で与えられる。
x1 y1x2 y2x3 y3x4 y4x5 y5
５点 A,B,C,D,E の座標 xi と yi (0≦xi≦100,0≦yi≦100)が順番に、それぞれ１行に与えられる。ただし、５点の座標はすべて異なり、３点が同じ直線上に位置することはない。また、どの点も距離 0.00001 だ
けずらしたとしても答えは変わらないとする。

出力
星型５角形が描ける場合「1」を、そうでない場合「0」を１行に出力する。

12/21

入出力例
入力例１1 4

出力例１17 4
2 14 66 1
入力例２1 4

出力例２04 6
2 17 46 1

13/21

問題９

移動マスゲーム（１０点）

イヅア高校の生徒たちは、来年の体育祭に備えて移動マスゲームの練習をしています。このマスゲーム
では、先生の号令に合わせて生徒達が移動しながら体の向きを変えます。
移動マスゲームでは、1 から N までの番号が付いた区画にいる生徒に対して、先生が指示を出します。
区画は 1 から順に西から東に一列に並んでいます。初めそれぞれの生徒はどこかの区画にいて、全員が北を向いて立っています。どの区画も生徒を全員収容できる広さがあります。先生は、指示の時点で何番から何番までの区画にいる生徒が、どれだけ移動するか伝えます。
先生が a,b,c と３つの数を叫ぶと、その時点で a 番目から b 番目までの区画にいる生徒が全員、c の値に応じて一斉に移動して、さらに体の向きを 180 度変えます。c は整数で、正なら生徒が東に、負なら生徒が西に、数の大きさ１ごとに 1 区画分移動し、移動の前に北向きだった生徒は移動後に南向きになり、南向きだった生徒は北向きになります。このとき、a 番目よりも小さい番号の区画に移動することを指示された生徒は a 番目の区画に移動し、b 番目よりも大きい番号の区画に移動することを指示された生徒は b 番目の区画に移動します。このため、a 番目から b 番目までの区画にいても、まったく移動しない生徒がいることもありますが、そのような生徒も必ず体の向きを 180 度変えます。
指示を出す先生は、ある時点での生徒たちの向きが、移動マスゲームの美しさに関係があると考えています。そのため、いくつかの時点での指示の直後で、指定した範囲の区画にいる生徒のうち北を向いている生徒の人数から南を向いている生徒の人数を引いた値を知りたいと考えています。

課題
区画の数と生徒の人数、それぞれの生徒が初めにいる区画の番号、先生の号令と人数の差を調べる問い
合わせの情報が与えられたとき、各問い合わせについて、指定した範囲の区画にいる生徒のうち、北を向いている生徒の人数から南を向いている生徒の人数を引いた値を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N M
x1
x2
:
xM
Q
info1
info2
:
infoQ
１行目に区画の数N(2≦N≦109=10の9乗)と生徒の人数M(1≦M≦100,000)が与えられる。続くM行に、i番目の生徒が最初にいる区画の番号xi(1≦xi≦N)が与えられる。続く１行に号令と問い合わせに関する情報の数Q(1≦Q≦100,000)が与えられる。続くQ行に号令と問い合わせに関する情報infoiが与えられる。
14/21

情報は時系列順に並んでいる。各infoiは、以下のいずれかの形式で与えられる。
1 a b cまたは
2 d e
1 a b c は、a番目からb番目までの区画にいる生徒が数cに応じて移動しつつ向いている方向を変えよという号令を表す。ただし、1≦a≦b≦N、-N＜c＜Nでc≠0である。2 d eは、その時点でd番目からe番目までの区画にいる生徒のうち、北を向いている生徒の人数から南を向いている生徒の人数を引いた値がいくつになるかという問い合わせを表す。ただし、1≦d≦e≦Nである。
問い合わせに関する情報は１つ以上与えられる。

出力
各問い合わせについて、問い合わせで指定した範囲の区画にいる生徒のうち、北を向いている生徒の人数から南を向いている生徒の人数を引いた値を１行に出力する。

入出力例
入力例
6 6112356112 1 6
1 4 6 -2
2 2 42 3 4
1 1 4 1
2 1 1
2 2 2
2 3 3
2 4 4
2 5 5
2 6 6

出力例
60-10-2-110015/21

問題１０

通学路

（１０点）

PCK 君が住むアイヅ町には、N 個の地点と各地点をつなぐ M 本の道があります。地点にはそれぞれ 1 から N までの番号がついていて、どの道も双方向に移動することができます。また、どの地点からでも、いくつかの道を通っていけば他の地点に到達できます。
PCK 君の家は地点１に、学校は地点 N にあります。PCK 君は、アイヅ町にあるすべての道から、必ず通る道を一つ選んだ場合各々について、学校に行くための最短路を調べたいと考えています。ただし、通学路は以下の条件を満たす必要があります。
•

通学路に含まれる地点はちょうど１回通る。

•

上の条件を満たす通学路の中で距離が最短である。

課題
地点の数と、地点同士を直接つなぐ道の情報が与えられる。各道を選んだときの通学路の距離を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N M
s1 t1 d1
s2 t2 d2:
sM tM dM
１行目に地点の数 N(2≦N≦20)と道の数 M(1≦M≦N(N-1)/2)が与えられる。続く M 行に、２つの地点を直接つなぐ道の情報が与えられる。si と ti (1≦si＜ti≦N)は i 番目の道がつなぐ２つの地点の番号であり、di(1≦di≦1000)はその道の距離を表す。ただし、どの２つの地点についても、それらを直接つなぐ道は１本以下とする。

出力
出力は M 行であり、入力で i 番目に与えられた道を必ず使う場合の通学路の距離を、i 行目に出力する。ただし、i 番目に与えられた道を使う通学路が存在しない場合は「-1」を出力する。

入出力例
入力例
5 5
1 2 4
1 3 1
1 4 3
2 4 2
4 5 6

出力例
12-1912916/21

問題１１

モンスター甲子園（１０点）

あなたは近日開かれるモンスター甲子園に、育てているモンスターを出場させようとしています。モンスター甲子園では相手モンスターが何体か出現し、それらのモンスターと一対一で順番に試合を行います。勝利してもしなくても、次の試合に進めます。試合では、対戦するモンスター同士が持っている、すばやさ、ちからづよさ、かしこさ、の３つの数値を比較し、そのうち２つ以上の数値の大きさが上回っているモンスターが勝利となります。
相手モンスターとの対戦を有利に進めるために、あなたのモンスターの数値を調整することができます。
金貨１枚を支払うと、３つの数値のうちひとつだけ、大きさを１増やしてもらえます。その代わりに他の２つの数値のうちどちらかの大きさを１減らさなければなりません。数値はいくらでも大きくできますが、負にならないように増減させる必要があります。数値の調整は各試合の前に行うことができ、そのとき金貨を何枚使ってもかまいません。金貨があるかぎり数値の調整が可能です。また、増減した数値は以降の試合に引き継がれます。
あなたは、相手モンスターの情報を入手し、自分のモンスターをどのように戦わせるかを考えているところです。

課題
あなたのモンスターの各数値と、試合前に対戦するモンスターの各数値、対戦する順番、使うことのできる金貨の枚数が与えられる。このとき、あなたのモンスターが勝利する試合の最大数を計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N C
a s w
a1 s1 w1：
aN sN wN
１行目に試合の数N(1≦N≦50)と使うことのできる金貨の枚数C(1≦C≦5000)が与えられる。続く1行にあなたのモンスターのすばやさ(0≦a≦100)、ちからづよさ(0≦s≦100)、かしこさ(0≦w≦100)が与えられる。続くN行にi番目に対戦するモンスターのすばやさ(0≦ai≦100)、ちからづよさ(0≦si≦100)、かしこさ(0≦wi≦100)が与えられる。

出力
あなたのモンスターが勝利する試合の最大数を出力する。

17/21

入出力例
入力例１2 22

出力例１
210 30 5030 100 1020 50 50
入力例２3 3030 30 0

出力例２270 25 2025 30 60
20 25 9018/21

問題１２平方連続部分文字列（１２点）

古代国家イワシロでは、今年は雨がほとんど降らず、民衆は困っていました。そのため、新米神官のあなたが、リュウガサワで雨乞いの儀式をすることになりました。
雨乞いの儀式では、雨を降らせてくれる竜神様のために、祈りの書に書かれた祈りの呪文を唱えます。
呪文を唱え終えると、竜神様はその呪文の中に、同じ言葉が２回続けて現れる個所がいくつあったか、あなたに尋ねます。あなたがそれを言い当てれば、祈りが成就して竜神様が雨を降らせてくれます。
たとえば、あなたが abababab という呪文を唱えたら、その中に現れる同じ言葉が２回続けて現れる箇所は、以下の６箇所になります。
⚫

１文字目から始まる abababab の１箇所（abab が２回続けて現れる）。

⚫
⚫

１文字目、３文字目、５文字目からそれぞれ始まる abab の３箇所（ab が２回続けて現れる）。
２文字目と４文字目からそれぞれ始まる baba の２箇所（ba が２回続けて現れる）。

祈りを成就させるためには、どんな呪文を唱えたときも、あなたはそのような箇所の個数を正確に答えなければなりません。

課題
文字列が与えられたとき、その中に同じ文字列が２回続けて現れる箇所の個数を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
str
１行に英小文字からなる文字列strが与えられる。ただし、strの長さは3以上100,000以下である。

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

出力与えられた文字列の中に同じ文字列が２回続けて現れる箇所の個数を 1 行に出力する。

入出力例
入力例１abababab

出力例１6

入力例２aaaaaaa

出力例２1219/21

問題１３

ツリーキーボード（１２点）

PCK 博士はコンピュータ用の画期的な入力デバイス、ツリーキーボードを開発した。このキーボードには、それぞれ 1 から N の番号が付けられた N 個のキーが配置されており、それらが N-1 本のワイヤで配線されている。また、どのキーからもいくつかのワイヤをたどっていけば他のキーに到達できる。
キーボードの設定として、各キーには１つの文字を割り当てることができ、これらはいつでも自由に変更することができる。このキーボードでは、あるキーs を押して、次にキーt を押したとき、キーs からキーt に至る最短経路上にあるすべてのキーの文字が順番に 1 回ずつ入力される。このとき、キーs とキーt が同じキーだった場合、文字は一度だけ入力される。

課題
ツリーキーボードの情報、キーボードの設定操作、入力操作が与えられたとき、各入力操作直後の時点までにコンピュータに入力された異なる文字列の数を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N
k1
k2
:
kN
u1 v1
u2 v2
:

uN-1 vN-1
Q
q1
q2
:
qQ
１行目にキーの数 N(1≦N≦100,000)が与えられる。続く N 行に、キー i に最初に設定されている英小文字 ki が与えられる。続く N-1 行にワイヤの情報が与えられる。ui と vi(1≦ui＜vi≦N)は i 番目のワイヤが繋ぐキーの番号である。
続く行に操作の数 Q(1≦Q≦100,000)が与えられる。続く Q 行に各操作が以下の形式で与えられる。
1 s tまたは
2 k c
1 s t は、キーs(1≦s≦N)とキーt(1≦t≦N)を順番に打つ入力操作を表す。2 k c は、キーk(1≦k≦N)の印字文字を英小文字 c に変更する設定操作を表す。
20/21

出力
各入力操作後に、その時点までにコンピュータに入力された異なる文字列の数をそれぞれ１行に出力する。

入出力例
入力例
6出力例
1ab2
2aceb
1 2
2 3
2 4
2 55 64
1 1 6
1 3 4
2 5 c
1 1 521/21