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

全国高等学校パソコンコンクール実行委員会

問題１

２０周年

（１点）

選手の皆さん、パソコン甲子園へようこそ。パソコン甲子園は今年で２０周年を迎えました。２００３
年に第 1 回が開催されてから、これまでにたくさんの高校生が参加してくれました。これからも多くの高校生に支えられて３０周年、４０周年と続けていきたいです。

課題
年が西暦で与えられたとき、その年がパソコン甲子園の第何回目の開催かを求めるプログラムを作成せよ。ただし、パソコン甲子園は２００３年から毎年 1 回開催されるものとする。

入力
入力は以下の形式で与えられる。
𝑌
１行に年𝑌(2,003 ≤ 𝑌 ≤ 2,100)が西暦で与えられる。

出力
第何回目の開催かを表す数を１行に出力する。

入出力例
入力例１2003

出力例１1

入力例２2022

出力例２20問題２

体温測定（２点）

ヤエさんの朝の日課は、起きたらすぐに自分の体温を測ることです。毎朝かかさず体温を測っているので、ヤエさんは自分の平熱を知っています。体温は日によって平熱よりも高くなったり低くなったりしますが、ヤエさんは体温が３７度５分以上のとき、学校を休むことにしています。

課題
ヤエさんが測定した体温とヤエさんの平熱が与えられたとき、測定した体温が３７度５分以上、平熱以上３７度５分未満、平熱未満のどれかを判定するプログラムを作成せよ。ただし、ヤエさんの平熱は、３５度０分以上３６度９分以下であるものとする。

入力
入力は以下の形式で与えられる。
𝑑 𝑚𝑑 𝑚
入力は２行で与えられる。１行目にヤエさんが測定した体温の度𝑑 (34 ≤ 𝑑 ≤ 40)と分𝑚 (0 ≤ 𝑚 ≤ 9)が整数で与えられる。２行目にヤエさんの平熱の度𝑑 (35 ≤ 𝑑 ≤ 36)と分𝑚 (0 ≤ 𝑚 ≤ 9)が整数で与えられる。

出力
ヤエさんが測定した体温が３７度５分以上なら「2」、平熱以上３７度５分未満なら「1」、平熱未満なら「0」を１行に出力する。

入出力例
入力例１37 236 5

出力例１1

入力例２36 136 9

出力例２0

入力例３37 836 7

出力例３2

問題３

負けが勝ち

（３点）

アイヅ君はワカマツ君と「負けが勝ち」じゃんけんゲームをします。このゲームでは２人がじゃんけんを３回します。ゲームが始まる前に、アイヅ君は「負けが勝ち」と宣言することができます。宣言しなければ、じゃんけんで勝った回数が多い方がゲームの勝者となります。しかし、宣言するとじゃんけんで負けた回数が多い方がゲームの勝者となります。
２人は自分たちが出すすべての手をあらかじめ決めています。２人の友人であるあなたは、２人が出すすべての手を教えてもらいました。アイヅ君は、「負けが勝ち」と宣言すべきかどうか、あなたにアドバイスを求めています。

課題
３回のじゃんけんでアイヅ君とワカマツ君が出す手が順に与えられる。アイヅ君がワカマツ君に勝つために、「負けが勝ち」と宣言すべきかどうかを判定するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑥 𝑦
𝑥 𝑦
𝑥 𝑦
入力は３行で与えられる。𝑖行目に、𝑖回目にアイヅ君とワカマツ君がそれぞれ出すじゃんけんの手𝑥𝑖 と𝑦 が与えられる。𝑥 と 𝑦 はそれぞれ0, 1, または2であり、0が「グー」、1が「チョキ」、2が「パー」を表す。

出力
アイヅ君が「負けが勝ち」と宣言すべきなら 1、宣言すべきでないなら 0、宣言にかかわらず勝てない場
合は-1 を出力する。

入出力例
入力例１0 1
1 22 2

出力例１0

入力例２0 10 20 2

出力例２1

入力例３1 00 12 2

出力例３-1

問題４グループ（４点）

0 番から𝑁 − 1番まで番号が付けられた学生𝑁人が、校庭で円形に並んでいる。その並びは時計回りに 0番の次は 1 番、1 番の次は 2 番、…という順番になっていて、𝑁 − 1番の次は 0 番となっている。学生たちの中には隣の学生と手をつないでいる者もおり、手をつないでいる一続きの学生同士は一つのグループである。また、手を誰とも繋いでいない一人だけの学生も一つのグループである。

課題
それぞれの学生について、次の番号の学生と手をつないでいるかを表す情報が与えられたとき、グループの数を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝑐𝑐:𝑐
１行目に学生の人数𝑁(3 ≤ 𝑁 ≤ 100)が与えられる。続く𝑁行に、𝑖番目の学生が𝑖 + 1番目の学生と手をつないでいるかどうかを表す数𝑐 (0または1)が与えられる。𝑐 が0のときは手をつないでいないことを表し、1のときは手をつないでいることを表す。ただし、𝑐(𝑖 = 𝑁 − 1のとき)は、𝑁 − 1番目と0番目の学生が手をつないでいるかどうかを表す。

出力グループの数を１行に出力する。

入出力例
入力例１510010

出力例１3

入力例２3101

出力例２1問題５

ゆパスタの茹で具合（６点）

パスタ博士である PCK 君は、毎晩パスタを調理して食べている。調理に使用するパスタは同じ製品で、ゆ茹で時間が短い順に「茹で足りない」「ちょうど良い」「茹ですぎ」のように茹で具合が変化する。パス
タの茹で具合は茹で時間だけで決まるので、茹で時間が同じなら同じ茹で具合になる。
PCK 君は様々な時間でパスタを調理したときの茹で具合の記録を𝑁日間取っており、さらに𝑀日間、様々な茹で時間でパスタを調理する予定である。

課題
パスタの茹で具合の記録を取った日数、それぞれの日のパスタの茹で時間と茹で具合、これからパスタを調理する日数、それぞれのパスタの茹で時間が与えられたとき、それぞれのパスタが「茹で足りない」「ちょうど良い」「茹ですぎ」または「判断できない」のどれであるかを判定するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝑎 𝑠𝑎 𝑠:𝑎 𝑠𝑀𝑏𝑏:𝑏
１行目に、記録を取った日数𝑁 (1 ≤ 𝑁 ≤ 100)が与えられる。
続く𝑁行に、𝑖日目の調理から得られた茹で時間𝑎 (1 ≤ 𝑎 ≤ 1,000,000,000)と茹で具合𝑠 (0 ≤ s ≤ 2)が整数で与えられる。𝑠 はパスタを𝑎 分間茹でたときの茹で具合であり、0のとき「茹で足りない」、1のとき「ちょうど良い」、2のとき「茹ですぎ」を表す。ただし、𝑖 ≠ 𝑗ならば𝑎 ≠ 𝑎 、かつ、𝑠 < 𝑠 ならば 𝑎 < 𝑎 とする。
続く１行に、これから調理する日数𝑀 (1 ≤ 𝑀 ≤ 100)が与えられる。
続く𝑀行に、それぞれの日に調理するパスタの茹で時間𝑏 (1 ≤ 𝑏 ≤ 1,000,000,000)が整数で与えられる。

出力
パスタを𝑏 分間茹でたときの茹で具合を𝑖行目に出力する。
「茹で足りない」「ちょうど良い」「茹ですぎ」または「判断できない」をそれぞれ 0, 1, 2, -1 で表すものとする。

入出力例
入力例１49 23 07 15 15122965

出力例１20211

入力例２54 16 21 08 23 1447102

出力例２122-1

パスタを7分間茹でた場合と10分間茹でた場合の茹で具合は、6分間茹でた場合の茹で具合から「茹ですぎ」と判断できる。いっぽう、1分間茹でた場合と3分間茹でた場合の茹で具合が異なることから、パスタを2分間茹でた場合の茹で具合は判断できない。
入力例３21 0
3 212

出力例３-1

茹で時間が1分と3分の場合の茹で具合がそれぞれ「茹で足りない」と「茹ですぎ」であることが分かっている。このとき、ちょうど良い茹で具合になる茹で時間の範囲は、1分過ぎから2分未満まで、1分過ぎから3分未満まで、2分過ぎから3分未満まで、の３つの場合があり得る。これらの場合で、2分での茹で具合はそれぞれ「茹ですぎ」、「ちょうど良い」、「茹で足りない」となる。このため、パスタを2分間茹でた場合の茹で具合は判断できない。

問題６スプリットタイム（６点）

カクマ君は体力測定の持久走に参加した。カクマ君は運動場のトラックを時刻０に走り始めて、トラックを周回する。この持久走では、スタートから１周、２周、…、𝑁周したときの目標経過時間（スプリットタイム）がそれぞれ決められていて、カクマ君はそれらにしたがって以下のように走らなければならない。


𝑖周したときの目標経過時間より早くカクマ君が𝑖周したときは、𝑖周走り終えたところで目標経過時間になるまで立ち止まる。目標経過時間になった瞬間に持久走を再開し、𝑖 + 1周目を走り始める。



それ以外の場合は、カクマ君は立ち止まらずに走り続ける。

カクマ君が２周続けて目標経過時間よりも遅れて周回したとき持久走は終了となる。２周続けて目標経過時間よりも遅れて周回することなくトラックを𝑁周できたときにも、持久走は終了となる。目標経過
時間に遅れずに周回した回数がカクマ君の記録になる。たとえば、１周、２周、４周したときには遅れずに周回し、３周、５周、６周したときには遅れて周回したなら、６周したところで終了し、記録は３回になる。

課題
カクマ君がトラックを１周するのにかかる時間と、各周回後のスタートからの目標経過時間が与えられたとき、カクマ君の記録を求めるプログラムを作成せよ。ただし、カクマ君がトラックを１周するのにかかる時間はつねに一定とする。

入力
入力は以下の形式で与えられる。
𝑁𝑇𝑎 𝑎 …𝑎
１行目に、周回の最大数𝑁(1 ≤ 𝑁 ≤ 100)とカクマ君がトラックを１周するのにかかる時間𝑇(1 ≤ 𝑇 ≤1,000,000)が与えられる。２行目に、𝑖周したときの目標経過時間 𝑎 (1 ≤ 𝑎 ≤ 1,000,000,000)が与えられる。ただし、𝑎 < 𝑎 である。

出力
カクマ君の記録を 1 行に出力する。

入出力例
入力例１6 1012 25 32 40 53 61

出力例１2

カクマ君は10分で周回するので、最初に1周した後2分立ち止まり、スタートから12分経過後に2周目を走り始める。2周するのはスタートから22分経過後なので、3分立ち止まって25分経過後に3周目を走り始める。しかし、スタートから32分経過するまでに3周することはできず、そのまま走り始めても40分経過するまでに4周できないので4周で終了する。目標経過時間に遅れず周回したのは、それぞれ1周、2周したときなので、カクマ君の記録は2回である。
入力例２7 810 20 25 38 43 52 68

出力例２3

最初の2周は目標経過時間に遅れず、スタートから20分経過後に3周目を走り始める。25分経過までには3周できないが、そのまま走り続けて38分経過するまでに4周できる。しかし、38分経過後から5周目を走り始めると、スタートから43分経過するまでには5周できず、そのまま走り続けても52分経過するまでには6周できないので、6周で終了となる。目標経過時間に遅れず周回したのは、それぞれ1周、2周、4周したときなので、カクマ君の記録は3回である。

問題７

税の徴収

（８点）

イヅア村には１から𝑁までの番号が付いた𝑁軒の家がある。この村では、𝑀人の徴税官が税を徴収する。
徴税官は家を訪れて税金を徴収する。1 軒の家で徴収する金額は、徴税官ごとに決まっている。
はじめに、徴税官はそれぞれ異なる家に派遣され、そこで税金を徴収する。
次に、徴税官がいる家のうち番号が一番小さい家にいる徴税官が、それよりも大きい番号の家のうち、まだ徴税が済んでいない最も番号が小さい家に移動し、そこで税金を徴収する。これを繰り返し、どの徴税官も税金を徴収できなくなったら徴収を終える。

課題
家の軒数と徴税官の人数、各徴税官が徴収する金額と最初に派遣される家の番号が与えられたとき、イヅア村から徴収できる税金の総額を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝑀𝑡 ℎ𝑡 ℎ:𝑡 ℎ１行目に家の軒数𝑁(1 ≤ 𝑁 ≤ 100,000)と徴税官の人数𝑀(1 ≤ 𝑀 ≤ 𝑁)が与えられる。続く𝑀行に𝑖番目の徴税官が徴収する税金の金額𝑡 (1 ≤ 𝑡 ≤ 10,000)と最初に派遣される家の番号ℎ (1 ≤ ℎ ≤ 𝑁)が与えられる。ただし、異なる徴税官が同じ家に最初に派遣されることはない（𝑖 ≠ 𝑗ならばℎ ≠ ℎ ）。

出力
イヅア村から徴収できる税金の総額を 1 行に出力する。

入出力例
入力例１6 22 13 3

出力例１14入力例２7 33 42 35 7

出力例２15問題８一方通行迷路ゲーム（１０点）

あなたは一方通行迷路ゲームというコンピュータゲームで遊んでいる。このゲームでは、𝐻行𝑊列のマスで区切られた長方形が画面上に表示される。各マスは壁、道、スタート、ゴールのいずれかで、スタートとゴールはそれぞれ一つだけである。道のマスとスタートのマスでは、上下左右に隣接する道のマスかゴールのマスだけに進むことができる。ただし、道のマスのうちいくつかは一方通行のマスであり、上下左右のうち一つの方向にしか出られない。
1 回のゲームでは、スタートから出発して道を通ってゴールを目指す。ゴールにたどりつければゲームクリア、たどりつけないことがわかった時点でゲームオーバーである。スタートからゴールまでの移動回数が少ないほど、ランキングが上がる。ゲーム中で一度だけ、一方通行のマスを一つ選んでその方向を好きな方向に変えることができる。ランキング上位を目指すために、あなたは画面をよく見て、どの一方通行のマスを選んで方向を変えればいいか、よく検討しなければならない。

課題
画面上に各マスの情報が与えられたとき、スタートからゴールにたどりつけるかどうか判定し、たどりつけるときは最小の移動回数を報告するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝐻𝑊𝑠 , 𝑠 , ⋯𝑠 ,𝑠 , 𝑠 , ⋯𝑠 ,:𝑠 , 𝑠 , ⋯𝑠 ,１行目に画面上の長方形の行の数𝐻(2 ≤ 𝐻 ≤ 300)、列の数𝑊(2 ≤ 𝑊 ≤ 300)が与えられる。続く𝐻行に𝑖行𝑗列目のマスを表す文字𝑠 , が与えられる。各𝑠 , は以下のどれか一つである。
.

一方通行ではない道#

壁U, D, L, R

一方通行の道。それぞれ、上、下、左、右の方向へだけ出られるマスを表す。

S, G

Sがスタート、Gがゴール。

出力スタートからゴールにたどりつく最小の移動回数を 1 行に出力する。ただし、たどりつけないときは「-1」を出力する。

入出力例
入力例１4 5
##S##
#..##
#.DG.
#..##

出力例１3

入力例２
4 3
#S.
#U.
GD.
###

出力例２5

入力例３
3 4
#..#
.LDG
.S#.

出力例３-1

問題９

パスワードをお忘れですか？

（１２点）

二郎君は数式を用いたセキュリティシステムを開発した。システムには a、b、c、d を変数とする数式が設定されており、それぞれに０から９までの整数を入力すると計算が行われる。その計算結果が正の整数𝑁と一致したとき、ロックが解除される。ロックを解除できる４つの整数を a,b,c,d の順に並べた４桁の数字の列がパスワードになる。
二郎君はこのシステムで彼が使っているパスワードを忘れてしまった。幸い、二郎君はシステムに設定されている数式と、𝑁の値は覚えていたので、それを使ってパスワードを特定しようと考えた。

課題
システムに設定されている数式と正の整数𝑁が与えられたとき、パスワードの候補の数を求めるプログ
ラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑆𝑁
１行目にシステムに設定されている数式を表す文字列𝑆が与えられる。２行目に、整数𝑁(1 ≤ 𝑁 ≤ 10,000,000,000,000,000 = 10の16乗)が与えられる。
𝑆は算術式を表す文字列であり、以下の要素から構成される。


加減乗算（それぞれ +, -, *）。



カッコ「(」または「)」。
0から10,000までの整数。
変数a,b,c,d。
変数の連結。

変数が連続して与えられた場合は変数の連結を表し、それらの変数の値を並べてできる一つの数とみなす。たとえば、a=0、b=1、c=2なら、abcは一つの整数12を表す。
また、𝑆は以下の条件を満たす。


符号を反転する記号として演算子-が使われることはない。
乗算を表すときに演算子*が省略されることはない。
𝑆の長さは200以下である。
乗算演算子*は２回までしか現れない。
変数が連続するのは４つまでである（たとえば、abcda, aaabb, aaaaaaのようなものは与えられない）。
空白文字は含まれない。
変数の連結を除いて、通常の数式である。

出力
パスワードの候補の数を１行目に出力する。パスワードがひとつに特定できる場合は、それを２行目に出力する。

入出力例
入力例１a+b+c+d36

出力例１19999

入力例２a+b+c+d5

出力例２56

式a+b+c+dが5になるのはa=b=c=0,d=5のときだが、他にもa=b=c=1,d=2などでも5になるので、合計で56通りの候補が存在する。

入力例３b+c+d27

出力例３10式b+c+dが27になるのはb=c=d=9のときだが、aの選び方は任意なので10通りの候補が存在する。

入力例４abcd+abcd1024

出力例４
10512

式abcd+abcdが1024になるのはa=0,b=5,c=1,d=2のときだけなので、候補は１つだけであり、0512が唯一のパスワードである。

問題１０

テレポート移動網（１２点）

人類は研究の末、ついにテレポート装置を利用した移動網を構築できるようになった。テレポート装置が設置できるのは 1 から𝑁までの番号が付いた地点だけで、全部で𝑀台のテレポート装置が設置されている。𝑖番目のテレポート装置は地点𝑎 に設置されており、移動先𝑏 と使用コスト𝑓 が設定されている。
地点𝑎 にいる利用者は使用コスト𝑓 を支払うと地点𝑏 に移動できる。
テレポート装置の利用者は事前に申請をすれば、装置を他の地点に移設できる。装置１台を１つ離れた番号の地点に移設するごとに申請が１回必要で、１回当たり申請コスト𝐶がかかる。申請には以下のルールがある。


１回の申請では、装置 1 台を移設前の地点から番号が１つだけ離れた地点にだけ移設できる。たとえば、地点 7 にあるテレポート装置は地点 6 か 8 だけに移設できる。また、地点 1 にある装置は 2だけに、地点𝑁にある装置は𝑁 −1 だけにそれぞれ移設できる。
装置が移設されても、その装置により利用者が移動できる地点や使用コストは移設前と変わらない。
同じ装置の移設は何度でも申請することができる。

同じ装置の移設を何度も申請することで、２つ以上番号が離れた地点へ移設させることができる。たとえば、地点 5 にある装置を地点 8 に移設したいときは、5 から 6、6 から 7、7 から 8 への各移設のために３回の申請が必要で、そのために 3×𝐶の申請コストがかかる。
あなたは、テレポート装置を利用して地点１から地点𝑁まで移動する計画を立てているが、使用コストと申請コストの総和をできるだけ少なくして出費を抑えたいと思っている。

課題
テレポート装置の情報と 1 回あたりの申請コストが与えられたとき、利用者が地点 1 から地点𝑁へテレポートだけで移動するのにかかる、使用コストと装置の移設に必要な申請コストの総和の最小値を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝑀𝐶𝑎 𝑏 𝑓𝑎 𝑏 𝑓:
𝑎 𝑏 𝑓
１行目に、地点の数𝑁(2 ≤ 𝑁 ≤ 200,000)、テレポート装置の数𝑀(1 ≤ 𝑀 ≤ 100,000)、１回あたりの申請コスト𝐶(1 ≤ 𝐶 ≤ 1,000)が与えられる。続く𝑀行に、𝑖番目のテレポート装置が設置されている地点の番号𝑎 (1 ≤ 𝑎 ≤ 𝑁)、転送先の地点の番号𝑏 (1 ≤ 𝑏 ≤ 𝑁)、使用コスト𝑓 (1 ≤ 𝑓 ≤ 1,000)が与えられる。入力はすべて整数である。

出力コストの総和の最小値を１行に出力する。ただし、どのようにしてもたどり着けない場合は、-1 を出力する。

入出力例
入力例１9 2 33 6 1
5 9 7

出力例１17入力例２3 3 13 1 13 2 1
1 2 1

出力例２-1

入力例３10 4 1
1 9 1
5 10 19 5 3
10 5 1

出力例３4

申請コスト１を使って地点１０にあるテレポート装置を地点９に移設することで、利用者は地点１から地点１０へ使用コスト３で移動することができるので、コストの総和の最小値は４になる。

問題１１

農地開発

（３６点）

イヅア国では国内にある広大な土地を利用して、複数の農園を開拓することになった。
イヅア国ではすでに𝑁箇所の農園が開拓されており、農園には 1 から𝑁までの番号がついている。農園の間にはそれらを直接つなぐ道が、全部で𝑁 − 1本ある。どの道も同じ長さで、どちらの方向にも通ることができる。また、どの農園からでも、いくつかの道を通っていくことで他のどの農園にも到達できる。
また、それぞれの農園では、その農園の収支を記録している。
あなたは新しい任務としてイヅア国の農園の拡張と管理を任される予定である。上司から、以下の２種類の作業をいくつか組み合わせた指示を受け取ることになった。
作業１：農園を新たに開拓し、すでにある農園との間に道を作り接続する。新たに作る道の長さはすでにある道の長さと同じとする。

作業２：農園を２つ指定し、それらの農園をつなぐ最短の経路を見つける。その経路上にある農園の中から、𝑘番目に収支の少ない農園の収支を報告する。

あなたは任務が始まる前に、報告すべき収支を計算するプログラムを作っておこうと考えている。

課題
現在の農園の情報と、それぞれの作業に関する情報が与えられたとき、報告すべき農園の収支を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝑀𝑏𝑏：
𝑏𝑠 𝑡𝑠 𝑡：𝑠𝑡𝑜𝑝
𝑜𝑝：𝑜𝑝
１行目に、すでにある農園の数𝑁(2 ≤ 𝑁 ≤ 100,000)と作業の数𝑀(1 ≤ 𝑀 ≤ 100,000)が与えられる。続く𝑁行に、𝑖番目の農園の収支𝑏 (−1,000,000 ≤ 𝑏 ≤ 1,000,000)が整数で与えられる。続く𝑁 − 1行に、２つの農園を直接つなぐ道の情報が与えられる。𝑠 と𝑡 (1 ≤ 𝑠 < 𝑡 ≤ 𝑁)は、𝑖番目の道がつなぐ２つの農園の番号である。ただし、どの２つの農園についても、それらを直接つなぐ道は１本以下とする。
続く𝑀行に、作業を示す情報𝑜𝑝 が与えられる。各𝑜𝑝 は以下のいずれかの形式で与えられる。

1𝑢𝑤
または
2𝑢𝑣𝑘
以下では、作業を実行する前の農園の数を𝑃とする。最初の文字が1の場合、番号が𝑃 + 1となる農園を新たに作り、農園𝑢(1 ≤ 𝑢 ≤ 𝑃)との間に道を作り接続する作業を示す。その収支は𝑤(−1,000,000 ≤𝑤 ≤ 1,000,000)である。
最初の文字が2の場合、農園𝑢(1 ≤ 𝑢 ≤ 𝑃)と農園𝑣(1 ≤ 𝑣 ≤ 𝑃)を最短の道のりでたどったときに訪れるすべての農園の収支のうち、少ないほうから𝑘(1 ≤ 𝑘 ≤ 𝑃)番目の収支を報告する作業を示す。ただし、𝑘はこの指示で訪れる農園の数を超えない。

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

出力収支を報告する作業ごとに、農園の収支を出力する。

入出力例
入力例
5 9131141 22 32 44 5
2 2 5 21 2 2
2 5 6 22 5 6 32 5 6 11 6 5
1 6 7
2 1 8 32 1 8 4

出力例323137