Problem Statement

The magnitude of an earthquake is a logarithmic scale of the energy released by the earthquake. It is known that each time the magnitude increases by 1, the amount of energy gets multiplied by approximately 32.
Here, we assume that the amount of energy gets multiplied by exactly 32 each time the magnitude increases by 1. In this case, how many times is the amount of energy of a magnitude A earthquake as much as that of a magnitude B earthquake?

Constraints

• 3\leq B\leq A\leq 9
• A and B are integers.

Sample Input 1

6 4

Sample Output 1

1024

6 is 2 greater than 4, so a magnitude 6 earthquake has 32\times 32=1024 times as much energy as a magnitude 4 earthquake has.

Sample Input 2

5 5

Sample Output 2

1

Earthquakes with the same magnitude have the same amount of energy.

Problem Statement

You are given an N-character string S consisting of lowercase English letters.

Output the string of N-A-B characters obtained by removing the first A characters and the last B characters from S.

Constraints

• 1\le N\le20
• 0\le A
• 0\le B
• A+B\lt N
• S is a string of N characters consisting of lowercase English letters.
• N, A, and B are all integers.

Sample Input 1

7 1 3
atcoder

Sample Output 1

tco

Removing the first one character and the last three characters from atcoder gives tco.

Sample Input 2

1 0 0
a

Sample Output 2

a

The string to be output may be equal to S.

Sample Input 3

20 4 8
abcdefghijklmnopqrst

Sample Output 3

efghijkl

Problem Statement

You are given integer sequences, each of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
All elements of A are different. All elements of B are different, too.

Print the following two values.

1. The number of integers contained in both A and B, appearing at the same position in the two sequences. In other words, the number of integers i such that A_i = B_i.
2. The number of integers contained in both A and B, appearing at different positions in the two sequences. In other words, the number of pairs of integers (i, j) such that A_i = B_j and i \neq j.

Constraints

• 1 \leq N \leq 1000
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• A_1, A_2, \dots, A_N are all different.
• B_1, B_2, \dots, B_N are all different.
• All values in input are integers.

Sample Input 1

4
1 3 5 2
2 3 1 4

Sample Output 1

1
2

There is one integer contained in both A and B, appearing at the same position in the two sequences: A_2 = B_2 = 3.
There are two integers contained in both A and B, appearing at different positions in the two sequences: A_1 = B_3 = 1 and A_4 = B_1 = 2.

Sample Input 2

3
1 2 3
4 5 6

Sample Output 2

0
0

In both 1. and 2., no integer satisfies the condition.

Sample Input 3

7
4 8 1 7 9 5 6
3 5 1 7 8 2 6

Sample Output 3

3
2

Problem Statement

You are given a string S consisting of lowercase English letters. Remove all occurrences of the most frequent character(s) in S, then output the remaining characters concatenated in their original order.

If there are multiple characters with the maximum frequency, remove all of them.

Constraints

• 1 \le |S| \le 100
• S is a string consisting of lowercase English letters.

Sample Input 1

mississippi

Sample Output 1

mpp

The most frequent characters in mississippi are s and i, each appearing four times. Removing all occurrences of s and i yields the string mpp.

Sample Input 2

atcoder

Sample Output 2

Sample Input 3

beginner

Sample Output 3

bgir

Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition. This definition is the same as the one in Problem A.

• The digits of x are strictly decreasing from top to bottom.
• In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
  • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

Find the K-th smallest 321-like Number.

Constraints

• All input values are integers.
• 1 \le K
• At least K 321-like Numbers exist.

Sample Input 1

15

Sample Output 1

32

The 321-like Numbers are (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) from smallest to largest.
The 15-th smallest of them is 32.

Sample Input 2

321

Sample Output 2

9610

Sample Input 3

777

Sample Output 3

983210

Problem Statement

We have a sequence of length N: A=(a_1,\ldots,a_N). Additionally, you are given an integer K.

You can perform the following operation zero or more times.

• Choose an integer i such that 1 \leq i \leq N-K, then swap the values of a_i and a_{i+K}.

Determine whether it is possible to sort A in ascending order.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N-1
• 1 \leq a_i \leq 10^9
• All values in input are integers.

Sample Input 1

5 2
3 4 1 3 4

Sample Output 1

Yes

The following sequence of operations sorts A in ascending order.

• Choose i=1 to swap the values of a_1 and a_3. A is now (1,4,3,3,4).
• Choose i=2 to swap the values of a_2 and a_4. A is now (1,3,3,4,4).

Sample Input 2

5 3
3 4 1 3 4

Sample Output 2

No

Sample Input 3

7 5
1 2 3 4 5 5 10

Sample Output 3

Yes

No operations may be needed.

Problem Statement

There are H \times W cookies in H rows and W columns.
The color of the cookie at the i-row from the top and j-th column from the left is represented by a lowercase English letter c_{i,j}.

We will perform the following procedure.

1. For each row, perform the following operation: if there are two or more cookies remaining in the row and they all have the same color, mark them.

2. For each column, perform the following operation: if there are two or more cookies remaining in the column and they all have the same color, mark them.

3. If there are any marked cookies, remove them all and return to 1; otherwise, terminate the procedure.

Find the number of cookies remaining at the end of the procedure.

Constraints

• 2 \leq H, W \leq 2000
• c_{i,j} is a lowercase English letter.

Sample Input 1

4 3
aaa
aaa
abc
abd

Sample Output 1

2

The procedure is performed as follows.

• 1. Mark the cookies in the first and second rows.
• 2. Mark the cookies in the first column.
• 3. Remove the marked cookies.

At this point, the cookies look like the following, where . indicates a position where the cookie has been removed.

...
...
.bc
.bd

• 1. Do nothing.
• 2. Mark the cookies in the second column.
• 3. Remove the marked cookies.

At this point, the cookies look like the following, where . indicates a position where the cookie has been removed.

...
...
..c
..d

• 1. Do nothing.
• 2. Do nothing.
• 3. No cookies are marked, so terminate the procedure.

The final number of cookies remaining is 2.

Sample Input 2

2 5
aaaaa
abcde

Sample Output 2

4

Sample Input 3

3 3
ooo
ooo
ooo

Sample Output 3

0

Problem Statement

We have a number sequence A = (A_1, A_2, \dots, A_N) of length N and integers X and Y. Find the number of pairs of integers (L, R) satisfying all the conditions below.

• 1 \leq L \leq R \leq N
• The maximum value of A_L, A_{L+1}, \dots, A_R is X, and the minimum is Y.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 2 \times 10^5
• 1 \leq Y \leq X \leq 2 \times 10^5
• All values in input are integers.

Sample Input 1

4 3 1
1 2 3 1

Sample Output 1

4

4 pairs satisfy the conditions: (L,R)=(1,3),(1,4),(2,4),(3,4).

Sample Input 2

5 2 1
1 3 2 4 1

Sample Output 2

0

No pair (L,R) satisfies the condition.

Sample Input 3

5 1 1
1 1 1 1 1

Sample Output 3

15

It may hold that X=Y.

Sample Input 4

10 8 1
2 7 1 8 2 8 1 8 2 8

Sample Output 4

36

Problem Statement

We have a loaf of bread of length L, which we will cut and distribute to N children.
The i-th child (1\leq i\leq N) wants a loaf of length A_i.

Now, Takahashi will repeat the operation below to cut the loaf into lengths A_1, A_2, \ldots, A_N for the children.

Choose a loaf of length k and an integer x between 1 and k-1 (inclusive). Cut the loaf into two loaves of length x and k-x.
This operation incurs a cost of k regardless of the value of x.

Each child i must receive a loaf of length exactly A_i, but it is allowed to leave some loaves undistributed.

Find the minimum cost needed to distribute loaves to all children.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1\leq A_i\leq 10^9
• A_1+A_2+\cdots+A_N\leq L\leq 10^{15}
• All values in input are integers.

Sample Input 1

5 7
1 2 1 2 1

Sample Output 1

16

Takahashi can cut the loaf for the children as follows.

• Choose the loaf of length 7 and x=3, cutting it into loaves of length 3 and 4 for a cost of 7.
• Choose the loaf of length 3 and x=1, cutting it into loaves of length 1 and 2 for a cost of 3. Give the former to the 1-st child.
• Choose the loaf of length 2 and x=1, cutting it into two loaves of length 1 for a cost of 2. Give them to the 3-rd and 5-th children.
• Choose the loaf of length 4 and x=2, cutting it into two loaves of length 2 for a cost of 4. Give them to the 2-nd and 4-th children.

This incurs a cost of 7+3+2+4=16, which is the minimum possible. There will be no leftover loaves.

Sample Input 2

3 1000000000000000
1000000000 1000000000 1000000000

Sample Output 2

1000005000000000

Note that each child i must receive a loaf of length exactly A_i.