横浜くんはケースに入ったクレヨンを持っている．クレヨンの種類は 1 文字で表され，英小文字・英大文字・数字のいずれかで表される．ケースに同じ種類のクレヨンが複数本入っていることもある．

ある日，ケースに入ったクレヨンを家族に貸したところ，種類がバラバラに並んだ状態で返却された．クレヨンをきれいに並べることが好きな横浜くんは，次に示す順番でクレヨンを並べ替えることにした．

• 英小文字はどの英大文字よりも左に並べられ，英大文字はどの数字よりも左に並べられる
• 英小文字の中では，アルファベット順で早いものが左に並べられる
• 英大文字の中では，アルファベット順で早いものが左に並べられる
• 数字の中では，数字が小さいものが左に並べられる

並べ替えたあとのクレヨンの並びを求めよ．

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

S

各データセットは，クレヨンの並びを表した文字列 S の 1 行からなる．S の左から i 番目の文字は，左から i 番目に入っているクレヨンの種類を表す．

S の長さは 1 以上 1,000 以下であり，S は英小文字・英大文字・数字からなる文字列である．

入力の終わりは # のみからなる行で示す．データセットは 50 個以内である．

各データセットに対して，並べ替えたあとのクレヨンの並びを表した文字列を 1 行で出力せよ．

ICPC2023YokohamaRegional
ICPCJapaneseAlumniGroup
GoodLuckForAllContestants
#

aaaeghiklmnoooCCIPRY0223
aaeeilmnnopprsuuACCGIJP
acdekllnnoooorsstttuACFGL

あなたは働いたら負けだと思っている．できることなら，寝て食べてオンラインジャッジを埋めるだけの生活をしていきたい．しかし，現実は世知辛いもので，そのためにはまず先立つ資産が必要である．

あなたは理想の生活を以下のようにモデル化した．あなたはいくらかの初期資産を有している．毎年，生活費が c 必要になるため，保有している資産からちょうど c を年始に一括で現金化し，その現金で生活を行う．その後，現金化していない残りの全資産を 1 年間運用し，あなたの絶対に働きたくないという強い意志がもたらした天賦の資産運用能力により，必ず年末に r %の利率で資産を増やす．すなわち，資産を M だけ運用した場合，年末に資産が M (1 + r / 100) になる．このとき，運用後の資産が非整数となった場合，小数点以下が切り捨てられ整数となる．

あなたはこの理想の生活を y 年間続けたいと思っている．すなわち，ある年の年始から理想の生活を始め，y 年目の年末の時点で資産が非負であるようにしたい．理想の生活のために目標となる初期資産さえわかれば，その初期資産を盾に高らかに辞表を叩きつける未来のために，一時負けを受け入れ労働に甘んじてやらないこともない．そこでまず，モデル化された理想の生活を y 年間続けるために必要な初期資産として最小の整数を求めるプログラムを書くことにした．

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

y c r

y は理想の生活を行う年数であり，1 以上 100,000 以下の整数である．c は 1 年分の生活費であり，1 以上 10⁹ 以下の整数である．r は 1 年間の資産運用による利率であり，1 以上 100 以下の整数である．

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

各データセットに対して，年始に資産が c 減り，年末に残りの資産が r %増える生活を y 年間行うために必要となる最小の初期資産を，整数で 1 行に出力せよ．

3 1000 5
10000 1000000000 100
0 0 0

2860
2000000000

N 種類のゲームがある．これから D 日間，ゲームを一日に一つずつ遊ぶ．あるゲームを複数回遊んでもよく，また一回も遊ばないゲームがあってもよい．

i 番目のゲームの楽しさの初期値は A_i である．このゲームを一日遊ぶと，翌日には，その楽しさは B_i だけ減少する．逆に，このゲームを一日遊ばないでいると，翌日には，その楽しさは（初期値を超えない範囲で） B_i だけ回復する．すなわち，ある日の i 番目のゲームの楽しさが x であった場合，このゲームの翌日の楽しさは，このゲームを遊んだ場合は x - B_i に，遊ばなかった場合は min(x + B_i, A_i) に，それぞれ変化する．

D 日間でのゲームの遊び方として考えられるものは N^D 通りあるが，このうち遊んだゲームの楽しさの合計が最大となるような遊び方をしたときの，その楽しさの合計の値を求めよ．

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

N D A₁ B₁ ... A_N B_N

1 行目には整数 N および D が与えられる．N はゲームの種類数であり，1 ≤ N ≤ 100,000 を満たす．D はゲームを遊ぶ日数であり，1 ≤ D ≤ 100,000 を満たす．

続く N 行には，N 種類のゲームの情報が与えられる．このうち i 番目の行には整数 A_i および B_i が与えられる．A_i は i 番目のゲームの楽しさの初期値であり， 1 ≤ A_i ≤ 100,000 を満たす．B_i は i 番目のゲームを遊んだときの楽しさの減少量であり， 1 ≤ B_i ≤ 100,000 を満たす．

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

各データセットに対し，答えを一行に出力せよ．

2 3
10 10
1 1
1 3
10 1
1 6
3 1
0 0

21
27
3

最初のデータセットでは，ゲーム 1，ゲーム 2，ゲーム 1 の順番で遊んだとき，楽しさの合計が 10 + 1 + 10 = 21 となる．

二番目のデータセットでは，ゲーム 1 を三日連続で遊んだとき，楽しさの合計が 10 + 9 + 8 = 27 となる．

4 人の候補者から 1 人を選出する選挙の投票結果を見てある人がこう言った．「この数字は IPv4 アドレスに見えるね」

あなたはこれを，任意の K つ組について一般化することにした．すなわち，任意の正整数 K について，IPvK アドレスを「0 以上 255 以下の整数の K つ組を . で連結したもの」と定義する．

いま，N 人の有権者と K 人の候補者からなる選挙が行われようとしている．各候補者には 1 から K までの番号が付けられている．各有権者は K 人の候補者の中のいずれかひとりに投票する．ただし，棄権や無効票，按分票はないものとする．したがって，各候補者の得票数は 0 以上の整数であり，かつ，全候補者の得票数の総和は N 票である．なお，無記名投票のため，どの有権者がどの候補者に投票したかは区別しないものとする．

ここで， K 人の候補者の得票数を 1 番の候補者のものから順に . で連結したものであって， IPvK アドレスとみなせるようなものからなる集合を考える．それぞれについて K 人の候補者の得票数の積を求め，それらすべての総和を 998,244,353 で割った余りを求めよ．

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

K N

整数 K および N が与えられる．K は候補者の人数であり，1 ≤ K ≤ 2,000 を満たす．N は有権者の人数であり，1 ≤ N ≤ K × 255 を満たす．

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

各データセットに対し，答えを一行に出力せよ．

4 3
2 510
4 5
271 828
2000 133333
0 0

0
65025
8
53634343
781942874

最初のデータセットでは，4 人の候補者の得票数の積は常に 0 となるため，その総和も 0 となる．

二番目のデータセットでは，2 人の候補者が 255 票ずつ得たとき，またそのときに限り，得票数を連結したものを IPv2 アドレスとみなせる．したがって，255 × 255 = 65025 が答えとなる．

陸上競技ファンのあなたは，とあるマラソンの大会を現地で観戦することにした．この大会では，XY 平面上の原点と点 (a, b) を結ぶ線分上がマラソンコースとなる．また，大会中の交通規制のため，大会の観戦は，X 座標と Y 座標がともに整数である点のうち，マラソンコース上にない点のみで行うことができる．

あなたは，もちろん，できるだけマラソンコースに近い地点で大会を観戦したい．上述の条件を満たす点のうち，マラソンコースまでのユークリッド距離が最も近い点を求めよ．ただし，そのような点が複数ある場合には，その中で X 座標が最も小さい点を求めよ．さらにそのような点が複数ある場合には，その中で Y 座標が最も小さい点を求めよ．

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

a b

a, b はともに 1 以上 10⁹ 以下の整数であり，マラソンコースの一方の端点の座標を表す．

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

各データセットに対し，あなたがこのマラソン大会を観戦するのに最適な地点の X 座標と Y 座標を，空白区切りで一行に出力せよ．

2 3
2 9
7 2
9 8
4 9
6 6
5 7
9 1
5 3
65537 735134400
0 0

1 1
1 4
3 1
1 1
1 2
0 1
2 3
1 0
2 1
23788 266832127

h × w の等間隔の格子点があり，上から r 番目，左から c 番目の位置を (r, c) とする (1 ≤ r ≤ h, 1 ≤ c ≤ w)．各格子点上に1匹ずつ蛙がいる．各々の蛙は強さが数値化されており，位置 (r, c) にいる蛙の強さは f_{r, c} である．だが，彼らはみな，自分が世界で一番強いと思っている井の中の蛙である．彼らは自分より強い蛙がいない範囲を直感的に把握しており，その範囲内のみで活動することによりそのアイデンティティを保っている．

位置 (r₁, c₁) と位置 (r₂, c₂) との距離を |r₁ - r₂| + |c₁ - c₂| と定義する．このとき，位置 (r, c) にいる蛙は，距離 d 以内に自分より厳密に強い蛙がいないければ，この範囲で活動できる．すなわち，|r - i| + |c - j| ≤ d を満たすすべての 1 ≤ i ≤ h, 1 ≤ j ≤ w について，f_{i, j} ≤ f_{r, c} であれば，位置 (r, c) にいる蛙は距離 d の範囲で活動できる．

格子上の蛙たちがどれだけ井の中の蛙なのかの度合い，通称「井度」を把握するため，あなたにプログラムの作成依頼が飛び込んだ．各距離 d = 1, 2, ..., h + w - 2 について，距離 d の範囲で活動可能な蛙の数を求めるプログラムを作成し，あなたがプログラミング界の井の中の蛙ではないことを証明しよう．

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

h w f_1,1 f_1,2 ... f_1,w f_2,1 f_2,2 ... f_2,w ... f_h,1 f_h,2 ... f_h,w

入力の 1 行目は格子の大きさを表す 2 つの整数 h と w からなり， 1 ≤ h ≤ 1,000，1 ≤ w ≤ 1,000，h + w ≥ 3 を満たす．続く h 行は各行 w 個の整数からなり，各蛙の強さの情報である．r 行目の c 番目の整数は位置 (r, c) の蛙の強さ f_{r, c} を表す．各 f_{r, c} はいずれも 1 以上 10⁹ 以下である．

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

各データセットに対して，h + w - 2 個の整数を空白区切りで 1 行に出力せよ．ここで，行内の i 番目の整数は，距離 i 以内に自分より強い蛙が存在しないような蛙の数である．

4 5
9 1 1 1 3
5 2 1 3 1
6 4 1 1 2
4 4 3 2 8
7 5
24 18 10 34 43
37 26 42 49 27
10 41 3 19 29
31 4 10 32 42
44 25 41 14 28
36 21 25 30 40
1 43 8 40 44
3 3
1 1 1
1 1 1
1 1 1
1 9
1 2 3 4 5 4 3 2 1
0 0

7 4 2 2 2 2 1
9 5 3 3 3 1 1 1 1 1
9 9 9 9
1 1 1 1 1 1 1 1

映画好きの栄花さんは，夏休みに映画館に行くことにした．この映画館では，N 種類の映画が，それぞれ一日に一回上映されている．栄花さんの目標は，全種類の映画をなるべく早く見終えることである．

ここで，栄花さんのいる世界では，一日は T 時間からなる．ある日の開始から x 時間 (0 ≤ x ≤ T) 経過した時刻を，その日の x 時と呼ぶ．ある日の T 時は，その翌日の 0 時と同一の時刻である．

この映画館で上映される N 種類の映画のうち，i 番目の映画は，毎日 S_i 時からその D_i 時間後まで放映される．映画によっては，日をまたいで放映されることもありうる．栄花さんは，それぞれの映画を最初から最後まで継続して視聴しなければならず，一度見始めた映画を途中で見るのをやめたり，上映中の映画を途中から見始めたりすることはできない．また，複数の映画を一度に視聴することもできない．ただし，ある映画の上映終了と同時刻に別の映画が上映開始される場合，それらの映画を連続して視聴することはできる．なお，映画を視聴していない時間帯があっても構わない．

栄花さんは，夏休み初日の 0 時にこの映画館に到着した．ここから栄花さんが映画を視聴する順番を適切に選んだ場合，全 N 種類の映画を見終えるのは，最短で何時間後になるだろうか？なお，0 時に上映開始する映画がある場合，栄花さんは早速その映画を視聴する事が可能である．また，栄花さんは強靭な肉体と精神を持っているため，睡眠や食事などの時間について考慮する必要はない．

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

N T S₁ D₁ ... S_N D_N

1 行目には整数 N および T が与えられる．N はこの映画館で上映されている映画の種類数であり，1 ≤ N ≤ 20,000 を満たす．T は栄花さんのいる世界における一日の時間数であり，1 ≤ T ≤ 10⁹ を満たす．

続く N 行には，N 種類の映画の情報が与えられる．このうち i 番目の行には整数 S_i および D_i が与えられる．S_i は i 番目の映画の上映開始時刻であり，0 ≤ S_i < T を満たす．D_i は i 番目の映画の上映時間であり，1 ≤ D_i ≤ T を満たす．

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

各データセットに対し，栄花さんが N 種類の映画すべてを見終えるのが，夏休み初日の 0 時から起算して最短で何時間後になるか，一行に出力せよ．

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

24
21
3

あなたは，オリエンテーリングの競技に参加することになった．この競技では，XY 平面の原点から出発し，N 個のチェックポイントを順番に通過し，再び原点に戻ってくればクリアとなる．あなたの目的は，クリアのための移動距離を最小化することである．

ここで，この競技における各チェックポイントは，すべての辺が座標軸に平行な長方形である．すなわち，4 点 (L_i, B_i), (R_i, B_i), (R_i, T_i), (L_i, T_i) を頂点とする長方形の辺上および内部を，i 番目のチェックポイントと呼ぶ．形式的には，以下の二つの条件をともに満たしたとき，i 番目のチェックポイントを通過したとみなす．

• 条件 1: i ≥ 2 であるならば，i-1 番目のチェックポイントはすでに通過済みである．
• 条件 2: あなたが現在いる座標 (x, y) が，L_i ≤ x ≤ R_i および B_i ≤ y ≤ T_i を満たす．

条件 1 を満たさない状態であるチェックポイント内に立ち入ったり，すでに通過済みのチェックポイント内に再度立ち入ったりしてもよいが，その場合は何も起きない．

あなたは，この二次元平面上を自由に動くことができる．あなたが原点から出発し，N 個のチェックポイントを順番に通過し，再び原点に戻ってくるまでの移動距離の最小値を求めよ．

なお，この問題において，チェックポイントは以下の制約を満たす．

• どの二つのチェックポイントも，点を共有しない．
• いずれのチェックポイントも，原点を含まない．

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

N L₁ R₁ B₁ T₁ ... L_N R_N B_N T_N

1 行目には整数 N が与えられる．N はこのオリエンテーリングにおけるチェックポイントの数であり，1 ≤ N ≤ 9 を満たす．

続く N 行には，N 個のチェックポイントの情報が与えられる．このうち i 番目の行には整数 L_i, R_i, B_i, T_i が与えられ，それぞれこのチェックポイントの左端の X 座標，右端の X 座標，下端の Y 座標，上端の Y 座標を表す．-10,000 ≤ L_i < R_i ≤ 10,000 および -10,000 ≤ B_i < T_i ≤ 10,000 を満たすことが保証される．どの二つのチェックポイントも点を共有せず，また，いずれのチェックポイントも原点を含まないことが保証される．

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

各データセットに対し，あなたがこの競技をクリアするために必要な移動距離の最小値を，一行に出力せよ．出力は相対誤差または絶対誤差が 10^-6 以下であれば許容される．

2
1 2 -1 2
-2 -1 -2 2
2
1 2 1 2
-2 -1 -2 2
2
3 4 -2 2
1 2 -1 2
3
15 20 0 14
-5 15 15 20
-15 -5 0 14
0

4
4.576491223
6
50