問題文

高橋君は，文字列 S を持っています． 高橋君は yahoo という文字列が好きなので，S を編集することで yahoo の繰り返しで得られる文字列に変えようとしています． ここで，yahoo の繰り返しで得られる文字列とは，yahoo を 0 個以上つなげてできる文字列です．これらは，短いほうから順に (空文字列)，yahoo，yahooyahoo，… となります．

高橋君は 1 回の操作で次のうちいずれかを行うことができます．

• S の任意の 1 文字を選んで，それを任意の英小文字に書き換える．
• S の任意の 1 文字を選んで，その文字を S から取り除く．
• S の任意の位置に，任意の英小文字を挿入する．

高橋君が S を yahoo の繰り返しで得られる文字列にするために，必要な操作の回数の最小値を求めてください．

制約

• 1 \leq |S| \leq 10^5
• S は英小文字からなる

入力例 1

yfoo

出力例 1

2

例えば，次のようにすればよいです．

• 2 文字目の f を h に変える．S は yhoo になる．
• 1 文字目と 2 文字目の間に a を挿入する．S は yahoo になる．

入力例 2

z

出力例 2

1

1 文字目の z を取り除くと，S は空文字列になり，yahoo の繰り返しで得られる文字列になります．

入力例 3

yahooyahooyahooyahooyahoo

出力例 3

0

入力例 4

yahyahoo

出力例 4

2

問題文

ACoder では，チーム高橋とチーム青木の 2 チーム対抗でのプログラミングコンテストを開こうとしています． チーム高橋の参加者の候補は N 人いて，チーム高橋の i 番目の候補者の実力は A_i で表されます． また，チーム青木の参加者の候補は M 人いて，チーム青木の i 番目の候補者の実力は B_i で表されます．

コンテストを開く前に，チーム高橋，チーム青木のそれぞれから K 人ずつの参加者を選ぶことにしました． 参加者は，それぞれのチームの参加者の候補から選ばれます． ここで，K 人ずつの参加者を選んだときの，チーム間の実力差を次のように定義することにしました．

• チーム高橋の参加者の中で i 番目に実力の値が大きい人の実力を X_i，チーム青木の参加者の中で i 番目に実力の値が大きい人の実力を Y_i とする．
• このとき，チーム間の実力差は，max (|X_1 - Y_1|, |X_2 - Y_2|, ..., |X_K - Y_K| ) である．

各チームの参加者を決めたときの，チーム間の実力差の最小値を求めてください．

制約

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq K \leq min (N, M)
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• A_i, B_i は整数

入力例 1

3 4 2
2 11 16
4 7 9 10

出力例 1

2

チーム高橋からは 1, 2 番目の候補者を，チーム青木からは 1, 3 番目の候補者を，参加者として選ぶことにするとよいです． このとき，チーム高橋の参加者の実力は大きい方から順に 11, 2，チーム青木の参加者の実力は大きい方から順に 9, 4 となります．

入力例 2

6 5 3
15 7 14 3 14 11
20 18 15 18 17

出力例 2

3

問題文

高橋君は，数列 [A_1, A_2, ..., A_N] を持っています． 高橋君は，数列のある区間内の数すべてに同じ値を足すのが好きです．また，高橋君は M の倍数が好きなので，数列のある区間に現れる M の倍数の個数が気になります．

高橋君のために，次のような質問に答えてあげてください．ただし，質問は全部で Q 個与えられるものとします．

• i 番目の質問では，l_i, r_i, d_i が与えられる．まず，A_{l_i}, A_{l_i + 1}, ..., A_{r_i} それぞれの値に d_i を足す．その後，A_{l_i}, A_{l_i + 1}, ..., A_{r_i} の中にある M の倍数の個数を答える．

制約

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq M \leq 10^5
• 0 \leq A_i \leq 10^9
• 1 \leq l_i \leq r_i \leq N
• 0 \leq d_i \leq 10^9
• A_i, d_i は整数

入力例 1

5 4 4
1 2 4 3 4
1 2 2
2 5 0
4 5 5
1 5 3

出力例 1

1
3
1
1

各質問の後での数列の値は以下のようになります．

• 1 番目の質問の後，数列は [3, 4, 4, 3, 4] になる．
• 2 番目の質問の後，数列は [3, 4, 4, 3, 4] になる．
• 3 番目の質問の後，数列は [3, 4, 4, 8, 9] になる．
• 4 番目の質問の後，数列は [6, 7, 7, 11, 12] になる．

入力例 2

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

出力例 2

3
1
0
1
3
1
2
4
0

問題文

高橋君は，長さ N の数列 A を持っています． 高橋君は，A の最長増加部分列を探して遊ぶことにしました． A の最長増加部分列とは，A の部分列であり，かつ狭義単調増加なものの中で，最も長いものを意味します． 高橋君は，A の最長増加部分列をただ探すだけではつまらないと思い，A の最長増加部分列となる部分列の中で，辞書順で K 番目のものを求めることにしました． なお，取り出す位置が異なっても，数列として同じ部分列は区別しないことにしました．

しかし，高橋くんは途中で疲れて寝てしまいました． 高橋君の代わりに，A の最長増加部分列のうち辞書順で K 番目のものを求めて出力するプログラムを書いてください． なお，そのようなものが存在しない場合は，None と出力してください．

制約

• 入力は全て整数である
• 1 \leq N \leq 300,000
• 1 \leq K \leq 10^{18}
• 1 \leq A_i \leq 10^9

入力例 1

6 2
3 6 5 1 2 7

出力例 1

3 5 7

A の最長部分増加列となる部分列は，以下の 3 通りあります．

• [1,2,7]
• [3,5,7]
• [3,6,7]

辞書順で 2 番目のものは，[3,5,7] です．

入力例 2

4 2
1 1 2 2

出力例 2

None

A の最長増加部分列は，[1,2] の 1 通りしかないので，None を出力します．

入力例 3

20 1000
2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19

出力例 3

2 4 6 8 10 11 13 16 18 20

問題文

高橋王国には N 個の都市 1, 2, ..., N があります． どの 2 つの異なる都市の間にも，それらの都市間を直接結ぶ瞬間移動装置が設けられています． 都市 x と y を結ぶ瞬間移動装置を使うと，都市 x から都市 y へも，都市 y から都市 x へも移動することができます．

しかし現在，都市 a_i と b_i (i = 1, 2, ..., M) を直接結ぶ瞬間移動装置は故障しており，使うことができません．

次のような形式の Q 個の質問に答えてください．

• i 番目の質問では，c_i と d_i が与えられる．このとき，都市 c_i から都市 d_i まで瞬間移動装置を乗り継いで移動するためには，最小で何回瞬間移動装置を利用すればよいか？

制約

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq a_i < b_i \leq N
• a_i = a_j かつ b_i = b_j を満たす異なる i, j の組は存在しない
• 1 \leq c_i < d_i \leq N

入力例 1

6 7 4
1 2
2 4
2 5
2 6
3 5
3 6
5 6
1 2
2 3
5 6
2 5

出力例 1

2
1
2
3

使える瞬間移動装置は，下図のようになります．図の太線はその都市間を結ぶ瞬間移動装置が使えること，点線は故障していることを表します．

入力例 2

4 4 2
1 3
1 4
2 3
2 4
1 2
1 3

出力例 2

1
-1