Problem Statement

You are given a string S consisting of uppercase and lowercase English letters.
Here, exactly one character of S is uppercase, and the others are all lowercase.
Find the integer x such that the x-th character of S is uppercase.
Here, the initial character of S is considered the 1-st one.

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of uppercase and lowercase English letters.
• S has exactly one uppercase letter.

Sample Input 1

aBc

Sample Output 1

2

The 1-st character of aBc is a, the 2-nd is B, and the 3-rd is c; the 2-nd character is uppercase.
Thus, 2 should be printed.

Sample Input 2

xxxxxxXxxx

Sample Output 2

7

An uppercase letter X occurs as the 7-th character of S=xxxxxxXxxx, so 7 should be printed.

Sample Input 3

Zz

Sample Output 3

1

Problem Statement

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

Determine whether there is a place in A where the same element appears three or more times in a row.

More formally, determine whether there exists an integer i with 1 \le i \le N-2 such that A_i = A_{i+1} = A_{i+2}.

Constraints

• 3 \le N \le 100
• 1 \le A_i \le 100
• All input values are integers.

Sample Input 1

5
1 4 4 4 2

Sample Output 1

Yes

We have A=(1,4,4,4,2). There is a place where 4 appears three times in a row, so print Yes.

Sample Input 2

6
2 4 4 2 2 4

Sample Output 2

No

We have A=(2,4,4,2,2,4). There is no place where the same element appears three or more times in a row, so print No.

Sample Input 3

8
1 4 2 5 7 7 7 2

Sample Output 3

Yes

Sample Input 4

10
1 2 3 4 5 6 7 8 9 10

Sample Output 4

No

Sample Input 5

13
1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 5

Yes

Problem Statement

On a non-empty string, a left shift moves the first character to the end of the string, and a right shift moves the last character to the beginning of the string.

For example, a left shift on abcde results in bcdea, and two right shifts on abcde result in deabc.

You are given a non-empty S consisting of lowercase English letters. Among the strings that can be obtained by performing zero or more left shifts and zero or more right shifts on S, find the lexicographically smallest string and the lexicographically largest string.

Constraints

• S consists of lowercase English letters.
• The length of S is between 1 and 1000 (inclusive).

Sample Input 1

aaba

Sample Output 1

aaab
baaa

By performing shifts, we can obtain four strings: aaab, aaba, abaa, baaa. The lexicographically smallest and largest among them are aaab and baaa, respectively.

Sample Input 2

z

Sample Output 2

z
z

Any sequence of operations results in z.

Sample Input 3

abracadabra

Sample Output 3

aabracadabr
racadabraab

Problem Statement

N players with ID numbers 1, 2, \ldots, N are playing a card game.
Each player plays one card.

Each card has two parameters: color and rank, both of which are represented by positive integers.
For i = 1, 2, \ldots, N, the card played by player i has a color C_i and a rank R_i. All of R_1, R_2, \ldots, R_N are different.

Among the N players, one winner is decided as follows.

• If one or more cards with the color T are played, the player who has played the card with the greatest rank among those cards is the winner.
• If no card with the color T is played, the player who has played the card with the greatest rank among the cards with the color of the card played by player 1 is the winner. (Note that player 1 may win.)

Print the ID number of the winner.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq T \leq 10^9
• 1 \leq C_i \leq 10^9
• 1 \leq R_i \leq 10^9
• i \neq j \implies R_i \neq R_j
• All values in the input are integers.

Sample Input 1

4 2
1 2 1 2
6 3 4 5

Sample Output 1

4

Cards with the color 2 are played. Thus, the winner is player 4, who has played the card with the greatest rank, 5, among those cards.

Sample Input 2

4 2
1 3 1 4
6 3 4 5

Sample Output 2

1

No card with the color 2 is played. Thus, the winner is player 1, who has played the card with the greatest rank, 6, among the cards with the color of the card played by player 1 (color 1).

Sample Input 3

2 1000000000
1000000000 1
1 1000000000

Sample Output 3

1

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N.

For each i=1,\ldots,N, solve the following problem.

Problem: Find the sum of all elements in A that are greater than A_i.

Constraints

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

Sample Input 1

5
1 4 1 4 2

Sample Output 1

10 0 10 0 8

• For i=1, the sum of elements greater than A_1=1 is 4+4+2=10.
• For i=2, the sum of elements greater than A_2=4 is 0.
• For i=3, the sum of elements greater than A_3=1 is 4+4+2=10.
• For i=4, the sum of elements greater than A_4=4 is 0.
• For i=5, the sum of elements greater than A_5=2 is 4+4=8.

Sample Input 2

10
31 42 59 26 53 58 97 93 23 54

Sample Output 2

456 414 190 487 361 249 0 97 513 307

Sample Input 3

50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Problem Statement

You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.

Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:

• for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.

Constraints

• 2 \le N \le 8
• 1 \le M \le 5
• S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
• S_i are pairwise distinct.

Sample Input 1

4 4
bbed
abcd
abed
fbed

Sample Output 1

Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.

Sample Input 2

2 5
abcde
abced

Sample Output 2

No

No matter how the strings are rearranged, the condition is never satisfied.

Sample Input 3

8 4
fast
face
cast
race
fact
rice
nice
case

Sample Output 3

Yes

Problem Statement

Takahashi will encounter N monsters in order. The i-th monster (1\leq i\leq N) has a strength of A_i.

For each monster, he can choose to either let it go or defeat it.
Each action awards him experience points as follows:

• If he lets a monster go, he gains 0 experience points.
• If he defeats a monster with strength X, he gains X experience points.
  If it is an even-numbered defeated monster (2nd, 4th, ...), he gains an additional X experience points.

Find the maximum total experience points he can gain from the N monsters.

Constraints

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

Sample Input 1

5
1 5 3 2 7

Sample Output 1

28

If Takahashi defeats the 1st, 2nd, 3rd, and 5th monsters, and lets the 4th monster go, he gains experience points as follows:

• Defeats a monster with strength A_1=1. He gains 1 experience point.
• Defeats a monster with strength A_2=5. He gains 5 experience points. As it is the 2nd defeated monster, he gains an additional 5 points.
• Defeats a monster with strength A_3=3. He gains 3 experience points.
• Lets the 4th monster go. Takahashi gains no experience points.
• Defeats a monster with strength A_5=7. He gains 7 experience points. As it is the 4th defeated monster, he gains an additional 7 points.

Therefore, in this case, he gains 1+(5+5)+3+0+(7+7)=28 experience points.
Note that even if he encounters a monster, if he lets it go, it does not count as defeated.

He can gain at most 28 experience points no matter how he acts, so print 28.
As a side note, if he defeats all monsters in this case, he would gain 1+(5+5)+3+(2+2)+7=25 experience points.

Sample Input 2

2
1000000000 1000000000

Sample Output 2

3000000000

Beware that the answer may not fit in a 32-bit integer.

Problem Statement

10^{100} potatoes are coming from a conveyor belt one by one. The weights of the potatoes are described by a sequence W = (W_0, \dots, W_{N-1}) of length N: the weight of the i-th potato coming is W_{(i-1) \bmod N}, where (i-1) \bmod N denotes the remainder when i - 1 is divided by N.

Takahashi will prepare an empty box and then pack the potatoes in order, as follows.

• Pack the incoming potato into the box. If the total weight of the potatoes in the box is now X or greater, seal that box and prepare a new empty box.

You are given Q queries. In the i-th query (1 \leq i \leq Q), given a positive integer K_i, find the number of potatoes in the K_i-th box to be sealed. It can be proved that, under the Constraints of the problem, there will be at least K_i sealed boxes.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq X \leq 10^9
• 1 \leq W_i \leq 10^9 \, (0 \leq i \leq N - 1)
• 1 \leq K_i \leq 10^{12} \, (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

3 2 5
3 4 1
1
2

Sample Output 1

2
3

Before sealing the 2-nd box, Takahashi will do the following:

• Prepare an empty box.
• Pack the 1-st potato into the box. Now, the total weight of potatoes in the box is 3.
• Pack the 2-nd potato into the box. Now, the total weight of potatoes in the box is 3 + 4 = 7, which is not less than X = 5, so seal this box.
• Prepare a new empty box.
• Pack the 3-rd potato into the box. Now, the total weight of potatoes in the box is 1.
• Pack the 4-th potato into the box. Now, the total weight of potatoes in the box is 1 + 3 = 4.
• Pack the 5-th potato into the box. Now, the total weight of potatoes in the box is 1 + 3 + 4 = 8, which is not less than X = 5, so seal this box.

The 1-st box sealed contains 2 potatoes, and the 2-nd box sealed contains 3 potatoes.

Sample Input 2

10 5 20
5 8 5 9 8 7 4 4 8 2
1
1000
1000000
1000000000
1000000000000

Sample Output 2

4
5
5
5
5

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
For each pair of integers (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, (i, j) contains a positive integer A_{i,j}. Additionally, every square is painted white.

Takahashi has a rectangular black stamp that can cover h_1 rows and w_1 columns, and Aoki has a rectangular white stamp that can cover h_2 rows and w_2 columns. Using these stamps and the grid, they will play a game against each other.

First, Takahashi presses his black stamp to paint a rectangular region with h_1 rows and w_1 columns black.
That is, he chooses a pair of integers (i, j) such that 1 \leq i \leq H - h_1 + 1 and 1 \leq j \leq W - w_1 + 1, and paints black every square (r, c) such that i \leq r \leq i + h_1 - 1 and j \leq c \leq j + w_1 - 1.

Second, Aoki presses his white stamp to paint a rectangular region with h_2 rows and w_2 columns white.
That is, he chooses a pair of integers (i, j) such that 1 \leq i \leq H - h_2 + 1 and 1 \leq j \leq W - w_2 + 1, and paints white every square (r, c) such that i \leq r \leq i + h_2 - 1 and j \leq c \leq j + w_2 - 1.
If some of these squares are already painted black by Takahashi, they will also become white.

The game's score is defined as the sum of the integers written on the squares painted black after Takahashi and Aoki press their stamps as described above. Takahashi follows the optimal strategy to make the score as large as possible, while Aoki follows the optimal strategy to make the score as small as possible. What will the game's score be?

Constraints

• 2 \leq H, W \leq 1000
• 1 \leq h_1, h_2 \leq H
• 1 \leq w_1, w_2 \leq W
• 1 \leq A_{i, j} \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

19

The game will go as follows.

• Initially, all squares are painted white.
• First, Takahashi presses his 2 \times 3 black stamp to paint the following six squares black: (2, 2), (2, 3), (2 ,4), (3, 2), (3, 3), (3, 4).
• Second, Aoki presses his 3 \times 1 white stamp to paint the following three squares white: (1, 4), (2, 4), (3, 4).
• Eventually, the following four squares are painted black: (2, 2), (2, 3), (3, 2), (3, 3), for a score of 9 + 2 + 3 + 5 = 19.

Sample Input 2

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

Sample Output 2

0

After Aoki presses his stamp, all squares will be white, for a score of 0.

Sample Input 3

10 10 3 7 2 3
9 7 19 7 10 4 13 9 4 8
10 15 16 3 18 19 17 12 13 2
12 18 4 9 13 13 6 13 5 2
16 12 2 14 18 17 14 7 8 12
12 13 17 12 14 15 19 7 13 15
5 2 16 10 4 6 1 2 7 8
10 14 14 10 9 13 11 4 9 19
16 12 3 19 19 6 2 19 14 20
15 3 19 19 2 10 1 4 3 15
13 20 5 6 19 1 7 17 10 19

Sample Output 3

180