Problem Statement

AtCoder currently holds four series of regular contests: ABC, ARC, AGC, and AHC.

What is the series of regular contests currently held by AtCoder in addition to S_1, S_2, and S_3?

Constraints

• Each of S_1, S_2, and S_3 is ABC, ARC, AGC, or AHC.
• S_1, S_2, and S_3 are pairwise different.

Sample Input 1

ARC
AGC
AHC

Sample Output 1

ABC

Given in input are ARC, AGC, and AHC. The rest is ABC.

Sample Input 2

AGC
ABC
ARC

Sample Output 2

AHC

Problem Statement

There are N people numbered 1 to N.
You are given their schedule for the following D days. The schedule for person i is represented by a string S_i of length D. If the j-th character of S_i is o, person i is free on the j-th day; if it is x, they are occupied that day.

From these D days, consider choosing some consecutive days when all the people are free.
How many days can be chosen at most? If no day can be chosen, report 0.

Constraints

• 1 \leq N \leq 100
• 1 \leq D \leq 100
• N and D are integers.
• S_i is a string of length D consisting of o and x.

Sample Input 1

3 5
xooox
oooxx
oooxo

Sample Output 1

2

All the people are free on the second and third days, so we can choose them.
Choosing these two days will maximize the number of days among all possible choices.

Sample Input 2

3 3
oxo
oxo
oxo

Sample Output 2

1

Note that the chosen days must be consecutive. (All the people are free on the first and third days, so we can choose either of them, but not both.)

Sample Input 3

3 3
oox
oxo
xoo

Sample Output 3

0

Print 0 if no day can be chosen.

Sample Input 4

1 7
ooooooo

Sample Output 4

7

Sample Input 5

5 15
oxooooooooooooo
oxooxooooooooox
oxoooooooooooox
oxxxooooooxooox
oxooooooooxooox

Sample Output 5

5

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N and a positive integer K.

Find the sum of the integers between 1 and K, inclusive, that do not appear in the sequence A.

Constraints

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

Sample Input 1

4 5
1 6 3 1

Sample Output 1

11

Among the integers between 1 and 5, three numbers, 2, 4, and 5, do not appear in A.

Thus, print their sum: 2+4+5=11.

Sample Input 2

1 3
346

Sample Output 2

6

Sample Input 3

10 158260522
877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739

Sample Output 3

12523196466007058

Problem Statement

The programming contest World Tour Finals is underway, where N players are participating, and half of the competition time has passed. There are M problems in this contest, and the score A_i of problem i is a multiple of 100 between 500 and 2500, inclusive.

For each i = 1, \ldots, N, you are given a string S_i that indicates which problems player i has already solved. S_i is a string of length M consisting of o and x, where the j-th character of S_i is o if player i has already solved problem j, and x if they have not yet solved it. Here, none of the players have solved all the problems yet.

The total score of player i is calculated as the sum of the scores of the problems they have solved, plus a bonus score of i points.
For each i = 1, \ldots, N, answer the following question.

• At least how many of the problems that player i has not yet solved must player i solve to exceed all other players' current total scores?

Note that under the conditions in this statement and the constraints, it can be proved that player i can exceed all other players' current total scores by solving all the problems, so the answer is always defined.

Constraints

• 2\leq N\leq 100
• 1\leq M\leq 100
• 500\leq A_i\leq 2500
• A_i is a multiple of 100.
• S_i is a string of length M consisting of o and x.
• S_i contains at least one x.
• All numeric values in the input are integers.

Sample Input 1

3 4
1000 500 700 2000
xxxo
ooxx
oxox

Sample Output 1

0
1
1

The players' total scores at the halfway point of the competition time are 2001 points for player 1, 1502 points for player 2, and 1703 points for player 3.

Player 1 is already ahead of all other players' total scores without solving any more problems.

Player 2 can, for example, solve problem 4 to have a total score of 3502 points, which would exceed all other players' total scores.

Player 3 can also, for example, solve problem 4 to have a total score of 3703 points, which would exceed all other players' total scores.

Sample Input 2

5 5
1000 1500 2000 2000 2500
xxxxx
oxxxx
xxxxx
oxxxx
oxxxx

Sample Output 2

1
1
1
1
0

Sample Input 3

7 8
500 500 500 500 500 500 500 500
xxxxxxxx
oxxxxxxx
ooxxxxxx
oooxxxxx
ooooxxxx
oooooxxx
ooooooxx

Sample Output 3

7
6
5
4
3
2
0

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.