Problem Statement

You are given a string S of length N consisting only of lowercase English letters.

Find the number of strings obtained by permuting the characters of S (including the string S itself) that do not contain a palindrome of length K as a substring.

Here, a string T of length N is said to "contain a palindrome of length K as a substring" if and only if there exists a non-negative integer i not greater than (N-K) such that T_{i+j} = T_{i+K+1-j} for every integer j with 1 \leq j \leq K.
Here, T_k denotes the k-th character of the string T.

Constraints

• 2 \leq K \leq N \leq 10
• N and K are integers.
• S is a string of length N consisting only of lowercase English letters.

Sample Input 1

3 2
aab

Sample Output 1

1

The strings obtained by permuting aab are aab, aba, and baa. Among these, aab and baa contain the palindrome aa of length 2 as a substring.
Thus, the only string that satisfies the condition is aba, so print 1.

Sample Input 2

5 3
zzyyx

Sample Output 2

16

There are 30 strings obtained by permuting zzyyx, 16 of which do not contain a palindrome of length 3. Thus, print 16.

Sample Input 3

10 5
abcwxyzyxw

Sample Output 3

440640

Problem Statement

You are given a string S of length N. Let S_i\ (1\leq i \leq N) be the i-th character of S from the left.

You may perform the following two kinds of operations zero or more times in any order:

• Pay A yen (the currency in Japan). Move the leftmost character of S to the right end. In other words, change S_1S_2\ldots S_N to S_2\ldots S_NS_1.

• Pay B yen. Choose an integer i between 1 and N, and replace S_i with any lowercase English letter.

How many yen do you need to pay to make S a palindrome?

Constraints

• 1\leq N \leq 5000
• 1\leq A,B\leq 10^9
• S is a string of length N consisting of lowercase English letters.
• All values in the input except for S are integers.

Sample Input 1

5 1 2
rrefa

Sample Output 1

3

First, pay 2 yen to perform the operation of the second kind once: let i=5 to replace S_5 with e. S is now rrefe.

Then, pay 1 yen to perform the operation of the first kind once. S is now refer, which is a palindrome.

Thus, you can make S a palindrome for 3 yen. Since you cannot make S a palindrome for 2 yen or less, 3 is the answer.

Sample Input 2

8 1000000000 1000000000
bcdfcgaa

Sample Output 2

4000000000

Note that the answer may not fit into a 32-bit integer type.

Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i,j) the cell at the i-th row from the top and j-th column from the left. Each cell in the grid has a lowercase English letter written on it. The letter written on (i,j) equals the j-th character of a given string S_i.

Snuke will repeat moving to an adjacent cell sharing a side to travel from (1,1) to (H,W). Determine if there is a path in which the letters written on the visited cells (including initial (1,1) and final (H,W)) are s \rightarrow n \rightarrow u \rightarrow k \rightarrow e \rightarrow s \rightarrow n \rightarrow \dots, in the order of visiting. Here, a cell (i_1,j_1) is said to be an adjacent cell of (i_2,j_2) sharing a side if and only if |i_1-i_2|+|j_1-j_2| = 1.

Formally, determine if there is a sequence of cells ((i_1,j_1),(i_2,j_2),\dots,(i_k,j_k)) such that:

• (i_1,j_1) = (1,1),(i_k,j_k) = (H,W);
• (i_{t+1},j_{t+1}) is an adjacent cell of (i_t,j_t) sharing a side, for all t\ (1 \leq t < k); and
• the letter written on (i_t,j_t) coincides with the (((t-1) \bmod 5) + 1)-th character of snuke, for all t\ (1 \leq t \leq k).

Constraints

• 2\leq H,W \leq 500
• H and W are integers.
• S_i is a string of length W consisting of lowercase English letters.

Sample Input 1

2 3
sns
euk

Sample Output 1

Yes

The path (1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3) satisfies the conditions because they have s \rightarrow n \rightarrow u \rightarrow k written on them, in the order of visiting.

Sample Input 2

2 2
ab
cd

Sample Output 2

No

Sample Input 3

5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku

Sample Output 3

Yes

Problem Statement

There are N cells in a row, numbered 1 to N.
For each 1 \leq i < N, cells i and i+1 are adjacent.

Initially, cell i is painted with color i.

You are given Q queries. Process them in order. Each query is of one of the following two types.

• 1 x c: Repaint the following to color c: all reachable cells reachable from cell x by repeatedly moving to an adjacent cell painted in the same color as the current cell.
• 2 c: Print the number of cells painted with color c.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• In queries of the first type, 1 \leq x \leq N.
• In queries of the first and second types, 1 \leq c \leq N.
• There is at least one query of the second type.
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
4

The queries recolor the cells as shown in the figure.

Problem Statement

For a string S of length N and an integer i\ (0\leq i\leq N), let us define the string f_i(S) as the concatenation of:

• the first i characters of S,
• the reversal of S, and
• the last (N-i) characters of S,

in this order. For instance, if S= abc and i=2, we have f_i(S)= abcbac.

You are given a string T of length 2N. Find a pair of a string S of length N and an integer i\ (0\leq i\leq N) such that f_i(S)=T. If no such pair of S and i exists, report that fact.

Constraints

• 1\leq N \leq 10^6
• N is an integer.
• T is a string of length 2N consisting of lowercase English letters.

Sample Input 1

3
abcbac

Sample Output 1

abc
2

As mentioned in the problem statement, if S= abc and i=2, we have f_i(S)= abcbac, which equals T, so you should print abc and 2.

Sample Input 2

4
abababab

Sample Output 2

abab
1

S= abab and i=3 also satisfy the condition.

Sample Input 3

3
agccga

Sample Output 3

cga
0

S= agc and i=3 also satisfy the condition.

Sample Input 4

4
atcodeer

Sample Output 4

-1

If no pair of S and i satisfies the condition, print -1.