Problem Statement

Given is a string S consisting of lowercase English letters. Find the maximum positive integer K that satisfies the following condition:

• There exists a partition of S into K non-empty strings S=S_1S_2...S_K such that S_i \neq S_{i+1} (1 \leq i \leq K-1).

Here S_1S_2...S_K represents the concatenation of S_1,S_2,...,S_K in this order.

Constraints

• 1 \leq |S| \leq 2 \times 10^5
• S consists of lowercase English letters.

Sample Input 1

aabbaa

Sample Output 1

4

We can, for example, divide S into four strings aa, b, ba, and a.

Sample Input 2

aaaccacabaababc

Sample Output 2

12

Problem Statement

We have 3N colored balls with IDs from 1 to 3N. A string S of length 3N represents the colors of the balls. The color of Ball i is red if S_i is R, green if S_i is G, and blue if S_i is B. There are N red balls, N green balls, and N blue balls.

Takahashi will distribute these 3N balls to N people so that each person gets one red ball, one blue ball, and one green ball. The people want balls with IDs close to each other, so he will additionally satisfy the following condition:

• Let a_j < b_j < c_j be the IDs of the balls received by the j-th person in ascending order.
• Then, \sum_j (c_j-a_j) should be as small as possible.

Find the number of ways in which Takahashi can distribute the balls. Since the answer can be enormous, compute it modulo 998244353. We consider two ways to distribute the balls different if and only if there is a person who receives different sets of balls.

Constraints

• 1 \leq N \leq 10^5
• |S|=3N
• S consists of R, G, and B, and each of these characters occurs N times in S.

Sample Input 1

3
RRRGGGBBB

Sample Output 1

216

The minimum value of \sum_j (c_j-a_j) is 18 when the balls are, for example, distributed as follows:

• The first person gets Ball 1, 5, and 9.
• The second person gets Ball 2, 4, and 8.
• The third person gets Ball 3, 6, and 7.

Sample Input 2

5
BBRGRRGRGGRBBGB

Sample Output 2

960

Problem Statement

There are N positive integers arranged in a circle.

Now, the i-th number is A_i. Takahashi wants the i-th number to be B_i. For this objective, he will repeatedly perform the following operation:

• Choose an integer i such that 1 \leq i \leq N.
• Let a, b, c be the (i-1)-th, i-th, and (i+1)-th numbers, respectively. Replace the i-th number with a+b+c.

Here the 0-th number is the N-th number, and the (N+1)-th number is the 1-st number.

Determine if Takahashi can achieve his objective. If the answer is yes, find the minimum number of operations required.

Constraints

• 3 \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 1 1
13 5 7

Sample Output 1

4

Takahashi can achieve his objective by, for example, performing the following operations:

• Replace the second number with 3.
• Replace the second number with 5.
• Replace the third number with 7.
• Replace the first number with 13.

Sample Input 2

4
1 2 3 4
2 3 4 5

Sample Output 2

-1

Sample Input 3

5
5 6 5 2 1
9817 1108 6890 4343 8704

Sample Output 3

25

Problem Statement

We have a grid with N rows and M columns of squares. Each integer from 1 to NM is written in this grid once. The number written in the square at the i-th row from the top and the j-th column from the left is A_{ij}.

You need to rearrange these numbers as follows:

1. First, for each of the N rows, rearrange the numbers written in it as you like.
2. Second, for each of the M columns, rearrange the numbers written in it as you like.
3. Finally, for each of the N rows, rearrange the numbers written in it as you like.

After rearranging the numbers, you want the number written in the square at the i-th row from the top and the j-th column from the left to be M\times (i-1)+j. Construct one such way to rearrange the numbers. The constraints guarantee that it is always possible to achieve the objective.

Constraints

• 1 \leq N,M \leq 100
• 1 \leq A_{ij} \leq NM
• A_{ij} are distinct.

Sample Input 1

3 2
2 6
4 3
1 5

Sample Output 1

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

Sample Input 2

3 4
1 4 7 10
2 5 8 11
3 6 9 12

Sample Output 2

1 4 7 10 
5 8 11 2 
9 12 3 6 
1 4 3 2 
5 8 7 6 
9 12 11 10 

Problem Statement

Takahashi has a string S of length N consisting of lowercase English letters. On this string, he will perform the following operation K times:

• Let T be the string obtained by reversing S, and U be the string obtained by concatenating S and T in this order.
• Let S' be some contiguous substring of U with length N, and replace S with S'.

Among the strings that can be the string S after the K operations, find the lexicographically smallest possible one.

Constraints

• 1 \leq N \leq 5000
• 1 \leq K \leq 10^9
• |S|=N
• S consists of lowercase English letters.

Sample Input 1

5 1
bacba

Sample Output 1

aabca

When S=bacba, T=abcab, U=bacbaabcab, and the optimal choice of S' is S'=aabca.

Sample Input 2

10 2
bbaabbbaab

Sample Output 2

aaaabbaabb

Problem Statement

For a sequence S of positive integers and positive integers k and l, S is said to belong to level (k,l) when one of the following conditions is satisfied:

• The length of S is 1, and its only element is k.
• There exist sequences T_1,T_2,...,T_m (m \geq l) belonging to level (k-1,l) such that the concatenation of T_1,T_2,...,T_m in this order coincides with S.

Note that the second condition has no effect when k=1, that is, a sequence belongs to level (1,l) only if the first condition is satisfied.

Given are a sequence of positive integers A_1,A_2,...,A_N and a positive integer L. Find the number of subsequences A_i,A_{i+1},...,A_j (1 \leq i \leq j \leq N) that satisfy the following condition:

• There exists a positive integer K such that the sequence A_i,A_{i+1},...,A_j belongs to level (K,L).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq L \leq N
• 1 \leq A_i \leq 10^9

Sample Input 1

9 3
2 1 1 1 1 1 1 2 3

Sample Output 1

22

For example, both of the sequences (1,1,1) and (2) belong to level (2,3), so the sequence (2,1,1,1,1,1,1) belong to level (3,3).

Sample Input 2

9 2
2 1 1 1 1 1 1 2 3

Sample Output 2

41

Sample Input 3

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

Sample Output 3

31