時は平成50年春休み．情報学研究科に所属する京子さんは，京都にある某研究パークからの研究室の引越しがやっと終わり，ホッと一息ついていた． 今回の引越しは，古くなった校舎の改修工事によるもので，新年度から工事に伴い校舎の名前が変更されることになっている．

ホッとしていたのもつかの間，京子さんは先生から大学の資料に載っている校舎名を新しい名前に変更するお仕事を頼まれてしまった． しかし編集しなければならない資料には，今までの担当者が仕事を怠っていたせいか，ひとつ古い名前よりもっと古い名前が使われているものもあった．

なんとか京子さんは，平成の間に校舎が改名が行われた年度とその名前のリストを見つけることができた．平成元年度の校舎名は "kogakubu10gokan" であった．
だが引越し作業にとても疲れたので，その資料が作られた年度にこの校舎がどんな名前だったのかを自分の手で調べるのには我慢ならなかった．

そこで京子さんは，プログラミングが得意なあなたに手伝ってとお願いすることにした．
改名の歴史と資料が作られた年度が与えられるのでその年度の校舎の名前を出力するプログラミングを書いてあげよう．

N  Q 
year_1 name_1
year_2 name_2
     ...     
year_N name_N

入出力例

入力例 1

3 12
5 sogo5gokan
10 sogo10gokan
15 sogo15gokan

出力例 1

sogo10gokan

平成12年度の校舎名を出力すればよい．
校舎は，平成元年度の kogakubu10gokan から始まり，平成5年度に sogo5gokan， 平成10年度に sogo10gokan および平成15年度に sogo15gokan に改名されている．

入力例 2

3 10
5 kogakubu11gokan
10 sogo10gokan
15 KyotoUniversityResearchPark

出力例 2

sogo10gokan

平成10年度の校舎名を出力すればよい．
校舎は，平成10年度に sogo10gokan に改名されている．

入力例 3

3 3
5 kogakubu11gokan
10 sogo10gokan
15 KyotoUniversityResearchPark

出力例 3

kogakubu10gokan

平成3年度の校舎名を出力すればよい．
平成元年度から平成4年度までの校舎の名前は "kogakubu10gokan" である．

あなたは動物園に来てライオンを見ている。 この動物園にはn個のライオンのオリがある。 あなたはライオンが全部で何頭いるのか知りたくなったのだが、 一人で数えるのは大変だ。 そこで近くにいた動物園の来園者m人に協力してもらうことにした。

ライオンのオリは、それぞれ1番からn番までの数字がついており、 順番に並んでいる。 一つのオリには0頭以上x頭以下のライオンがいる。

m人の来園者でi番目の人(1 ≤ i ≤ m)には l_i番から r_i番までの 両端を含むすべてのオリのライオンの数の総和を数えてもらった。

この情報を元に、1からn 各オリの中のライオンの数を求めることにした。

n x m
l_1 r_1 s_1
...
l_m r_m s_m

入出力例

入力例 1

3 5 1
1 2 5

出力例 1

2 3 5

その他"4 1 5"や"0 5 5"なども正しい出力である。

入力例 2

4 5 2
1 3 15
3 4 3

出力例 2

-1

条件を満たすライオンの配置が一つもないときは-1を出力せよ。

目の前に M \times N 個のピースでできた板チョコがある． ピースには甘いピースと辛いピースの2種類があり，できるだけ多くの甘いピースを食べたい．

しかし，板チョコの食べ方にはルールがあり，以下のルールを守らなければならない．

• あるピースを食べるためには，そのピースの真上に隣接するピースが存在せず，加えてそのピースの少なくとも左右どちらかにはピースが存在しない必要がある．

例えば，図のような形のチョコレートでは，赤く色付けされたピースを次に食べることができる．

また奇妙なことに，あるピースを食べるとそのピースの上下左右に隣接していてかつまだ食べられていないピースの味が変化する． (甘いピースは辛く，辛いピースは甘くなってしまう)

上手くチョコレートを食べると最大でいくつの甘いピースを食べることができるだろうか?

  M N
  a_{11} … a_{1N}
  a_{21} … a_{2N}
  ︙
  a_{M1} … a_{MN}

入出力例

入力例1

2 3
1 1 1
1 1 1

出力例1

5

入力例2

4 2
1 0
0 1
0 1
0 1

出力例2

8

総合研究7号館の引越しに伴い，研究室にカーペットを敷くことになった． この問題では研究室を上から見たときの床を，二次元平面上の多角形とみなす． 床の形状を表す要素数Nの数列\{a_i\}が与えられる． R_iを，左下の座標が(i,0)で右上の座標が(i+1,a_i)である各辺がx軸またはy軸に平行な長方形の境界及び内部領域とする． このとき，床を表す多角形はR_1 ∪ R_2 ∪ R_3 ∪ … ∪ R_Nによって表される． カーペットは長方形であればどんな大きさのものを何枚でも用意することができる． 以下の条件を満たすようにカーペットを配置し，研究室の床を全て覆いつくしたい．

• カーペットは研究室からはみ出してはいけない．
• カーペットはいくらでも重ねて敷くことが可能である．このとき，カーペットの厚さは無視する．
• カーペットを切り離して利用することはできない．
• カーペットは各辺がx軸またはy軸に平行になるように配置しなければならない．

N
a_1 … a_N

入出力例

入力例1

3
1 2 1

出力例1

2

入力例2

10
1 2 2 1 3 4 3 1 2 2

出力例2

5

友達のいないきつねのボブは，今日は一人ですごろく遊びをして過ごすことにした． 各面に整数a_1,a_2,a_3,a_4,a_5,a_6が書かれた6面ダイスと，駒と，直線上にM個のマスがあり 左から順に1からMまでの番号が割り当てられたすごろく盤を用いることにした． すごろく盤の各マスには指示が数字で書かれており，i番目のマスには数字N_iが書かれている． これは，その値が正なら右，負なら左に，その絶対値だけ駒を移動せよという意味である． すなわち，i+N_i番目のマスに駒を移動せよという意味である． ボブは，以下のようにしてすごろく遊びをする．まず駒をスタート地点に置く． 次にサイコロを振り，サイコロが出た目の数を見て，駒を「現在のマスから右に移動する」か 「左に移動する」か「現在のマスに留まる」かを選択することができる． マスから移動する場合は，サイコロの出目の距離だけ駒を移動して，移動した先のマスの指示に従う． 指示に従って移動した先のマスの指示には従わない． 以後，ボブは上記のようにサイコロを振って駒を移動することを繰り返す． 移動した結果すごろく盤の外に駒が出てしまったらボブの負けであり，誤答(Wrong Answer)と判定される． この問題の目的はこのすごろくをゴールすることである．サイコロを振る回数は3000回以下とする．

入出力形式

入力は以下の形式で与えられる．

M
a_1 a_2 a_3 a_4 a_5 a_6
s g
N_1 ... N_M

Mはすごろく盤のマスの数である． a_1 ... a_6 はサイコロの各面に書かれている整数の値である． sとgはそれぞれすごろく盤のスタートとゴールの番号である． N_iはi番目のマスに書かれている指示である． これらの入力の後， さいころを振った結果を表す値 dice が改行とともに引き続いて入力から与えられる． これは，サイコロを振って出た目が a_dice であることを表す． これに対して，あなたのプログラムは駒を進めるかどうかを決め，その選択を出力しなければならない．駒を右に移動するならば 1 を，左に移動するならば -1 を，現在のマスに留まるならば 0 を出力せよ．出力の後には改行を出力せよ． あなたのプログラムが進むか戻るか留まるかを出力すると，次のサイコロを振った結果を入力から受け取ることができる．これを繰り返す． 例えばC/C++では

scanf("%d", &dice);

としてサイコロの面の番号を受け取り，これに対して左に移動するなら

printf("-1\n"); fflush(stdout);

とする．次に，

scanf("%d", &dice);

とすると，次のサイコロの面の番号を受け取ることが出来る．すごろくにゴールしたら直ちにプログラムを終了せよ． ゴールに辿り着くまでにサイコロを振る回数は3000回以下でなければならない． サイコロを振った回数が途中で3000回を超えた場合，誤答と判定される．

制約

• 2 ≤ M ≤ 300
• 1 ≤ s ≤ M, 1 ≤ g ≤ M
• s \neq g
• 1 ≤ a_i ≤ M-1
• 1 ≤ dice ≤ 6
• N_s = N_g = 0
• マスの命令に従って駒を進めて枠外に出る事はない．
• dice は \{1,2,…,6\} から擬似乱数で一様ランダムに選ばれる．
• いくらサイコロを振ったとしてもゴールできない盤面は与えられない．
• 入力の値は全て整数である．

入出力例1

すごろくの説明
プログラムの出力
プログラムへの入力
サイコロの目
駒の移動後のマスの番号
10
1 6 2 5 3 4
1 10
0 -1 3 -1 3 -2 -6 -5 -7 0

1回目のサイコロ
1
1

1回目のプログラムの出力
0
1
2回目のサイコロ
3
2

2回目のプログラムの出力
1
6
3回目のサイコロ
5
3

3回目のプログラムの出力
0
6
4回目のサイコロ
1
1

4回目のプログラムの出力
-1
8
5回目のサイコロ
3
2

5回目のプログラムの出力
1
10

７歳の誕生日に"彼"は父から告げられた．

「お前が７歳になったということは，私はもう引退だ．今日からお前が７歳教の長だ．
７歳教の戒律により，７歳教の長が７歳の間だけ布教活動を行うことが認められている．
この宇宙船を使って，よりたくさんの人々に７歳教の素晴らしさを広めてきなさい．」

７歳教をよりたくさんの人に広めるために"彼"は，自分の周りの星についての情報を集めた．
"彼"の星の周りには，n 個の惑星があり，惑星は 1, ... , n で番号付けされていることがわかった．
惑星i から 惑星jの間を移動するには，w_i_j (年)の時間がかかることもわかった．

そして，それぞれの星で彼が７歳でいられる時間，つまり布教活動できる時間が異なることがわかった．
それぞれの惑星上では，宇宙暦l_i年1月1日00:00:00以降r_i年1月1日00:00:00より前までの時間帯であれば7歳でいられる．
たとえ一度ある星で７歳以外の年齢になっても，その星で後から７歳になった場合や，別の星で７歳になれば布教活動を再開することができる．

しかしどの星でどれくらい，そしてどの順序で布教活動を行えばより多くの人に７歳教を伝えることができるのか，
"彼"にはわからなかった．そこで"彼"はプログラミングが得意なあなたに助けを求めることにした．

現在は宇宙暦0年1月1日00:00:00であり，"彼"は惑星 s にいる． 惑星間を最適に移動・滞在した場合に布教活動が行える最長の年数，
つまり"彼"が７歳でかつ惑星で過ごす最長の年数Tを求めてあげよう． ただし，年数Tには移動時間は含まれない．

n s
l_1 r_1
     ...     
l_{n} r_{n}
w_{1,1}  w_{1,2} ... w_{1,n}
     ...     
w_{n,1} w_{n,2} ... w_{n,n}

入出力例

入力例 1

2 1
0 100
150 250
0 100
100 0

出力例 1

150

入力例 2

5 1
7 44
10 49
38 48
11 23
11 30
0 1 7 2 7
10 0 3 8 10
4 8 0 2 5
3 2 1 0 4
8 4 3 3 0

出力例 2

41

きつねの次郎は夏休みの自由研究で最大独立集合問題のアルゴリズムを考えている． 最大独立集合問題では，入力として無向グラフ G=(V,E) が与えられる． G の各頂点が白または黒で塗られており，どの辺の端点も少なくとも一方が白く塗られているとき，黒い頂点集合のことを独立集合と呼ぶ． 例えば下図において，図の左部のようなグラフが与えられた時，図の中央部のように色を塗ると黒い頂点集合は独立集合になっているが，一方で図の右部のように色を塗った場合は黒い頂点集合は独立集合になっていない． 問題の目的は，要素数が最大であるような独立集合を求めることである． 便宜上，グラフ G の最大の独立集合の大きさを A(G) と記す．

残念ながらこの問題はNP困難であることが知られており，多項式時間で最適値を求めることは多分できそうにない． そこで，きつねの次郎は理論的には保証がないがなんとなくうまくいきそうな乱択アルゴリズムを考案した．そのアルゴリズムは次のようなものである．

【次郎のアルゴリズム】N=|V| をグラフの頂点数とする． 最初，すべての頂点は白で塗られている． いま，各頂点に 1,2,…,N の番号を，どの2つの頂点も互いに異なる番号を持つように割り当てる． このとき，N! = N \times (N-1) \times (N-2) \times … \times 1 通りの割り当て方が存在するが， これらの中から一様な確率で無作為に割り当てるものとする． 各頂点 v について，もし v に隣接するすべての頂点 w に対して v に割り当てられた番号が w より小さいとき v を黒く塗るということをする． (もし v に隣接する頂点が存在しない場合，アルゴリズムは v を黒く塗るものとする．) そして，黒く塗られた頂点を，問題の解として出力する．

次郎のアルゴリズムの動作例を下図に示す． 図の左部のようなグラフが与えられたとき，各頂点に番号を(無作為に)割り当て，そこから条件を満たす頂点を黒く塗っている．

定義から，このアルゴリズムによって黒く塗られる頂点集合は独立集合になっていることがわかる． アルゴリズムを作り，すっかり自信に満ちた様子の次郎であったが，それを横から見ていたきつねのしえるが突っ込みを入れてきた． そんなアルゴリズムでは全然良い解は出ない，と． 納得しようとしないきつねの次郎にために，しえるは致命的なケースを見せることにした．

E(G) を次郎のアルゴリズムが出力する黒い頂点集合の大きさの期待値とする． 頂点数が40以下の無向グラフで，A(G)-E(G) が最大になるようなものを1つ作り，それを出力せよ．

N
s_{11}s_{12}s_{13}…s_{1n}
s_{21}s_{22}s_{23}…s_{2n}
s_{31}s_{32}s_{33}…s_{3n}
…
s_{n1}s_{n2}s_{n3}…s_{nn}

入出力例

入力例 1

出力例 1

3
NYY
YNY
YYN

この出力は 3 頂点の完全グラフを表す．このグラフでは A(G) = E(G) = 1 であり，致命的なケースには程遠い．

入力例 2

出力例 2

3
NYN
YNY
NYN

この出力は 3 頂点のパスグラフを表す．このグラフでは A(G) = 2，E(G) = (1+1+1+1+2+2)/6 = 4/3 なので， A(G) - E(G) = 2/3 となる．

1以上N以下の整数からなる狭義単調増加数列で，数列の要素からどの2つの異なる数を取ってきても 他方が一方を割り切ることがないようなものを考える． そのような数列のうち，とりうる最大の長さをLとして，そのような数列(a_1,a_2,...,a_L)を考える． この数列のK番目の要素a_Kを求めよ．ただし，そのような数列(a_1...a_L)が複数個存在する場合は， a_Kの値としてとりうる最小の値を出力せよ． また，K > Lのときは-1を出力せよ．

C
N_1 K_1
  …
N_C K_C

制約

• 1 \leq C \leq 10^5
• 1 \leq N_i \leq 10^{18}
• 1 \leq K_i \leq N_i
• 入力値はすべて整数である．

この問題の判定には，50 点分のテストケースのグループが設定されている．このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす．

• C=1, N_i \leq 50

入出力例

入力例1

5
3 2
5 2
8 3
10 1
18 12

出力例1

3
3
5
4
-1

N=3のとき，2番目に小さい要素が最小となる組み合わせの一例として(2,3)が挙げられる．
N=5のとき，2番目に小さい要素が最小となる組み合わせの一例として(2,3,5)が挙げられる．
N=8のとき，3番目に小さい要素が最小となる組み合わせの一例として(3,4,5,7)が挙げられる．
N=10のとき，1番目に小さい要素が最小となる組み合わせの一例として(4,6,7,9,10)が挙げられる．

大きさ N の順列とは，数列 (1, 2, 3, …, N) の各要素を並べ替えたものである． 例えば (5, 2, 1, 4, 3) は大きさ 5 の順列だが，一方で (1, 5, 1, 2, 3) はそうではない．

この問題はリアクティブ方式のタスクである．あなたは応答プログラムと「順列当てゲーム」を行う． まず最初に，応答プログラムは順列 σを1つ内部で決める． 次に，あなたにはこの順列の大きさ N が伝えられる． この後，あなたは応答プログラムに何回か質問をする． そして，応答プログラムの持っている順列を特定することがあなたの目的である．

質問は次のようなものである： 大きさ N の順列 τ を1つ決め，それを応答プログラムに聞くと， 応答プログラムは数列 a_i = (σ上での数字 i の位置と τ 上での数字 i の位置の距離)を計算する． その後，数列 (a₁, a₂, a₃, …, a_N) を昇順に並べて列 (b₁, b₂, b₃, …, b_N) を作り，あなたのプログラムに出力する．

例えば，σ = (5, 2, 1, 4, 3) のとき，τ = (2, 3, 1, 4, 5) を聞くと， 応答プログラムは内部で (a₁, a₂, a₃, a₄, a₅) = (0, 1, 3, 0, 4) を計算し， これをソートした列 (b₁, b₂, b₃, b₄, b₅) = (0, 0, 1, 3, 4) を出力する．

できるだけ少ない質問回数で順列を特定するプログラムを記せ． 採点方法については「採点方式」の項で記す．

入出力形式

まず，順列の大きさ N が入力として与えられる．

N

続いて，あなたのプログラムは何回か応答プログラムに質問をする．質問のフォーマットは以下であるとする．

? τ1 τ2 τ3 … τN

b1 b2 b3 … bN

このやりとりをコード上で実装する場合，C++では例えば次のようになる． 例えば順列 (5, 2, 1, 4, 3) を質問したい場合には，例えば

int tau[5] = {5, 2, 1, 4, 3};
printf("?");
for (int i=0; i<5; ++i) printf(" %d", tau[i]);
printf("\n");
fflush(stdout);

for (int i=0; i<5; ++i) scanf("%d", &b[i]);

何回か質問を行った後，あなたは応答プログラムの持つ順列 σ を特定する．フォーマットは以下の通りとする． (質問のときのフォーマットとほぼ同じで，先頭の ? が ! になっていることに注意せよ．)

! τ1 τ2 τ3 … τN

この問題ではテストデータごとに質問回数の上限値が設定されており，プログラムの行った質問の回数がその上限値を上回ると誤答と判定される．

制約

• 1 ≤ N ≤ 400

採点方式

• 50点分のテストケースグループでは，質問回数の上限値は 1000 回である．
• 750点分のテストケースグループでは，質問回数の上限値は 240 回である．

入出力例1

プログラムの出力
プログラムへの入力
5
? 2 3 1 4 5

0 0 1 3 4
? 1 2 3 4 5

0 0 2 2 4
? 5 4 3 2 1

0 2 2 2 2
? 5 2 1 4 3

0 0 0 0 0
! 5 2 1 4 3

σ = (5, 2, 1, 4, 3) である．何度か質問を行った後に列を特定している．

入出力例2

プログラムの出力
プログラムへの入力
1
! 1

大きさ 1 の順列は 1 つしかないので質問をしなくても直ちに特定することができる．

サイズH×Wの盤面にサイズ1×2のタイルをマス目にそってN個配置する方法が何通りあるか求めたい.

タイルは重なってはいけない. また縦横どちらの向きに置いても構わない.

タイルは全て同じ見た目であり互いに区別しないものとする.

タイルは180度回転しても同じ見た目であり、区別しないものとする.

答えは大きくなる可能性があるので1,000,000,007で割った余りを答えよ

H W N

入出力例

入力例 1

2 2 1

出力例 1

4

次の4通りある。

入力例 2

2 2 2

出力例 2

2

次の2通りある

入力例 3

2 2 3

出力例 3

0

入力例 4

1000000000 1000000000 5

出力例 4

68450176

以下の２条件を全て満たす文字列Tの事を「良い」文字列と呼ぶことにする

• TはABCDEFGHIの9種類の文字列からなる
• T上の連続する２文字は次のグラフ上でも隣接している

「良い」文字列の例

• BEB
• ABCDCBEFGHI

「良い」文字列ではない例

• AC(AとCは隣接していない)
• AABCD(同じ文字はグラフ上では隣接していないとみなす)

• 任意の01列Sに対し,encode(S)は「良い」文字列である
• 任意の01列Sに対し,decode(encode(S))=Sを満たす

入出力形式

この問題にはencodeフェーズとdecodeフェーズがあり, それぞれ独立にプログラムが実行される.

encodeフェーズのとき, 入力は以下の形式で与えられる.

encode
N
S

decode
M
T

採点方式

この問題では入力Sに対する出力encode(S)の長さに応じて得点が決まる.

全てのテストケースについて, |encode(S)| ≦ |S| + 10 を満たすときこの問題に対する得点は満点の1000点となる.

また, |encode(S)| ≦ 2×|S| + 10 を満たす場合, この問題に対する得点は50点となる.

制約

• 1 ≤ N ≤ 300000

入出力例

encodeフェーズ

入力

encode
6
001100

出力

ABCBE

encodeフェーズの終了後あなたのプログラムは一旦終了し,次にdecodeフェーズが開始する

decodeフェーズ

入力

decode
5
ABCBE

001100