問題文

あなたは、育成シミュレーションゲーム「すぬけそだて」を入手しました。

「すぬけそだて」では、あなたはひょんなことから路地裏で世界一賢いねこ「すぬけ君」との運命の出会いを果たします。 拾いたてのすぬけ君はまだ体も貧弱で、ただにゃーにゃーと鳴いているばかりです。しかし成長するにつれ、すぬけ君のできることはどんどん増えていきます。

お手、ジャンプ、ネズミ取り、洗濯、引越し作業、競技プログラミング、ゲーム制作、確定申告、起業……すぬけ君の可能性は無限大です！　 賢くて、少し変わったねこと一緒の、夢のような生活があなたを待っています！

閑話休題。ところで、ゲームを始めるにあたって、あなたは自分の名前を決めなければいけません。名前として登録できるのは、A 文字以上 B 文字以下の英小文字からなる文字列です。

A,B とあなたの登録したい名前を表す文字列 S が与えられるので、その名前を登録できるかどうか判定してください。

制約

• 1 \leq A \leq B \leq 10
• A,B は整数である
• S の長さは 1 以上 10 以下である
• S は英小文字からなる

入力例 1

4 8
colopl

出力例 1

YES

colopl は 6 文字なので、登録できます。

入力例 2

2 7
kitayuta

出力例 2

NO

kitayuta は 8 文字なので、登録できません。

入力例 3

7 8
kyuri

出力例 3

NO

問題文

あなたは、「すぬけそだて」のチュートリアルをプレイしています。チュートリアルでは、あなたがすぬけ君を拾うに至った経緯が語られます。

始業時刻に遅刻し、昼食をひっくり返し、書いたプログラムはバグだらけ、挙句の果てに先輩を「パパ」と呼んでしまう……失意のどん底に陥っていたあなたは、人気のない暗い路地で、 にゃーにゃーと鳴くか細い声を耳にします。

最初は無視を決め込んでいたあなたでしたが、翌日も、その翌日も、あなたは同じ場所で同じ声を聴くのでした。

気になったあなたは、声のする方向に近づいてみました。草むらの中に広がっていた光景……それには説明の必要はないでしょう。

こうして、あなたとすぬけ君との共同生活が幕を開けたのです！

と、このような心温まるお話を見るのも、もう 10 回目です。「すぬけそだて」では、最初にランダムなゲームアイテム「マタタビ」がもらえるのですが、 あなたは好きな「マタタビ」がもらえるまでチュートリアルをやり直すことにした、というのがその理由です。

お話の内容を完全に覚えてしまったあなたは、素早くチュートリアルを終わらせることに集中することにしました。

チュートリアルは、N 個のフェイズに分かれています。各フェイズは「ローディング」か「ストーリー」のいずれかであり、文字列 S の i 文字目が 0 のとき i 個目の フェイズが「ローディング」であることを、1 のとき i 個目のフェイズが「ストーリー」であることを表します。また、i 個目のフェイズにかかる時間は、最初 T_i 秒です。

「ストーリー」のフェイズでは、開始直後にスキップボタンを押すことでそのストーリーをちょうど X 秒で終わらせることができます。スキップボタンを押さない場合、 このストーリーにかかる時間は T_i 秒のままです。「ローディング」のフェイズでは、進行を速めることはできません。

適切にボタンを押したとき、最小で何秒でチュートリアルを終わらせることができるでしょうか。

制約

• 1 \leq N \leq 1000
• 1 \leq X \leq 10^6
• S の長さは N である
• 1 \leq T_i \leq 10^6(1\leq i\leq N)
• N,X,T_i(1\leq i\leq N) は整数である

入力例 1

3 5
011
8
10
3

出力例 1

16

2 番目のフェイズでスキップを選択し、3 番目のフェイズでスキップを選択しない場合、8+5+3=16 秒でチュートリアルを終わらせることができます。

入力例 2

5 314
10101
159
265
358
979
323

出力例 2

2031

問題文

目当ての「マタタビ」を手に入れたあなたは、「すぬけそだて」を本格的に遊び始めました。

都市の道端とはいえやはり自然は弱肉強食の世界で、拾われたばかりのすぬけ君は弱りきっていました。 あなたは、ゲーム内アイテムを食べさせてあげることで、すぬけ君の体力を回復させようとしています。

さて、すぬけ君は好物が整数の書かれたカードであるという変わったねこです。カードをすぬけ君に与えると、あなたはむしゃむしゃと幸せそうにカードを食べるすぬけ君の愛らしい姿を眺めることができます。 しかし、カードを与えているうちに、あなたはカードを食べてもすぬけ君が喜ばないことがあることに気付きました。また、以下の性質を発見しました。

• すぬけ君は、その日にこれまでに食べたどのカードに書かれた整数とも互いに素である整数の書かれたカードを食べたとき、喜ぶ。そうでないとき、悲しむ。

今日のカードショップには A 以上 B 以下の整数の書かれたカードが 1 枚ずつ売られています。 あなたは、このうちの 0 枚以上の任意の枚数を購入し、すべてのカードをすぬけ君に与えることにしました。このとき、すぬけ君を 1 度でも悲しませてはいけません。

カードの買い方は何通りあるでしょうか。

制約

• 1 \leq A \leq B \leq 10^{18}
• B-A\leq 35

入力例 1

2 4

出力例 1

6

2 の書かれたカードと 4 の書かれたカードを同時に含まないものすべてが条件を満たします。これは 6 通りあります。

入力例 2

5 9

出力例 2

20

入力例 3

123456789987654321 123456789987654356

出力例 3

105728

問題文

あなたは、「すぬけそだて」を楽しんでいます。愛しのすぬけ君をできるだけ賢いねこにしたいあなたは、すぬけ君の知力トレーニングをすることにしました。

「すぬけそだて」では、あなたは「スタミナ」を消費してすぬけ君の知力をトレーニングすることができます。スタミナを 1 消費するごとに、すぬけ君の知力は 1 だけ上がります。

スタミナは、1 単位時間に 1 だけ、最大で X まで回復します。スタミナが上限 X に達している場合、時間経過でスタミナが回復することはありません。 また、スタミナを 0 未満にすることはできません。初期状態、すなわち時刻 O において、スタミナは満タンに、すなわち X だけ溜まっています。

もちろん、スタミナが溜まったらすぐに消費するのが最も効率的なのですが、残念なことにあなたには現実世界での用事があり、 四六時中「すぬけそだて」を遊んでいるというわけにはいきません(現実の生活というのは、往々にして融通の利かないものです)。

それでも、あなたは多忙な生活の合間を縫って、「すぬけそだて」を起動できる時間の候補を N 個ひねり出しました。i 個目の候補は時刻 T_i です。 あなたは多忙なため、一度ゲームを起動したら、一瞬のうちにスタミナの消費を終えてゲームを終了しなければなりません。 すなわち、時刻 T_i にスタミナが s だけ残っていた場合、あなたはスタミナを s 以下の任意の非負整数量消費し、消費した分だけすぬけ君の知力を上げる操作をすることができますが、 それ以外の操作はできません。

現実の予定というのはなかなか決まらないもので、あなたは自分がこれから先しばらくどれほど忙しいのかを読み切れずにいます。そこで、各 K=1,2,...,N について、 N 個のゲームの起動時刻の候補のうち K 個以下を選んでゲームを起動する場合に、最終的にすぬけ君の知力が最大でいくつになるのかを計算することにしました。 これらの N 個の値をすべて求めてください。

制約

• 1 \leq N \leq 5000
• 1 \leq X \leq 10^9
• 1 \leq T_i \leq 10^9(1\leq i\leq N)
• T_i < T_{i+1}(1\leq i\leq N-1)
• 入力はすべて整数である

入力例 1

3 3
2
4
6

出力例 1

3
6
7

K=1 のとき、時刻 4 にスタミナを 3 消費すればよいです。

K=2 のとき、時刻 2 にスタミナを 3 消費し、時刻 6 にスタミナを 3 消費すればよいです。

K=3 のとき、時刻 2 にスタミナを 3 消費し、時刻 4 にスタミナを 2 消費し、時刻 6 にスタミナを 2 消費すればよいです。

入力例 2

5 4
4
5
7
8
11

出力例 2

4
8
11
11
11

入力例 3

7 5
2
4
10
12
13
17
20

出力例 3

5
10
15
18
20
22
22

問題文

あなたは「すぬけそだて」を楽しんでいます。すぬけ君は、驚くほど賢くなりました！

レベルを上げ、めきめきと知力をつけたすぬけ君は、今や様々なビジネスに手を出しています。すぬけ君の一生懸命に働く姿を見たいあなたは、すぬけ君のオフィスを作ってあげることにしました。

ゲーム内通貨を溜めに溜めたあなたは、ついにすぬけ君の居住スペースを設計するためのアイテム「むげんのわっか」を手に入れました。 「むげんのわっか」は任意の長さの平面上の閉曲線として使うことができ、以下の条件を満たすように配置することができます。

• 「むげんのわっか」の点のうち 5000 点以下を選ぶ。選んだ点を柱の点と呼ぶ。柱の点では「むげんのわっか」は直角に曲がらなければならない。また、その他の点で曲がってはならない。
• 2 つの柱の点の間の部分は、x 軸または y 軸に平行でなければならない。
• すべての柱の点は、x 座標と y 座標がともに絶対値が 10^9 以下の整数である平面上の点に配置されなければならない。
• すべての柱の点について、その点の配置される平面上の点を、「むげんのわっか」の他の点が通ってはならない。「むげんのわっか」が、柱の点以外で自己交叉することは許される。
• 「むげんのわっか」によって、平面全体が(外平面も含めて)ちょうど K 個に分割されなければならない。

下図の最初の配置は条件を満たしますが、2 番目や 3 番目の配置は柱の点の配置された点を「むげんのわっか」が二度以上通っているので、条件を満たしません。

K が与えられるので、条件を満たす配置をひとつ求めてください。

制約

• 2 \leq K \leq 10^6

入力例 1

3

出力例 1

6
1 5
1 3
5 3
5 1
3 1
3 5

以下の図のように、平面が 3 つの部分に分かれています。

入力例 2

6

出力例 2

12
2 0
0 0
0 2
6 2
6 0
4 0
4 6
6 6
6 4
0 4
0 6
2 6