Problem Statement

Locate a piece on a chessboard.

We have a grid with 8 rows and 8 columns of squares. Each of the squares has a 2-character name determined as follows.

• The first character of the name of a square in the 1-st column from the left is a. Similarly, the first character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th column from the left is b, c, d, e, f, g, h, respectively.
• The second character of the name of a square in the 1-st row from the bottom is 1. Similarly, the second character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th row from the bottom is 2, 3, 4, 5, 6, 7, 8, respectively.

For instance, the bottom-left square is named a1, the bottom-right square is named h1, and the top-right square is named h8.

You are given 8 strings S_1,\ldots,S_8, each of length 8, representing the state of the grid.
The j-th character of S_i is * if the square at the i-th row from the top and j-th column from the left has a piece on it, and . otherwise. The character * occurs exactly once among S_1,\ldots,S_8. Find the name of the square that has a piece on it.

Constraints

• S_i is a string of length 8 consisting of . and*.
• The character * occurs exactly once among S_1,\ldots,S_8.

Sample Input 1

........
........
........
........
........
........
........
*.......

Sample Output 1

a1

As explained in the problem statement, the bottom-left square is named a1.

Sample Input 2

........
........
........
........
........
.*......
........
........

Sample Output 2

b3

Problem Statement

You are given N integers A_1, A_2, \ldots, A_N. Find the largest among those integers that are not the largest.

The constraints of this problem guarantee that the answer exists.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• It is not the case that all A_1, A_2, \ldots, A_N are equal.
• All input values are integers.

Sample Input 1

5
2 1 3 3 2

Sample Output 1

2

The largest integer among 2,1,3,3,2 is 3.

The integers that are not 3 among 2,1,3,3,2 are 2,1,2, among which the largest is 2.

Sample Input 2

4
4 3 2 1

Sample Output 2

3

Sample Input 3

8
22 22 18 16 22 18 18 22

Sample Output 3

18

Problem Statement

A bus is in operation. The number of passengers on the bus is always a non-negative integer.

At some point in time, the bus had zero or more passengers, and it has stopped N times since then. At the i-th stop, the number of passengers increased by A_i. Here, A_i can be negative, meaning the number of passengers decreased by -A_i. Also, no passengers got on or off the bus other than at the stops.

Find the minimum possible current number of passengers on the bus that is consistent with the given information.

Constraints

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

Sample Input 1

4
3 -5 7 -4

Sample Output 1

3

If the initial number of passengers was 2, the current number of passengers would be 2 + 3 + (-5) + 7 + (-4) = 3, and the number of passengers on the bus would have always been a non-negative integer.

Sample Input 2

5
0 0 0 0 0

Sample Output 2

0

Sample Input 3

4
-1 1000000000 1000000000 1000000000

Sample Output 3

3000000000

Problem Statement

Planning to place many PCs in his room, Takahashi has decided to write a code that finds how many PCs he can place in his room.

You are given H strings S_1,S_2,\ldots,S_H, each of length W, consisting of . and T.

Takahashi may perform the following operation any number of times (possibly zero):

• Choose integers satisfying 1\leq i \leq H and 1 \leq j \leq W-1 such that the j-th and (j+1)-th characters of S_i are both T. Replace the j-th character of S_i with P, and (j+1)-th with C.

He tries to maximize the number of times he performs the operation. Find possible resulting S_1,S_2,\ldots,S_H.

Constraints

• 1\leq H \leq 100
• 2\leq W \leq 100
• H and W are integers.
• S_i is a string of length W consisting of . and T.

Sample Input 1

2 3
TTT
T.T

Sample Output 1

PCT
T.T

He can perform the operation at most once.

For example, an operation with (i,j)=(1,1) makes S_1 PCT.

Sample Input 2

3 5
TTT..
.TTT.
TTTTT

Sample Output 2

PCT..
.PCT.
PCTPC

Problem Statement

Takahashi is having trouble with deciding a username for a service. Write a code to help him.

Find a string X that satisfies all of the following conditions:

• X is obtained by the following procedure:
  • Let S_1', S_2', \ldots,S_N' be a permutation of S_1, S_2, \ldots,S_N. Let X be the concatenation of S_1', (1 or more copies of _), S_2', (1 or more copies of _), \ldots, (1 or more copies of _), and S_N', in this order.
• The length of X is between 3 and 16, inclusive.
• X does not coincide with any of M strings T_1,T_2,\ldots,T_M.

If there is no X that satisfies all of the conditions, print -1 instead.

Constraints

• 1 \leq N \leq 8
• 0 \leq M \leq 10^5
• N and M are integers.
• 1 \leq |S_i| \leq 16
• N-1+\sum{|S_i|} \leq 16
• S_i \neq S_j if i \neq j.
• S_i is a string consisting of lowercase English letters.
• 3 \leq |T_i| \leq 16
• T_i \neq T_j if i \neq j.
• T_i is a string consisting of lowercase English letters and _.

Sample Input 1

1 1
chokudai
chokudai

Sample Output 1

-1

The only string that satisfies the first and second conditions is X= chokudai, but it coincides with T_1.
Thus, there is no X that satisfies all of the conditions, so -1 should be printed.

Sample Input 2

2 2
choku
dai
chokudai
choku_dai

Sample Output 2

dai_choku

Strings like choku__dai (which has two _'s between choku and dai) also satisfy all of the conditions.

Sample Input 3

2 2
chokudai
atcoder
chokudai_atcoder
atcoder_chokudai

Sample Output 3

-1

chokudai__atcoder and atcoder__chokudai (which have two _'s between chokudai and atcoder) have a length of 17, which violates the second condition.

Sample Input 4

4 4
ab
cd
ef
gh
hoge
fuga
____
_ab_cd_ef_gh_

Sample Output 4

ab__ef___cd_gh

The given T_i may contain a string that cannot be obtained by the procedure described in the first condition.