N 個の整数からなる列 A = (a₁, a₂, ..., a_N) が与えられる．A を昇順に並べかえたとき，連続する整数が続く区間の長さの最大値を求めよ．

ここで，(a_l, a_l+1, ..., a_r-1, a_r) が「連続する整数が続く区間である」とは，a_l から a_r にかけて値が 1 ずつ増加していることをいう．例えば (3, 4, 5, 6) や (0, 1, 2, 3, 4, 5)，(1) は連続する整数が続く区間であるが，(7, 7, 7) や (1, 3, 4, 5) は連続する整数が続く区間ではない．

入力は複数のデータセットからなる．各データセットは次の形式で表される．

N a₁ a₂ ... a_N

各データセットは 2 行からなる．最初の行には数列の長さ N (1 ≤ N ≤ 100) がある．次の行には空白で区切られた N 個の整数 a₁, a₂, ..., a_N がある．ここで a₁ から a_N はすべて 0 以上 10,000 以下である．また，数列内の要素の値はすべて異なることが保証される．

入力の終わりはゼロひとつを含む行で示す．データセットは 50 個以内である．

各データセットに対して，数列を昇順に並べたときの，連続する整数が続く区間の長さの最大値を求めよ．

9
12 2 13 3 6 8 9 7 1
5
9 7 5 3 1
13
153 156 150 152 162 154 159 155 158 151 160 161 157
9
100 101 102 200 201 202 300 301 302
0

4
1
13
3

鐘星くんの今月のお小遣いの金額は，次のようなゲームで決まることになった．

1. はじめに，N 枚のカードが横一列に並んでいる．それぞれのカードには，1 から 9 までのいずれかの数字が 1 つ書かれている．また，整数 K が指定される．ここで N は K の倍数である．
2. 鐘星くんは，これら N 枚のカードの中から，何枚かのカードを選んで破り捨てることができる．ここで，破り捨てるカードの枚数は，K の倍数でなければならない．なお，1 枚も破り捨てなくてもよいし，N 枚全部破り捨ててもよい．
3. 残ったカードの枚数は K の倍数である．これらのカードを，順番を変えることなく，左から順に K 枚ずつのグループに分ける．
4. それぞれのグループのカードに書かれた数字を，K 桁の十進数とみなす．これら K 桁の数をすべて足し合わせた値が，鐘星くんの今月のお小遣いの金額となる．

たとえば，N = 9, K = 3 で，カードに書かれた数字が左から順に 2, 9, 9, 7, 9, 2, 4, 5, 8 であったとする．これらのカードを 1 枚も破り捨てない場合，鐘星くんの今月のお小遣いは 299 + 792 + 458 = 1549 円である．一方，1 枚目，6 枚目，7 枚目の計 3 枚のカードを破り捨てる場合，残った 6 枚のカードに書かれた数字は左から順に 9, 9, 7, 9, 5, 8 となり，お小遣いは 997 + 958 = 1955 円となる．なお，すべてのカードを破り捨てた場合，お小遣いは 0 円である．

鐘星くんが破り捨てるカードを適切に選んだとき，今月のお小遣いは最大でいくらになるだろうか．

入力は 50 個以下のデータセットからなる．各データセットは次の形式で表される．

K s₁s₂...s_N

1 行目には整数 K が与えられる．K は 2 以上 14 以下であることが保証される．

2 行目には文字列が与えられ，その長さが N である．N は K 以上 200,000 以下の整数であり，かつ K の倍数であることが保証される．また，この文字列の i 番目の文字 s_i は，はじめに左から i 番目のカードに書かれている数字であり，1 以上 9 以下であることが保証される．

入力の終わりは 1 つのゼロからなる行で表される．

各データセットに対し，鐘星くんの今月のお小遣いの最大値を表す整数を，1 行に出力せよ．

なお，この問題の制約から，答えが 2⁶³ 未満であることは証明できる．ただし，32 ビット整数型では表現できない場合があることに注意せよ．

3
299792458
14
37828944296678
2
9335413296572977435242595825577315838186532253894144498711392753253512
0

1955
37828944296678
2022

文字数が多い英単語はしばしば，前後の1文字ずつだけを残し，それ以外の中間部分をその文字数で置き換える形で省略されることがある． たとえば，"internationalization" は "i18n"，"localization" は "l10n"，"accessibility" は "a11y" などと略記される． ここではこの略記を一般化し，前後の文字を 1 文字以上であれば好きなだけ残してよいものとし，この表記を「字数略記」と呼ぶこととする． 例えば，"i18n"，"int13tion"，"i1ternationalization" はいずれも "internationalization" の字数略記であるが，"i123n"，"i4national3tion"，"19n" はいずれも "internationalization" の字数略記ではない．ただし，どの区間も字数に置き換えないそのままの "internationalization" も，"internationalization" の字数略記として有効であるものとする．

あなたは，英小文字のみからなる単語が N 個含まれた辞書を持っており，この辞書内の単語をそれぞれ字数略記に変換した辞書を作ろうと思っている． ここで，もしもある字数略記が変換前の辞書に含まれる複数の単語の字数略記として有効であると，その字数略記だけを見て元の単語を一意に復元することができなくなってしまう．よって，そのような字数略記を変換後の辞書に含めることはできない． 例えば，"love" と "live" がともに辞書に含まれる場合，いずれかでも "l2e" という字数略記に変換してしまうと，"l2e" を見たときに元が "love" だったのか "live" だったのかわからず，復元できなくなってしまう．この場合，例えば "love" を "lo1e"，"live" を "li1e" と字数略記すれば，いずれも元の単語を一意に特定することができる．

与えられた辞書に対し，字数略記変換後の辞書として考えられるもののうち，変換に使用した整数の和として考えられるものの最大値を求めよ． ただし，単語そのままを字数略記とする場合に使用した整数は，0 であるとみなす．

入力は 50 個以下のデータセットからなる．各データセットは次の形式で表される．

N s₁ s₂ ... s_N

最初の行は辞書に含まれる単語の個数 N からなる (1 ≤ N ≤1,000)．続く N 行には，変換前の辞書に含まれる単語が，各行ごとに 1 つ与えられる．各単語の長さは 3 以上 30 以下であり，英小文字アルファベットのみからなる．辞書に含まれる単語はすべて相異なることが保証される．

入力の終わりは，1 つのゼロからなる行で表される．

各データセットについて，各単語を一意に復元できるよう字数略記に変換するとき，使用した整数の和の最大値を 1 行に出力せよ．

5
abcxxfg
abcyyfg
abcdefx
azcdefg
www
3
internationalization
localization
accessibility
4
love
live
cat
cut
3
class
comes
cross
2
aaa
aaaaaaaaaa
0

16
39
2
6
9

二次元平面上に凸 N 角形がある．各頂点には反時計回りに 1 から N までの番号がつけられている．

この多角形の周上に，三点 P, Q, R がある．はじめ，P, Q, R はそれぞれ，多角形の頂点 k_P, k_Q, k_R と同じ座標にある．その後，P, Q, R は同じ速さで，多角形の周上を反時計回りに一周する．

時々刻々と変化する三角形 PQR の形状．あなたには，この三角形の面積の最小値を求めてほしい．なお，P, Q, R が同一直線上に存在する場合，三角形 PQR の面積は 0 であるものとみなす．

入力は 50 個以下のデータセットからなる．各データセットは次の形式で表される．

N K_P K_Q K_R x₁ y₁ ... x_N y_N

• N は凸多角形の頂点数であり，3 ≤ N ≤ 1,000 を満たす．
• K_P, K_Q, K_R はそれぞれ，点 P, Q, R がはじめに存在する頂点の番号であり，1 ≤ K_P < K_Q < K_R ≤ N を満たす．
• 各 (x_i, y_i) は凸多角形の i 番目の頂点の座標であり，-10,000 ≤ x_i,y_i ≤ 10,000 を満たす．凸多角形の座標は反時計回りで与えられることが保証される．
• 入力される数値はいずれも整数である．

入力の終わりは 4 つのゼロからなる行で表される．

各データセットに対し，三角形 PQR の面積の最小値を，一行に出力せよ．出力は 10^-4 を超える誤差を含んではならない．

4 1 2 3
10 10
-10 10
-10 -10
10 -10
3 1 2 3
-10 -10
10 -10
0 10
0 0 0 0

100.000000000000000
49.442719099991588

正の整数 M, A が与えられる．整数 x が以下の条件をすべて満たすとき，x は良い整数である．良い整数の個数を求めよ．

• 1 ≤ x < M．
• M と x は互いに素．
• M と A の最大公約数を g とするとき，Ax ≡ g (mod M)．

入力は 500 個以下のデータセットからなる．各データセットは次の形式で表される．

M A

各データセットは整数 M と A を含む 1 行からなる．2 ≤ M ≤ 10¹² および 1 ≤ A < M を満たすことが保証される．

入力の終わりは 2 つのゼロからなる行で表される．

各データセットに対し，良い整数の個数を 1 行に出力せよ．

6 4
5040 128
1000000000000 500000000000
0 0

1
8
400000000000

あなたは K 人からなる勇者グループの一員である．あなたたち勇者グループの目的は N 階ダンジョンの最終層（第 N 階層）にいる魔王を倒すことであるが，何回このダンジョンに挑んでも魔王に手も足も出ずに困っている． 手も足も出ない原因の一つは，各階層に存在する門番モンスターの存在である．第 1 層から第 N-1 階層までの各階層では門番モンスターが次の階層への階段を守っており，彼らを倒して進んでいくと魔王の下に辿り着くまでに消耗してしまう．

そこで，あなたたちはダンジョンに潜む M 人の魔女を頼ることにした．i 番目の魔女はダンジョンの第 S_i 階層に潜んでおり，第 S_i 階層にいるときにお金を払うと，その人をより深い階層である第 T_i 階層までワープさせてくれる．魔女は最初の一人目は C_i 円でワープさせてくれるが，足元を見るのが得意なので，一人ワープさせるにつれて D_i 円ずつ金額を上乗せしてくることがわかっている．より正確に表すと，i 番目の魔女がこれまで j 人ワープさせていた場合，i 番目の魔女の次のワープにかかる金額は C_i + j × D_i である．一人の魔女が複数人を同時にワープさせることはないため，複数人で同時に魔女のもとへ訪れたからといって金額が安くなることはない．

また，魔女にお金を払ってワープさせてもらうと，その魔女が知っている魔王に関する情報を教えてくれる，ということがわかった．あなたたちは万全を期すために，M 人全員の魔女から魔王に関する情報を仕入れたい．

よって，あなたたちは K 人バラバラにダンジョンの第 1 階層に入り，それぞれが魔女から情報を仕入れ，第 N 階層で K 人全員で集合することにした．このときに情報を統合すると M 人の魔女全員分の情報が集まっているようにしたい．なお，門番モンスターを倒せば魔女に頼らなくても 1 つ上または下の階層に移動できるが，門番モンスターとの戦闘による消耗を避けるため，魔女によるワープ以外では階層を跨がないようにしたい．

あなたたちはお金を無限に持っているわけではないので，なるべく魔女に払う金額の合計を少なくしたい．K 人を最適に行動させたとき，魔女に払う金額の合計は最小でいくらになるだろうか？

入力は複数のデータセットからなる．各データセットは次の形式で表される．

N M K S₁ T₁ C₁ D₁ ... S_M T_M C_M D_M

• N はダンジョンの階層数を表す整数であり，2 ≤ N ≤ 500 を満たす．
• M は魔女の人数を表す整数であり，1 ≤ M ≤ 500 を満たす．
• K は勇者グループの人数を表す整数であり，1 ≤ K ≤ 5,000 を満たす．
• 各 i = 1, 2, ... , M について，S_i は i 番目の魔女がいる階層，T_i はワープ先の階層，C_i はワープの初期金額，D_i は上乗せ金額を表す整数であり，1 ≤ S_i < T_i ≤ N, 1 ≤ C_i ≤ 10⁹, 1 ≤ D_i ≤ 10⁹ を満たす．
• i ≠ j なる i, j について，(S_i, T_i) ≠ (S_j, T_j) を満たす．
• 各魔女について，その魔女のワープを経由しつつ第 1 階層から第 N 階層へ魔女のワープのみを使用して到達する方法が存在する．

入力の終わりは 3 つのゼロからなる行で表される．入力に含まれるデータセットは 50 個以下である．

各データセットに対して，魔女に払う金額の最小値を出力せよ．問題文中の条件を満たすような行動が存在しない場合は代わりに -1 と出力せよ．

3 2 5
1 2 90 2
2 3 10 1
3 3 6
1 2 1 1
2 3 1 4
1 3 18 2
3 3 3
1 2 1 1
2 3 1 4
1 3 18 2
3 3 1
1 2 1 1
2 3 1 4
1 3 18 2
6 7 50
1 2 55 4
1 3 86 3
2 4 13 84
3 4 31 51
3 5 10 78
4 6 1 71
5 6 39 35
0 0 0

530
76
27
-1
72445

あなたは JAG 王国の勇者である．鍛錬を積んでいるあなたの現在の所持金は 10¹⁰⁰ である．

JAG 王国には 1, 2, ..., N で番号付けされた N 個の街がある．また，街 i と街 i+1 (1 ≤ i < N) の間には道路があり，通行すると所持金が C_i 変動する．つまり，C_i が正のときはあなたの所持金が |C_i| だけ増加するが，そうでないときはあなたの所持金が |C_i| だけ減少する．

N 個の街すべてでクエストが発生しているため，勇者であるあなたは冒険に出かけることにした．冒険は以下を満たすものでなければならない．

• 冒険では，N 個すべての街で 1 度ずつクエストを行わなければならない．
• クエストを行う街の順番を (x₁, x₂, ..., x_N) と定めたとする (i ≠ j ならば x_i ≠ x_j)．あなたは街 x₁ を出発地としてクエストを順番に行う．街 x_k から x_k+1 (1 ≤ k < N) へ移動するときは，x_k から x_k+1 まで最短経路で移動しなければならない．ここで「最短経路」とは，通る道路の数が最も少ない経路を指す．
• 街 x_N で最後のクエストを行うと，そこで冒険は終了となる．

冒険が終了した後の所持金をできるだけ多くするには，どのような順番でクエストを行えばよいだろうか？

入力は複数のデータセットからなる．各データセットは次の形式で表される．

N C₁ C₂ ... C_N-1

各データセットは 2 行からなる．最初の行には街の数を表す整数 N (2 ≤ N ≤ 3,000) がある．次の行には空白で区切られた N-1 個の整数 C₁, C₂, ..., C_N-1 がある．C_i は街 i と街 i+1 の間を通行したときに所持金がいくら変動するかを表す値である．ここで C₁ から C_N-1 はすべて -10⁹ 以上 10⁹ 以下である．

入力の終わりはゼロひとつを含む行で示す．データセットは 50 個以内である．

各テストケースに対する出力は 2 行からなる．1 行目では，冒険が終了した後の所持金と，冒険を行う前の所持金との差としてあり得る最大値を出力する．2 行目では，その所持金を達成できるような，クエストを行う街の順番 (x₁, x₂, ..., x_N) をスペース区切りで出力する．

答えとしてあり得るものが複数ある場合は，どれを出力しても正解となる．

4
2 3 4
4
2 -3 4
6
-1 -1 -1 -1 -1
6
-1 -1 100 -1 -1
0

21
2 4 1 3
9
2 1 4 3
-5
1 2 3 4 5 6
492
1 4 3 5 2 6

ICPC 市では毎年7月に，ICPC City Parade Ceremony が開かれる．このお祭りでは多くの屋台が ICPC 市の路上に出店され，多くの市民が屋台を楽しんで巡る．あなたはこのお祭りを効率よく巡りたいと考えた．

ICPC 市は，1 から N までの番号のついた N か所の交差点と，M 本の通りからなる．それぞれの通りは異なる 2 つの交差点を繋ぎ，双方向に通行可能である．複数の通りが同じ交差点の組を直接繋ぐことはない．どの 2 つの交差点についても，いくつかの通りを経由することで，互いに行き来することができる．

お祭りでは，屋台がすべての通りに出店される．お祭りを最大限楽しむためには，全ての屋台を巡るべきである．また，各屋台を何度も見物するのは飽きてしまうため，同じ屋台を 3 回以上通るのは避けたい．更に，同じ通りを連続で行き来するのは，見物したばかりの屋台を通ることになるので遠慮したい．つまり，同じ通りを 2 回通る場合には，間に別の通りを 1 つ以上挟むようにしたい．

果たしてその様な順路が存在するのかと気になったあなたは，ICPC 市の地図を元に，どの交差点の順番で通るべきか解析するプログラムを書くことにした．

ここで，順路とは，任意の交差点から始まり，今いる交差点から延びる通りを一つ選んで別の交差点へ移動することを繰り返し，任意の交差点で終わるものを指す．始めと終わりの交差点は，同じであっても，違っていてもよい．また，ある通りを移動している途中で，元いた交差点へ引き返してはならない．

入力は 50 個以下のデータセットからなる．各データセットは次の形式で表される．

N M a₁ b₁ ... a_M b_M

1 行目には，市の交差点の数を表す整数 N と，通りの数を表す整数 M が空白区切りで与えられる． 続く M 行には， それぞれ空白で区切られた 1 以上 N 以下の相異なる整数 a_i と b_i が与えられ，これは i 番目の通りが交差点 a_i と交差点 b_i を繋いでいる事を表す．ここで，2 つ以上の通りが同じ交差点の組を直接繋ぐことはないことが保証される． N は 2 以上 20,000 以下，M は 1 以上 20,000 以下であることが保証される． 入力の終わりは空白区切りのゼロふたつの行で示す．

各データセットに対し，問題文中の条件を満たす順路が存在するならば，順路上の交差点番号を順番に，空白区切りで一行に出力せよ．答えとしてあり得るものが複数ある場合は，どれを出力しても正解となる．もしもそのような順路が存在しないならば，代わりに -1 を一行に出力せよ．

なお，出力検証機の都合上，改行コードには LF または CR+LF のいずれかを使用せよ．他の問題と異なり，CR のみを使用した場合は誤答扱いとなる．

6 9
1 2
2 3
3 4
4 5
5 6
1 6
1 4
2 5
3 6
5 4
1 2
1 3
1 4
1 5
10 19
1 7
6 8
3 8
2 3
7 9
6 9
3 9
4 9
1 6
8 9
9 10
7 10
4 5
3 4
6 10
6 7
1 9
5 8
2 9
0 0

1 2 3 4 5 6 1 4 5 2 1 6 3
-1
4 9 6 10 9 2 3 8 9 1 6 10 7 1 9 3 4 5 8 6 7 9