問題文

高橋君は新しい会社を作ろうとしています。 今回は検索サイトの会社を作ることにしたため、yahoo の 5 文字を並び替えた文字列を社名にすることにしました。

友人の青木君は、新しい会社の名前として文字列 S を提案しました。この文字列が高橋君の希望に合うかどうかを判定してください。

制約

• |S|=5
• S は英小文字のみからなる。

入力例 1

oohay

出力例 1

YES

yahoo の文字をそれぞれ 5,4,3,2,1 文字目の順に並び替えれば oohay となります。

入力例 2

abcde

出力例 2

NO

入力例 3

yahoo

出力例 3

YES

yahoo のままでも条件を満たします。

入力例 4

yohaa

出力例 4

NO

問題文

高橋君はオークションサイトでの買い物を楽しんでいます。 今、このオークションサイトには N 個の商品が出品されており、i 個目の商品の値段は A_i 円です。 このオークションサイトでは、一日に一個までしか商品を買うことができず、 一日たつごとにどの商品も値段が 1 円ずつ増えます。 もちろん、同じ商品は一度までしか買うことはできません。

高橋君は K 個の商品を買いたいです。 高橋君が K 個の商品を買うために必要な金額の最小値を求めてください。

制約

• 1 ≦ N ≦ 10^5
• 1 ≦ K ≦ N
• 1 ≦ A_i ≦ 10^9

入力例 1

3 2
1 3 5

出力例 1

5

例えば、以下のように買い物をすれば高橋君は 5 円で 2 個の商品を買うことができます。

• 1 日目に 3 円の商品を買う。このとき、残りの商品の値段は 1 円ずつ上がり、2 円と 6 円の商品が残る。
• 2 日目に 2 円の商品を買う。このとき、使った金額の合計は 5 円となる。

入力例 2

5 3
6 3 2 4 7

出力例 2

12

問題文

高橋君は Yafoo という検索エンジンをよく利用しています。

Yafoo には N 個のサイトが登録されており、i 個目のサイトの登録名は S_i です。 また、文字列 T を検索ワードとして検索を行うと、登録されている N 個のサイトのうち、 登録名の長さが |T| 以上でかつ登録名の先頭 |T| 文字が T に一致するようなサイト全てが検索結果として得られます。

今、高橋君は検索結果として A_1,\ A_2,\ ...,\ A_K 番目のサイトが得られるようにしたいです。 そのような検索結果がちょうど得られるような検索ワードが存在するかどうかを判定し、存在する場合はその中で長さが最小のものを求めてください。

制約

• 1 ≦ N ≦ 10^5
• 1 ≦ K ≦ N
• 1 ≦ A_i ≦ N
• 各 A_i は相異なる。
• 1 ≦ |S_i| ≦ 10^5
• |S_i| の合計は 10^5 以下である。
• S_i はそれぞれ英小文字からなる。

入力例 1

3 2
1 2
abc
ab
a

出力例 1

ab

ab という文字列が条件を満たす検索ワードです。

入力例 2

3 2
1 2
abc
ab
abc

出力例 2

-1

入力例 3

3 3
1 2 3
abc
ab
abc

出力例 3

検索ワードは空文字列でも良いことに注意してください。

問題文

高橋君は工場の経営者です。 今は休暇中であり工場には商品が 1 つもありませんが、 休暇明け 1 日目からは毎日 K 個ずつ商品を生産する予定です。

また、この工場はとても人気で注文が入ることがあります。 しかし、この工場に入る注文は少し変わっており、以下のような形式で行われます。

• 注文 (D,A) : 休暇明けから D 日目までの商品の生産が終わった直後に商品を A 個まで買い取る。実際に売る個数は 0～A 個の範囲で高橋君が選ぶことが出来る。ただし、在庫の個数を超えて売ることは出来ない。

この工場のプログラミング担当であるあなたは、高橋君から注文追加や経理に関する質問の情報を Q 回渡されます。 i 番目の情報は以下の形式で入力されます。

• 注文追加「1\ D_i\ A_i」: (D_i,A_i) という形式の注文が工場に追加される。
• 経理質問「2\ D_i」: 質問の時点までに入った注文だけを考えたとき、休暇明け D_i 日目までの商品の生産と注文の処理を終えた時点で、最大で何個の商品を売ることができるかを求める。

全ての経理質問に正確に答えて、高橋君の経営を助けてあげてください。

制約

• 1 ≦ Q ≦ 10^5
• 1 ≦ K ≦ 10^9
• 1 ≦ D_i≦ 10^9
• 1 ≦ A_i≦ 10^9

部分点

• 600 点分のテストケースでは、経理質問における D_i の値が常に 10^9 である。

入力例 1

5 2
1 3 5
2 1
1 1 3
2 1
2 3

出力例 1

0
2
6

例えば、最後の経理質問のときの最適な商品の売り方は以下のようになります。

• 休暇明け 1 日目に商品を 2 個生産して、その後商品を 1 個売る。このとき、商品は 1 個残る。
• 休暇明け 2 日目に商品を 2 個生産する。このとき、商品は 3 個残る。
• 休暇明け 3 日目に商品を 2 個生産して、その後商品を 5 個売る。

入力例 2

4 2
1 5 5
2 1000000000
1 2 7
2 1000000000

出力例 2

5
9

この入力は部分点の制約を満たします。

入力例 3

10 4
2 6
1 5 7
2 6
2 4
2 1
2 7
1 5 7
2 7
2 2
1 4 6

出力例 3

0
7
0
0
7
14
0

問題文

高橋君は遊園地に遊びに来ました。遊園地には N 個のアトラクションが一列に並んでおり、順番に 1,\ 2,\ ...,\ N と番号がついています。

また、この遊園地で遊ぶためには体力が必要であり、隣り合うアトラクション間の移動には体力を 1 消費します。 さらに、i 個目のアトラクションで遊ぶためには体力が L_i 以上残っている必要があり、遊んだ後には体力がちょうど R_i になります。 ただし、いくつかのアトラクションはその面白さゆえか、遊んだ後に体力がもとより増えることもあります。

高橋君はできるだけ多くの種類のアトラクションで遊びたいです。 最初に遊ぶアトラクションとその後のアトラクションの順番をうまく選んだとき、高橋君が最大何種類のアトラクションで遊ぶことができるかを求めてください。 ただし、高橋君ははじめはとても気分がよく、体力が無限にあるとしてよいです。

制約

• 1 ≦ N ≦ 50,000
• 1 ≦ L_i ≦ 10^9
• 1 ≦ R_i ≦ 10^9

入力例 1

3
5 1 3
1 2 4

出力例 1

2

最初に 3 番目のアトラクションで遊び、その後 2 番目のアトラクションで遊べば、高橋君は 2 種類のアトラクションで遊ぶことができます。

入力例 2

5
3 1 2 4 5
2 5 4 1 3

出力例 2

3