Problem Statement

You are given a string S of length N consisting of A, B, and C.
Find the position where ABC first appears as a (contiguous) substring in S. In other words, find the smallest integer n that satisfies all of the following conditions.

• 1 \leq n \leq N - 2.
• The string obtained by extracting the n-th through (n+2)-th characters of S is ABC.

If ABC does not appear in S, print -1.

Constraints

• 3 \leq N \leq 100
• S is a string of length N consisting of A, B, and C.

Sample Input 1

8
ABABCABC

Sample Output 1

3

ABC first appears in S at the 3-rd through 5-th characters of S. Therefore, the answer is 3.

Sample Input 2

3
ACB

Sample Output 2

-1

If ABC does not appear in S, print -1.

Sample Input 3

20
BBAAABBACAACABCBABAB

Sample Output 3

13

Problem Statement

You are given two strings S and T consisting of lowercase English letters. The lengths of S and T are N and M, respectively. (The constraints guarantee that N \leq M.)

S is said to be a prefix of T when the first N characters of T coincide S.
S is said to be a suffix of T when the last N characters of T coincide S.

If S is both a prefix and a suffix of T, print 0;
If S is a prefix of T but not a suffix, print 1;
If S is a suffix of T but not a prefix, print 2;
If S is neither a prefix nor a suffix of T, print 3.

Constraints

• 1 \leq N \leq M \leq 100
• S is a string of length N consisting of lowercase English letters.
• T is a string of length M consisting of lowercase English letters.

Sample Input 1

3 7
abc
abcdefg

Sample Output 1

1

S is a prefix of T but not a suffix, so you should print 1.

Sample Input 2

3 4
abc
aabc

Sample Output 2

2

S is a suffix of T but not a prefix.

Sample Input 3

3 3
abc
xyz

Sample Output 3

3

S is neither a prefix nor a suffix of T.

Sample Input 4

3 3
aaa
aaa

Sample Output 4

0

S and T may coincide, in which case S is both a prefix and a suffix of T.

Problem Statement

The AtCoder Kingdom holds a festival for N days. On M of these days, namely on the A_1-th, A_2-th, \dots, A_M-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, A_M=N is guaranteed.)

For each i=1,2,\dots,N, solve the following problem.

• How many days later from the i-th day will fireworks be launched for the first time on or after the i-th day? If fireworks are launched on the i-th day, it is considered to be 0 days later.

Constraints

• 1 \le M \le N \le 2 \times 10^5
• 1 \le A_1 < A_2 < \dots < A_M = N
• All input values are integers.

Sample Input 1

3 2
2 3

Sample Output 1

1
0
0

The kingdom holds a festival for 3 days, and fireworks are launched on the 2-nd and 3-rd days.

• From the 1-st day, the first time fireworks are launched is the 2-nd day of the festival, which is 1 day later.
• From the 2-nd day, the first time fireworks are launched is the 2-nd day of the festival, which is 0 days later.
• From the 3-rd day, the first time fireworks are launched is the 3-rd day of the festival, which is 0 days later.

Sample Input 2

8 5
1 3 4 7 8

Sample Output 2

0
1
0
0
2
1
0
0

Problem Statement

A polyomino is a puzzle piece in the shape of a connected polygon made by connecting several squares by their edges.

There is a grid with four rows and four columns, and three polyominoes that fit within the grid.
The shape of the i-th polyomino is represented by 16 characters P_{i,j,k} (1 \leq j, k \leq 4). They describe the state of the grid when the i-th polyomino is placed on it. If P_{i, j, k} is #, the square at the j-th row from the top and k-th column from the left is occupied by the polyomino; if it is ., the square is not occupied. (Refer to the figures at Sample Input/Output 1.)

You want to fill the grid with all three polyominoes so that all of the following conditions are satisfied.

• All squares of the grid are covered by the polyominoes.
• The polyominoes must not overlap each other.
• The polyominoes must not stick out of the grid.
• The polyominoes may be freely translated and rotated but may not be flipped over.

Can the grid be filled with the polyominoes to satisfy these conditions?

Constraints

• P_{i, j, k} is # or ..
• The given polyominoes are connected. In other words, the squares that make up a polyomino can be reached from each other by following only the squares up, down, left, and right.
• The given polyominoes are not empty.

Sample Input 1

....
###.
.#..
....
....
.###
.##.
....
..#.
.##.
.##.
.##.

Sample Output 1

Yes

The figure below shows the shapes of the polyominoes corresponding to Sample Input 1.

In this case, you can fill the grid with them to satisfy the conditions in the problem statement by placing them as shown in the figure below.

Thus, the answer is Yes.

Sample Input 2

###.
#.#.
##..
....
....
..#.
....
....
####
##..
#...
#...

Sample Output 2

Yes

As in the first polyomino in Sample Input 2, a polyomino may be in the shape of a polygon with a hole.

Sample Input 3

##..
#..#
####
....
....
##..
.##.
....
.#..
.#..
.#..
.#..

Sample Output 3

No

Note that the polyominoes may not be flipped over when filling the grid.

Sample Input 4

....
..#.
....
....
....
..#.
....
....
....
..#.
....
....

Sample Output 4

No

Sample Input 5

....
####
#...
#...
....
####
...#
..##
....
..##
..#.
..##

Sample Output 5

No

Sample Input 6

###.
.##.
..#.
.###
....
...#
..##
...#
....
#...
#...
#...

Sample Output 6

Yes

Problem Statement

AtCoder Inc. is planning to develop a product. The product has K parameters, whose values are currently all zero. The company aims to raise all parameter values to at least P.

There are N development plans. Executing the i-th development plan (1 \le i \le N) increases the value of the j-th parameter by A_{i,j} for every integer j such that 1 \le j \le K, at the cost of C_i.

A development plan cannot be executed more than once. Determine whether the company can achieve its goal, and if it can, find the minimum total cost required to achieve the goal.

Constraints

• 1 \le N \le 100
• 1 \le K,P \le 5
• 0 \le A_{i,j} \le P(1 \le i \le N,1 \le j \le K)
• 1 \le C_i \le 10^9(1 \le i \le N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

9

If you execute the first, third, and fourth development plans, each parameter will be 3+2+0=5,0+4+1=5,2+0+4=6, all of which are at least 5, so the goal is achieved. The total cost in this case is 5 + 3 + 1 = 9.

It is impossible to achieve the goal at a total cost of 8 or less. Thus, the answer is 9.

Sample Input 2

7 3 5
85 1 0 1
37 1 1 0
38 2 0 0
45 0 2 2
67 1 1 0
12 2 2 0
94 2 2 1

Sample Output 2

-1

You cannot achieve the goal no matter what you do. Thus, print -1.

Problem Statement

You are given a string S of length N consisting of 0 and 1. Let S_i denote the i-th character of S.

Process Q queries in the order they are given.
Each query is represented by a tuple of three integers (c, L, R), where c represents the type of the query.

• When c=1: For each integer i such that L \leq i \leq R, if S_i is 1, change it to 0; if it is 0, change it to 1.
• When c=2: Let T be the string obtained by extracting the L-th through R-th characters of S. Print the maximum number of consecutive 1s in T.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq Q \leq 10^5
• S is a string of length N consisting of 0 and 1.
• c \in \lbrace 1, 2 \rbrace
• 1 \leq L \leq R \leq N
• N, Q, c, L, and R are all integers.

Sample Input 1

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

Sample Output 1

3
1
0
7

The queries are processed as follows.

• Initially, S= 1101110.
• For the first query, T = 1101110. The longest sequence of consecutive 1s in T is 111 from the 4-th character to 6-th character, so the answer is 3.
• For the second query, T = 101. The longest sequence of consecutive 1s in T is 1 at the 1-st or 3-rd character, so the answer is 1.
• For the third query, the operation changes S to 1110000.
• For the fourth query, T = 00. T does not contain 1, so the answer is 0.
• For the fifth query, the operation changes S to 1111111.
• For the sixth query, T = 1111111. The longest sequence of consecutive 1s in T is 1111111 from the 1-st to 7-th characters, so the answer is 7.

Problem Statement

For a non-negative integer sequence S=(S_1,S_2,\dots,S_k) and an integer a, we define the function f(S,a) as follows:

• f(S,a) = \sum_{i=1}^{k} S_i \times a^{k - i}.

For example, f((1,2,3),4) = 1 \times 4^2 + 2 \times 4^1 + 3 \times 4^0 = 27, and f((1,1,1,1),10) = 1 \times 10^3 + 1 \times 10^2 + 1 \times 10^1 + 1 \times 10^0 = 1111.

You are given positive integers N and X. Find the number, modulo 998244353, of triples (S,a,b) of a sequence of non-negative integers S=(S_1,S_2,\dots,S_k) and positive integers a and b that satisfy all of the following conditions.

• k \ge 1
• a,b \le N
• S_1 \neq 0
• S_i < \min(10,a,b)(1 \le i \le k)
• f(S,a) - f(S,b) = X

Constraints

• 1 \le N \le 10^9
• 1 \le X \le 2 \times 10^5
• All input values are integers.

Sample Input 1

4 2

Sample Output 1

5

The five triples (S,a,b)=((1,0),4,2),((1,1),4,2),((2,0),4,3),((2,1),4,3),((2,2),4,3) satisfy the conditions.

Sample Input 2

9 30

Sample Output 2

31

Sample Input 3

322322322 200000

Sample Output 3

140058961