A - Permute to Maximize

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

1 以上 9 以下の数字 A,B,C が与えられます。

A,B,C を好きな順番で並べて繋げることで作れる 3 桁の整数のうち、値が最大のものを求めてください。

制約

  • A,B,C は 1 以上 9 以下の数字

入力

入力は以下の形式で標準入力から与えられる。

A B C

出力

答えを出力せよ。

入力例 1

3 2 4

出力例 1

432

A,B,C を好きな順番で並べて繋げることで作れる 3 桁の整数は 324, 342, 234, 243, 432, 423 の 6 通りであり、 このうち値が最大のものは 432 です。

入力例 2

7 7 7

出力例 2

777

777 のみを作ることができます。

入力例 3

9 1 9

出力例 3

991

Score : 100 points

Problem Statement

You are given three digits A,B,C between 1 and 9, inclusive.

Find the maximum value among all 3-digit integers that can be formed by arranging A,B,C in any order and concatenating them.

Constraints

  • A,B,C are digits between 1 and 9, inclusive.

Input

The input is given from Standard Input in the following format:

A B C

Output

Output the answer.

Sample Input 1

3 2 4

Sample Output 1

432

There are six 3-digit integers that can be formed by arranging A,B,C in any order and concatenating them: 324, 342, 234, 243, 432, 423; the maximum value among them is 432.

Sample Input 2

7 7 7

Sample Output 2

777

Only 777 can be formed.

Sample Input 3

9 1 9

Sample Output 3

991
B - Last Two Digits

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

100 以上の整数 N が与えられます。N の下 2 桁を出力してください。

ただし、N の下 2 桁とは十の位と一の位をこの順に並べたものを言います。

制約

  • 100 \le N \le 999
  • N は整数である。

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを出力せよ。

入力例 1

254

出力例 1

54

254 の下 2 桁は 54 であるため、54 を出力します。

入力例 2

101

出力例 2

01

101 の下 2 桁は 01 であるため、01 を出力します。

Score : 100 points

Problem Statement

You are given an integer N at least 100. Print the last two digits of N.

Strictly speaking, print the tens and ones digits of N in this order.

Constraints

  • 100 \le N \le 999
  • N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

254

Sample Output 1

54

The last two digits of 254 are 54, which should be printed.

Sample Input 2

101

Sample Output 2

01

The last two digits of 101 are 01, which should be printed.
C - Perfect String

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

英大文字と英小文字からなる文字列のうち、以下の条件を全て満たすものを素晴らしい文字列ということとします。

  • 英大文字が文字列の中に現れる。
  • 英小文字が文字列の中に現れる。
  • 全ての文字が相異なる。

例えば、AtCoder や Aa は素晴らしい文字列ですが、atcoder や Perfect は素晴らしい文字列ではありません。

文字列 S が与えられるので、S が素晴らしい文字列か判定してください。

制約

  • 1 \le |S| \le 100
  • S は英大文字と英小文字からなる文字列である。

入力

入力は以下の形式で標準入力から与えられる。

S

出力

S が素晴らしい文字列ならば Yes を、そうでないならば No を出力せよ。

入力例 1

AtCoder

出力例 1

Yes

AtCoder は、英大文字が含まれ、英小文字も含まれ、かつ全ての文字が相異なるため素晴らしい文字列です。

入力例 2

Aa

出力例 2

Yes

A と a は違う文字であることに注意してください。この文字列は素晴らしい文字列です。

入力例 3

atcoder

出力例 3

No

英大文字が含まれていないため、素晴らしい文字列ではありません。

入力例 4

Perfect

出力例 4

No

2 文字目と 5 文字目が等しいため、素晴らしい文字列ではありません。

Score : 200 points

Problem Statement

Let us call a string consisting of uppercase and lowercase English alphabets a wonderful string if all of the following conditions are satisfied:

  • The string contains an uppercase English alphabet.
  • The string contains a lowercase English alphabet.
  • All characters in the string are pairwise distinct.

For example, AtCoder and Aa are wonderful strings, while atcoder and Perfect are not.

Given a string S, determine if S is a wonderful string.

Constraints

  • 1 \le |S| \le 100
  • S is a string consisting of uppercase and lowercase English alphabets.

Input

Input is given from Standard Input in the following format:

S

Output

If S is a wonderful string, print Yes; otherwise, print No.

Sample Input 1

AtCoder

Sample Output 1

Yes

AtCoder is a wonderful string because it contains an uppercase English alphabet, a lowercase English alphabet, and all characters in the string are pairwise distinct.

Sample Input 2

Aa

Sample Output 2

Yes

Note that A and a are different characters. This string is a wonderful string.

Sample Input 3

atcoder

Sample Output 3

No

It is not a wonderful string because it does not contain an uppercase English alphabet.

Sample Input 4

Perfect

Sample Output 4

No

It is not a wonderful string because the 2-nd and the 5-th characters are the same.
D - Geometric Sequence

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

A が等比数列であるか判定してください。

制約

  • 2\leq N\leq 100
  • 1\leq A_i\leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N

出力

A が 等比数列ならば Yes を、そうでないならば No を出力せよ。

入力例 1

5
3 6 12 24 48

出力例 1

Yes

A=(3,6,12,24,48) です。
A は初項 3, 公比 2, 項数 5 の等比数列となっています。
よって、Yes を出力します。

入力例 2

3
1 2 3

出力例 2

No

A=(1,2,3) です。
A_1:A_2=1:2\neq 2:3=A_2:A_3 より、A は等比数列ではありません。
よって、No を出力します。

入力例 3

2
10 8

出力例 3

Yes

A は初項 10, 公比 0.8, 項数 2 の等比数列となっています。
よって、Yes を出力します。

Score : 200 points

Problem Statement

You are given a length-N sequence A=(A_1,A_2,\ldots,A_N) of positive integers.

Determine whether A is a geometric progression.

Constraints

  • 2 \leq N \leq 100
  • 1 \leq A_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

If A is a geometric progression, print Yes; otherwise, print No.

Sample Input 1

5
3 6 12 24 48

Sample Output 1

Yes

A=(3,6,12,24,48).
A is a geometric progression with first term 3, common ratio 2, and five terms.
Therefore, print Yes.

Sample Input 2

3
1 2 3

Sample Output 2

No

A=(1,2,3).
Since A_1 : A_2 = 1 : 2 \neq 2 : 3 = A_2 : A_3, A is not a geometric progression.
Therefore, print No.

Sample Input 3

2
10 8

Sample Output 3

Yes

A is a geometric progression with first term 10, common ratio 0.8, and two terms.
Therefore, print Yes.
E - Enumerate Sequences

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

以下の条件を満たす長さ N の整数列を辞書順で小さい方から順に全て出力して下さい。

  • i 番目の要素は 1 以上 R_i 以下
  • 総和が K の倍数
数列の辞書順とは？ 数列 A = (A_1, \ldots, A_{|A|}) が B = (B_1, \ldots, B_{|B|}) より辞書順で真に小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。
  1. |A|<|B| かつ (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}) である。
  2. ある整数 1\leq i\leq \min\{|A|,|B|\} が存在して、下記の 2 つがともに成り立つ。
    • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
    • A_i < B_i

制約

  • 入力は全て整数
  • 1 \le N \le 8
  • 2 \le K \le 10
  • 1 \le R_i \le 5

入力

入力は以下の形式で標準入力から与えられる。

N K
R_1 R_2 \dots R_N

出力

出力すべき数列が X 個あり、そのうち i 個目が A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}) であったとき、答えを以下の形式で出力せよ。

A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}

入力例 1

3 2
2 1 3

出力例 1

1 1 2
2 1 1
2 1 3

出力すべき数列は 3 個で、辞書順で (1,1,2),(2,1,1),(2,1,3) です。

入力例 2

1 2
1

出力例 2



出力すべき数列が無い場合もあります。

この場合、出力は空で構いません。













入力例 3
5 5
2 3 2 3 2












出力例 3
1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1







Score : 300 points







Problem Statement
Print all integer sequences of length N that satisfy the following conditions, in ascending lexicographical order.


    

  • The i-th element is between 1 and R_i, inclusive.
    • 

  • The sum of all elements is a multiple of K.
    • 



 What is lexicographical order for sequences?
A sequence A = (A_1, \ldots, A_{|A|}) is lexicographically smaller than B = (B_1, \ldots, B_{|B|}) if either 1. or 2. below holds:

    

  1. |A|<|B| and (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
    2. 

  2. There exists an integer 1\leq i\leq \min\{|A|,|B|\} such that both of the following are true:

      

    • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
      • 

    • A_i < B_i
      • 

    















Constraints
    

  • All input values are integers.
    • 

  • 1 \le N \le 8
    • 

  • 2 \le K \le 10
    • 

  • 1 \le R_i \le 5
    • 
















Input
The input is given from Standard Input in the following format:


N K
R_1 R_2 \dots R_N












Output
Print the answer in the following format, where X is the number of sequences to print, the i-th of which is A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}):


A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}
















Sample Input 1
3 2
2 1 3












Sample Output 1
1 1 2
2 1 1
2 1 3



There are three sequences to be printed, which are (1,1,2),(2,1,1),(2,1,3) in lexicographical order.













Sample Input 2
1 2
1












Sample Output 2


There may be no sequences to print.

In this case, the output can be empty.













Sample Input 3
5 5
2 3 2 3 2












Sample Output 3
1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1







			


			
		

	
		

		

			F - 1122 Substring 2
			

			
実行時間制限: 2 sec / メモリ制限: 1024 MiB


			

				


配点 : 300 点







問題文
数字からなる文字列 S が与えられます。


以下の条件を全て満たす文字列 T を 1122文字列 と呼びます。（定義は F 問題と同じです。）


    

  • T は数字からなる空でない文字列
    • 

  • |T| は偶数。ここで、 |T| は文字列 T の長さを表す
    • 

  • T の 1 文字目から \frac{|T|}2 文字目までは全て同じ数字である
    • 

  • T の \frac{|T|}2+1 文字目から |T| 文字目までは全て同じ数字である
    • 

  • T の 1 文字目の数字に 1 を足すと |T| 文字目の数字になる
    • 



例えば 1122 や 01 、 444555 などは 1122文字列 ですが、 1222 や 90 は 1122文字列 ではありません。


S の 部分文字列 であって 1122文字列 であるものの個数を求めてください。


ただし、ある二つの部分文字列が文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えるものとします。











制約
    

  • S は長さ 1 以上 10^6 以下の数字からなる文字列
    • 
















入力
入力は以下の形式で標準入力から与えられる。


S













出力
S の空でない部分文字列であって 1122文字列 であるものの個数を出力せよ。















入力例 1
1122













出力例 1
2




以下の 2 つの部分文字列が条件を満たします。


    

  • S の 2 文字目から 3 文字目を取り出した 12
    • 

  • S の 1 文字目から 4 文字目を取り出した 1122
    • 



したがって、 2 を出力してください。













入力例 2
7788788













出力例 2
3




文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えることに注意してください。













入力例 3
2025













出力例 3
0




1122文字列 となる部分文字列が存在しない場合もあります。













入力例 4
1112222334445556555













出力例 4
11







Score : 300 points







Problem Statement
You are given a string S consisting of digits.


A string T is called a 1122-string if it satisfies all of the following conditions. (The definition is the same as in Problem F.)


    

  • T is a non-empty string consisting of digits.
    • 

  • |T| is even, where |T| denotes the length of string T.
    • 

  • All characters from the 1-st through the \frac{|T|}2-th character of T are the same digit.
    • 

  • All characters from the (\frac{|T|}2+1)-th through the |T|-th character of T are the same digit.
    • 

  • Adding 1 to the digit of the 1-st character of T gives the digit of the |T|-th character.
    • 



For example, 1122, 01, and 444555 are 1122-strings, but 1222 and 90 are not 1122-strings.


Find the number of substrings of S that are 1122-strings.


Two substrings are counted separately if they are extracted from different positions, even if they are identical as strings.











Constraints
    

  • S is a string consisting of digits with length between 1 and 10^6, inclusive.
    • 
















Input
The input is given from Standard Input in the following format:


S













Output
Output the number of non-empty substrings of S that are 1122-strings.















Sample Input 1
1122













Sample Output 1
2




The following two substrings satisfy the condition.


    

  • 12 extracted from the 2-nd through 3-rd characters of S
    • 

  • 1122 extracted from the 1-st through 4-th characters of S
    • 



Thus, output 2.













Sample Input 2
7788788













Sample Output 2
3




Note that two substrings are counted separately if they are extracted from different positions, even if they are identical as strings.













Sample Input 3
2025













Sample Output 3
0




There may be no substring that is a 1122-string.













Sample Input 4
1112222334445556555













Sample Output 4
11







			


			
		

	
		

		

			G - (xx)
			

			
実行時間制限: 2 sec / メモリ制限: 1024 MiB


			

				


配点 : 425 点







問題文
(, x, ) からなる文字列 A が与えられます。

あなたは A に対して次の 2 種類の操作を自由な順番で自由な回数行うことが出来ます。


    

  • A の部分文字列 (xx) を 1 カ所選び、xx に置換する。
    • 

  • A の部分文字列 xx を 1 カ所選び、(xx) に置換する。
    • 



(, x, ) からなる文字列 B が与えられます。A を B と一致させることが出来るか判定してください。


T 個のテストケースが与えられるので、それぞれに対して答えを求めてください。



部分文字列とは

S の 部分文字列 とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。

例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。 














制約
    

  • 1 \leq T \leq 3 \times 10^5
    • 

  • A, B は (, x, ) からなる長さ 1 以上 2\times 10^6 以下の文字列
    • 

  • 全てのテストケースに対する |A| + |B| の総和は 2 \times 10^6 以下 (ここで |A| は A の長さを意味する)
    • 
















入力
入力は以下の形式で標準入力から与えられる。


T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T



各テストケースは以下の形式で与えられる。


A
B












出力
T 行出力せよ。i 行目には i 番目のテストケースの答えを出力せよ。

各テストケースでは、A を B と一致させることが出来る場合は Yes を、そうでない場合は No を出力せよ。















入力例 1
6
(xx)x
x(xx)
(x)x
(xx)
)x()x(
)x()x(
x
(x)
(((((xx)))))x
x((((((((((xx))))))))))
((xx)xx)xx
(x((xx))x)(xx)












出力例 1
Yes
No
Yes
No
Yes
Yes



例えば 1 番目のテストケースでは、次の手順によって A を B と一致させることが出来ます。


    

  • A の 1 文字目から 4 文字目の (xx) を xx に置換する。操作後の A は xxx となる。
    • 

  • A の 2 文字目から 3 文字目の xx を (xx) に置換する。操作後の A は x(xx) となる。
    • 







Score : 425 points







Problem Statement
You are given a string A consisting of (, x, ).

You can perform the following two types of operations on A any number of times in any order.


    

  • Choose one occurrence of the substring (xx) in A and replace it with xx.
    • 

  • Choose one occurrence of the substring xx in A and replace it with (xx).
    • 



You are given a string B consisting of (, x, ). Determine whether you can make A equal to B.


You are given T test cases; solve each of them.



What is a substring

A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.

For example, ab is a substring of abc, but ac is not a substring of abc.














Constraints
    

  • 1 \leq T \leq 3 \times 10^5
    • 

  • A and B are strings of length between 1 and 2\times 10^6, inclusive, consisting of (, x, ).
    • 

  • The sum of |A| + |B| over all test cases is at most 2 \times 10^6 (where |A| denotes the length of A).
    • 
















Input
The input is given from Standard Input in the following format:


T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T



Each test case is given in the following format:


A
B












Output
Output T lines. The i-th line should contain the answer to the i-th test case.

For each test case, output Yes if you can make A equal to B, and No otherwise.















Sample Input 1
6
(xx)x
x(xx)
(x)x
(xx)
)x()x(
)x()x(
x
(x)
(((((xx)))))x
x((((((((((xx))))))))))
((xx)xx)xx
(x((xx))x)(xx)












Sample Output 1
Yes
No
Yes
No
Yes
Yes



For example, in the first test case, you can make A equal to B by the following procedure:


    

  • Replace the (xx) from the 1st through 4th characters of A with xx. After this operation, A is xxx.
    • 

  • Replace the xx from the 2nd through 3rd characters of A with (xx). After this operation, A is x(xx).
    • 







			


			
		

	
		

		

			H - Distance on Large Perfect Binary Tree
			

			
実行時間制限: 2 sec / メモリ制限: 1024 MiB


			

				


配点 : 500 点







問題文
2^N-1 頂点からなる木があります。

頂点には 1 から 2^N-1 の番号がつけられており、各 1\leq i < 2^{N-1} について、


    

  • 頂点 i と頂点 2i を結ぶ無向辺
    • 

  • 頂点 i と頂点 2i+1 を結ぶ無向辺
    • 



が存在します。これら以外の辺はありません。


2 頂点間の距離を、その 2 頂点を結ぶ単純パスに含まれる辺の個数とします。


頂点の組 (i,j) であって、距離が D であるようなものの個数を 998244353 で割った余りを求めてください。











制約
    

  • 2 \leq N \leq 10^6
    • 

  • 1 \leq D \leq 2\times 10^6
    • 

  • 入力に含まれる値は全て整数である
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N D












出力
答えを出力せよ。  















入力例 1
3 2












出力例 1
14



与えられる木は以下の図のようなものです。


図


距離が 2 であるような頂点の組は (1,4),(1,5),(1,6),(1,7),(2,3),(3,2),(4,1),(4,5),(5,1),(5,4),(6,1),(6,7),(7,1),(7,6) の 14 組存在します。













入力例 2
14142 17320












出力例 2
11284501







Score : 500 points







Problem Statement
We have a tree with 2^N-1 vertices.

The vertices are numbered 1 through 2^N-1. For each 1\leq i < 2^{N-1}, the following edges exist:


    

  • an undirected edge connecting Vertex i and Vertex 2i,
    • 

  • an undirected edge connecting Vertex i and Vertex 2i+1.
    • 



There is no other edge.


Let the distance between two vertices be the number of edges in the simple path connecting those two vertices.


Find the number, modulo 998244353, of pairs of vertices (i, j) such that the distance between them is D.











Constraints
    

  • 2 \leq N \leq 10^6
    • 

  • 1 \leq D \leq 2\times 10^6
    • 

  • All values in input are integers.
    • 
















Input
Input is given from Standard Input in the following format:


N D












Output
Print the answer. 















Sample Input 1
3 2












Sample Output 1
14



The following figure describes the given tree.


Figure


There are 14 pairs of vertices such that the distance between them is 2: (1,4),(1,5),(1,6),(1,7),(2,3),(3,2),(4,1),(4,5),(5,1),(5,4),(6,1),(6,7),(7,1),(7,6).













Sample Input 2
14142 17320












Sample Output 2
11284501






			


			
		

	
		

		

			I - More Holidays
			

			
実行時間制限: 2 sec / メモリ制限: 1024 MiB


			

				


配点 : 500 点







問題文
o と x からなる長さ N の文字列 S と、整数 M,K が与えられます。

S には少なくとも 1 つの x が含まれることが保証されます。


S を M 個連結して得られる長さ NM の文字列を T とします。
T に含まれる x のうち丁度 K 個を選んで o に変えることを考えます。

あなたの目標は、変更後の T に o のみからなるできるだけ長い連続部分文字列が含まれるようにすることです。

o のみからなる連続部分文字列の長さとして達成可能な最大値を求めてください。











制約
    

  • N,M,K は整数
    • 

  • 1 \le N \le 3 \times 10^5
    • 

  • 1 \le M \le 10^9
    • 

  • x を文字列 T に含まれる x の総数としたとき、 1 \le K \le x
    • 

  • S は o と x からなる長さ N の文字列
    • 

  • S には少なくとも 1 つの x が含まれる
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N M K
S












出力
答えを整数として出力せよ。















入力例 1
10 1 2
ooxxooooox












出力例 1
9



S= ooxxooooox 、 T= ooxxooooox です。

3 文字目と 4 文字目の x を o に変更することにより、変更後の T= ooooooooox となります。

このとき o のみからなる長さ 9 の連続部分文字列が得られ、これが達成可能な最大値です。













入力例 2
5 3 4
oxxox












出力例 2
8



S= oxxox 、 T= oxxoxoxxoxoxxox です。

5,7,8,10 文字目の x を o に変更することにより、変更後の T=  oxxooooooooxxox となります。

このとき o のみからなる長さ 8 の連続部分文字列が得られ、これが達成可能な最大値です。













入力例 3
30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox












出力例 3
19964887064







Score : 500 points







Problem Statement
You are given a string S of length N consisting of o and x, and integers M and K.

S is guaranteed to contain at least one x.


Let T be the string of length NM obtained by concatenating M copies of S.
Consider replacing exactly K x's in T with o.

Your objective is to have as long a contiguous substring consisting of o as possible in the resulting T.

Find the maximum length of a contiguous substring consisting of o that you can obtain.











Constraints
    

  • N, M, and K are integers.
    • 

  • 1 \le N \le 3 \times 10^5
    • 

  • 1 \le M \le 10^9
    • 

  • 1 \le K \le x, where x is the number of x's in the string T.
    • 

  • S is a string of length N consisting of o and x.
    • 

  • S has at least one x.
    • 
















Input
The input is given from Standard Input in the following format:


N M K
S












Output
Print the answer as an integer.















Sample Input 1
10 1 2
ooxxooooox












Sample Output 1
9



S= ooxxooooox and T= ooxxooooox.

Replacing x at the third and fourth characters with o makes T= ooooooooox.

Now we have a length-9 contiguous substring consisting of o, which is the longest possible.













Sample Input 2
5 3 4
oxxox












Sample Output 2
8



S= oxxox and T= oxxoxoxxoxoxxox.

Replacing x at the 5,7,8 and 10-th characters with o makes T= oxxooooooooxxox.

Now we have a length-8 contiguous substring consisting of o, which is the longest possible.













Sample Input 3
30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox












Sample Output 3
19964887064