Problem Statement

You are given a string S of length N consisting of lowercase English letters.
If there are any adjacent occurrences of a and b in S, print Yes; otherwise, print No. (The order of a and b does not matter.)

Constraints

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

Sample Input 1

3
abc

Sample Output 1

Yes

The string abc has a as the first character and b as the second character, which are adjacent. Thus, print Yes.

Sample Input 2

2
ba

Sample Output 2

Yes

The string ba has a as the second character and b as the first character, which are adjacent. (Note that the order of a and b does not matter.)

Sample Input 3

7
atcoder

Sample Output 3

No

Problem Statement

You are given an integer N and a string S consisting of lowercase English letters with length less than N.

Print the string obtained by repeatedly adding the lowercase English letter o to the beginning of S until its length becomes N.

Constraints

• 2\leq N \leq 100
• N is an integer.
• S is a string consisting of lowercase English letters with length between 1 and N - 1, inclusive.

Sample Input 1

5
abc

Sample Output 1

ooabc

Since N=5 and the length of S is 3, the answer is the string obtained by adding 5-3=2 os to the beginning of S.

Sample Input 2

2
o

Sample Output 2

oo

Sample Input 3

12
vgxgpuam

Sample Output 3

oooovgxgpuam

Problem Statement

You are given strings S and T consisting of lowercase and uppercase English letters.

Determine whether the string S satisfies the following condition:

• Every uppercase letter in S that is not at the beginning is immediately preceded by a character contained in T. More formally, for all integers i such that 2 \leq i \leq |S|, if the i-th character of S is uppercase, then the (i-1)-th character of S is contained in T.

Constraints

• Each of S and T is a string consisting of lowercase and uppercase English letters with length between 1 and 100, inclusive.

Sample Input 1

AtCoder
Total

Sample Output 1

Yes

The only uppercase letter in S that is not at the beginning is the 3rd character C. The immediately preceding character t is contained in T, so output Yes.

Sample Input 2

aBCdE
abcdcba

Sample Output 2

No

The 3rd character of S is the uppercase letter C, and its immediately preceding character is B, but B is not contained in T.

Sample Input 3

abcde
XYZ

Sample Output 3

Yes

Problem Statement

You are given an integer sequence A=(A_1,\ldots,A_N) of length N. Here, A_1, A_2, \ldots, A_N are all distinct.

Which element in A is the second largest?

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 10^9
• A_1, A_2, \ldots, A_N are all distinct.
• All input values are integers.

Sample Input 1

4
8 2 5 1

Sample Output 1

3

The second largest element in A is A_3, so print 3.

Sample Input 2

8
1 2 3 4 5 10 9 11

Sample Output 2

6

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N). You can perform the following operation any number of times (possibly zero).

• Choose integers i and j with 1\leq i,j \leq N. Decrease A_i by one and increase A_j by one.

Find the minimum number of operations required to make the difference between the minimum and maximum values of A at most one.

Constraints

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

Sample Input 1

4
4 7 3 7

Sample Output 1

3

By the following three operations, the difference between the minimum and maximum values of A becomes at most one.

• Choose i=2 and j=3 to make A=(4,6,4,7).
• Choose i=4 and j=1 to make A=(5,6,4,6).
• Choose i=4 and j=3 to make A=(5,6,5,5).

You cannot make the difference between maximum and minimum values of A at most one by less than three operations, so the answer is 3.

Sample Input 2

1
313

Sample Output 2

0

Sample Input 3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

Sample Output 3

2499999974

Problem Statement

You are given a grid of H rows and W columns.
Let (i,j) denote the cell at row i (1 \leq i \leq H) from the top and column j (1 \leq j \leq W) from the left.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H, each of length W, as follows:

• If the j-th character of S_i is #, cell (i,j) is painted black.
• If the j-th character of S_i is ., cell (i,j) is painted white.
• If the j-th character of S_i is ?, cell (i,j) is not yet painted.

Takahashi wants to paint each not-yet-painted cell white or black so that all the black cells form a rectangle.
More precisely, he wants there to exist a quadruple of integers (a,b,c,d) (1 \leq a \leq b \leq H, 1 \leq c \leq d \leq W) such that:

For each cell (i,j) (1 \leq i \leq H, 1 \leq j \leq W), if a \leq i \leq b and c \leq j \leq d, the cell is black;
otherwise, the cell is white.

Determine whether this is possible.

Constraints

• 1 \leq H, W \leq 1000
• H and W are integers.
• Each S_i is a string of length W consisting of #, ., ?.
• There is at least one cell that is already painted black.

Sample Input 1

3 5
.#?#.
.?#?.
?...?

Sample Output 1

Yes

The grid is in the following state. ? indicates a cell that are not yet painted.

By painting cells (1,3), (2,2), and (2,4) black and cells (3,1) and (3,5) white, the black cells can form a rectangle as follows:

Therefore, print Yes.

Sample Input 2

3 3
?##
#.#
##?

Sample Output 2

No

To form a rectangle with all black cells, you would need to paint cell (2,2) black, but it is already painted white.
Therefore, it is impossible to make all black cells form a rectangle, so print No.

Sample Input 3

1 1
#

Sample Output 3

Yes

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.

Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a (not necessarily contiguous) subsequence B=(B_1,B_2,\dots,B_M) of length M of A.

Notes

A subsequence of a number sequence is a sequence that is obtained by removing 0 or more elements from the original number sequence and concatenating the remaining elements without changing the order.

For example, (10,30) is a subsequence of (10,20,30), but (20,10) is not a subsequence of (10,20,30).

Constraints

• 1 \le M \le N \le 2000
• - 2 \times 10^5 \le A_i \le 2 \times 10^5
• All values in input are integers.

Sample Input 1

4 2
5 4 -1 8

Sample Output 1

21

When B=(A_1,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times 5 + 2 \times 8 = 21. Since it is impossible to achieve 22 or a larger value, the solution is 21.

Sample Input 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

Sample Output 2

54

Problem Statement

You are given a string S of length N consisting of the three characters A, B, and C.
There are \frac{N(N+1)}{2} non-empty substrings of S; find how many of them satisfy the following condition:

• The numbers of occurrences of A, B, and C are all distinct from each other.

Count two substrings separately if they are taken from different positions in S, even if they are identical as strings.

Constraints

• 1 \leq N \leq 2 \times 10^5
• |S|=N
• N is an integer.
• S is a string consisting of the three characters A, B, and C.

Sample Input 1

6
AABBCC

Sample Output 1

4

Deleting 0 characters from the beginning and 3 characters from the end of S gives AAB, which satisfies the condition.
Deleting 1 character from the beginning and 2 characters from the end of S gives ABB, which satisfies the condition.
Deleting 2 characters from the beginning and 1 character from the end of S gives BBC, which satisfies the condition.
Deleting 3 characters from the beginning and 0 characters from the end of S gives BCC, which satisfies the condition.
No other substrings satisfy the condition.

Sample Input 2

6
ABCABC

Sample Output 2

0

No substring satisfies the condition.

Sample Input 3

10
ACABCAABAB

Sample Output 3

17

Problem Statement

Takahashi and Aoki will play a game using cards with numbers written on them.

Initially, Takahashi has N cards with numbers A_1, \ldots, A_N in his hand, Aoki has M cards with numbers B_1, \ldots, B_M in his hand, and there are L cards with numbers C_1, \ldots, C_L on the table.
Throughout the game, both Takahashi and Aoki know all the numbers on all the cards, including the opponent's hand.

Starting with Takahashi, they take turns performing the following action:

• Choose one card from his hand and put it on the table. Then, if there is a card on the table with a number less than the number on the card he just played, he may take one such card from the table into his hand.

The player who cannot make a move first loses, and the other player wins. Determine who wins if both players play optimally.

It can be proved that the game always ends in a finite number of moves.

Constraints

• 1 \leq N, M, L
• N + M + L \leq 12
• 1 \leq A_i, B_i, C_i \leq 10^9
• All input values are integers.

Sample Input 1

1 1 2
2
4
1 3

Sample Output 1

Aoki

The game may proceed as follows (not necessarily optimal moves):

• Takahashi plays 2 from his hand to the table, and takes 1 from the table into his hand. Now, Takahashi's hand is (1), Aoki's hand is (4), and the table cards are (2,3).
• Aoki plays 4 from his hand to the table, and takes 2 into his hand. Now, Takahashi's hand is (1), Aoki's hand is (2), and the table cards are (3,4).
• Takahashi plays 1 from his hand to the table. Now, Takahashi's hand is (), Aoki's hand is (2), and the table cards are (1,3,4).
• Aoki plays 2 from his hand to the table. Now, Takahashi's hand is (), Aoki's hand is (), and the table cards are (1,2,3,4).
• Takahashi cannot make a move and loses; Aoki wins.

Sample Input 2

4 4 4
98 98765 987654 987654321
987 9876 9876543 98765432
123 12345 1234567 123456789

Sample Output 2

Takahashi

Sample Input 3

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

Sample Output 3

Aoki