Problem Statement

There is a stack of N cards, and the i-th card from the top has an integer A_i written on it.

You take K cards from the bottom of the stack and place them on top of the stack, maintaining their order.

Print the integers written on the cards from top to bottom after the operation.

Constraints

• 1 \leq K < N \leq 100
• 1 \leq A_i \leq 100
• All input values are integers.

Sample Input 1

5 3
1 2 3 4 5

Sample Output 1

3 4 5 1 2

Initially, the integers written on the cards are 1,2,3,4,5 from top to bottom.

After taking three cards from the bottom of the stack and placing them on top, the integers written on the cards become 3,4,5,1,2 from top to bottom.

Sample Input 2

6 2
1 2 1 2 1 2

Sample Output 2

1 2 1 2 1 2

The integers written on the cards are not necessarily distinct.

Problem Statement

Takahashi and Aoki played N games. You are given a string S of length N, representing the results of these games. Takahashi won the i-th game if the i-th character of S is T, and Aoki won that game if it is A.

The overall winner between Takahashi and Aoki is the one who won more games than the other. If they had the same number of wins, the overall winner is the one who reached that number of wins first. Find the overall winner: Takahashi or Aoki.

Constraints

• 1\leq N \leq 100
• N is an integer.
• S is a string of length N consisting of T and A.

Sample Input 1

5
TTAAT

Sample Output 1

T

Takahashi won three games, and Aoki won two. Thus, the overall winner is Takahashi, who won more games.

Sample Input 2

6
ATTATA

Sample Output 2

T

Both Takahashi and Aoki won three games. Takahashi reached three wins in the fifth game, and Aoki in the sixth game. Thus, the overall winner is Takahashi, who reached three wins first.

Sample Input 3

1
A

Sample Output 3

A

Problem Statement

There are non-negative integers A, B, C, D, E, and F, which satisfy A\times B\times C\geq D\times E\times F.
Find the remainder when (A\times B\times C)-(D\times E\times F) is divided by 998244353.

Constraints

• 0\leq A,B,C,D,E,F\leq 10^{18}
• A\times B\times C\geq D\times E\times F
• A, B, C, D, E, and F are integers.

Sample Input 1

2 3 5 1 2 4

Sample Output 1

22

Since A\times B\times C=2\times 3\times 5=30 and D\times E\times F=1\times 2\times 4=8,
we have (A\times B\times C)-(D\times E\times F)=22. Divide this by 998244353 and print the remainder, which is 22.

Sample Input 2

1 1 1000000000 0 0 0

Sample Output 2

1755647

Since A\times B\times C=1000000000 and D\times E\times F=0,
we have (A\times B\times C)-(D\times E\times F)=1000000000. Divide this by 998244353 and print the remainder, which is 1755647.

Sample Input 3

1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

Sample Output 3

0

We have (A\times B\times C)-(D\times E\times F)=0. Divide this by 998244353 and print the remainder, which is 0.

Problem Statement

There is a grid with N rows and N columns. The cell at the i-th row from the top and j-th column from the left is painted black if S_{i,j} is #, and white if it is ..

How many distinct patterns of painted cells can be obtained by extracting a region of M rows and M columns from this grid?

Constraints

• 1\leq M \leq N \leq 10
• N and M are integers.
• S_{i,j} is . or #.

Sample Input 1

3 2
...
###
#.#

Sample Output 1

3

The state of the given grid is as shown in the left figure below.
There are four ways to extract a region of two rows and two columns from this grid as shown in the right figure below, and there are three distinct patterns of painted cells.

Sample Input 2

10 3
..#.......
.###......
.#.#......
#####.....
#...#.....
......####
......#..#
......#...
......#..#
......####

Sample Output 2

36

Problem Statement

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

• the strings of length 1 consisting of uppercase English letters, in lexicographical order;
• the strings of length 2 consisting of uppercase English letters, in lexicographical order;
• the strings of length 3 consisting of uppercase English letters, in lexicographical order;
• ...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

• S is a valid ID of a problem given in AtCoder Big Contest.

Sample Input 1

AB

Sample Output 1

28

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.

Sample Input 2

C

Sample Output 2

3

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.

Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.

Problem Statement

You are given an integer sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

Find how many pairs of integers (i,j)\ (1\le i\lt j\le N) satisfy j-i=A _ i+A _ j.

Constraints

• 1\le N\le2\times10 ^ 5
• 1\le A _ i\le2\times10 ^ 5\ (1\le i\le N)
• All input values are integers.

Sample Input 1

9
3 1 4 1 5 9 2 6 5

Sample Output 1

3

For example, when (i,j)=(4,7), we have j-i=7-4=3 and A _ i+A _ j=1+2=3, so j-i=A _ i+A _ j.

In contrast, when (i,j)=(3,8), we have j-i=8-3=5 and A _ i+A _ j=4+6=10, so j-i\ne A _ i+A _ j.

Only the three pairs (i,j)=(1,9),(2,4),(4,7) satisfy the condition, so output 3.

Sample Input 2

3
123456 123456 123456

Sample Output 2

0

There may be no pairs that satisfy the condition.

Sample Input 3

30
8 3 6 4 9 6 5 6 5 6 3 4 7 3 7 4 9 8 5 8 3 6 8 8 4 5 5 5 6 5

Sample Output 3

17

Problem Statement

You initially have an empty string S.
Additionally, there are bags 1, 2, \dots, N, each containing some strings.
Bag i contains A_i strings S_{i,1}, S_{i,2}, \dots, S_{i,A_i}.

You will repeat the following steps for i = 1, 2, \dots, N:

• Choose and perform one of the following two actions:
  • Pay 1 yen, select exactly one string from bag i, and concatenate it to the end of S.
  • Do nothing.

Given a string T, find the minimum amount of money required to make the final S equal T.
If there is no way to make the final S equal T, print -1.

Constraints

• T is a string consisting of lowercase English letters with length between 1 and 100, inclusive.
• N is an integer between 1 and 100, inclusive.
• A_i is an integer between 1 and 10, inclusive.
• S_{i,j} is a string consisting of lowercase English letters with length between 1 and 10, inclusive.

Sample Input 1

abcde
3
3 ab abc abcd
4 f c cd bcde
2 e de

Sample Output 1

2

For example, doing the following makes the final S equal T with two yen, which can be shown to be the minimum amount required.

• For i=1, select abc from bag 1 and concatenate it to the end of S, making S= abc.
• For i=2, do nothing.
• For i=3, select de from bag 3 and concatenate it to the end of S, making S= abcde.

Sample Input 2

abcde
3
2 ab abc
3 f c bcde
1 e

Sample Output 2

-1

There is no way to make the final S equal T, so print -1.

Sample Input 3

aaabbbbcccc
6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc

Sample Output 3

4

Problem Statement

You are given an integer sequence A = (A_1, \dots, A_N) of length N, and integers M and K.
For each i = 1, \dots, N - M + 1, solve the following independent problem.

Find the sum of the first K values in the sorted list of the M integers A_i, A_{i + 1}, \dots, A_{i + M - 1} in ascending order.

Constraints

• 1 \leq K \leq M \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6 4 3
3 1 4 1 5 9

Sample Output 1

5 6 10

• For i = 1, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 1, 3, 4, where the sum of the first three values is 5.
• For i = 2, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 1, 4, 5, where the sum of the first three values is 6.
• For i = 3, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 4, 5, 9, where the sum of the first three values is 10.

Sample Input 2

10 6 3
12 2 17 11 19 8 4 3 6 20

Sample Output 2

21 14 15 13 13

Problem Statement

You are given a positive integer N.

Among all valid arithmetic expressions consisting of the characters 1, +, *, (, and ), find one of the minimum length whose value is N.

More formally, among the strings S satisfying all of the following conditions, find one of the minimum length:

• S conforms to the symbol <expr> in the BNF below.
• The value of the expression represented by S is N.

<expr>   ::= <term> | <expr> "+" <term>
<term>   ::= <factor> | <term> "*" <factor>
<factor> ::= <number> | "(" <expr> ")"
<number> ::= "1" | "1" <number>

Strings that conform to <expr> include:

• 1111+111 representing 1111+111.
• (1+1)*(1+1) representing (1+1)\times(1+1).
• (11+(1+1)*(1+1))+1 representing (11+(1+1)\times(1+1))+1.

Strings that do not conform to <expr> include:

• (1+1)(1+1)
• 1+2
• 1-1
• 1/1
• )1(
• 1++1
• +1
• (+1)
• 1*+1

Constraints

• 1 \le N \le 2000
• All input values are integers.

Sample Input 1

9

Sample Output 1

(1+1+1)*(1+1+1)

Expressions whose value is 9 include:

• (1+1+1)*(1+1+1)
• 1+1+1+1+1+1+1+1+1
• (1+1)*(1+1)*(1+1)+1

Among them, a shortest is (1+1+1)*(1+1+1).

Sample Input 2

11

Sample Output 2

11

Sample Input 3

403

Sample Output 3

1+(1+1+1)*(1+11+11+111)