Problem Statement

Takahashi measured his body temperature and found it to be X {}^\circC.

Body temperature is classified into the following:

• Higher than or equal to 38.0 {}^\circC: “High fever”
• Higher than or equal to 37.5 {}^\circC and lower than 38.0 {}^\circC: “Fever”
• Lower than 37.5 {}^\circC: “Normal”

Which classification does Takahashi's body temperature fall into? Present the answer as an integer according to the Output section.

Constraints

• 30 \leq X \leq 50
• X is given to one decimal place.

Sample Input 1

40.0

Sample Output 1

1

His body temperature is 40.0 {}^\circC, which is classified as a high fever. Thus, print 1.

Sample Input 2

37.7

Sample Output 2

2

His body temperature is 37.7 {}^\circC, which is classified as a fever. Thus, print 2.

Sample Input 3

36.6

Sample Output 3

3

His body temperature is 36.6 {}^\circC, which is classified as a normal temperature. Thus, print 3.

Problem Statement

You are given an integer N between 1 and 9, inclusive, as input.

Concatenate N copies of the digit N and print the resulting string.

Constraints

• N is an integer between 1 and 9, inclusive.

Sample Input 1

3

Sample Output 1

333

Concatenate three copies of the digit 3 to yield the string 333.

Sample Input 2

9

Sample Output 2

999999999

Problem Statement

N players played a round-robin tournament.

You are given an N-by-N table A containing the results of the matches. Let A_{i,j} denote the element at the i-th row and j-th column of A.
A_{i,j} is - if i=j, and W, L, or D otherwise.
A_{i,j} is W if Player i beat Player j, L if Player i lost to Player j, and D if Player i drew with Player j.

Determine whether the given table is contradictory.

The table is said to be contradictory when some of the following holds:

• There is a pair (i,j) such that Player i beat Player j, but Player j did not lose to Player i;
• There is a pair (i,j) such that Player i lost to Player j, but Player j did not beat Player i;
• There is a pair (i,j) such that Player i drew with Player j, but Player j did not draw with Player i.

Constraints

• 2 \leq N \leq 1000
• A_{i,i} is -.
• A_{i,j} is W, L, or D, for i\neq j.

Sample Input 1

4
-WWW
L-DD
LD-W
LDW-

Sample Output 1

incorrect

Player 3 beat Player 4, while Player 4 also beat Player 3, which is contradictory.

Sample Input 2

2
-D
D-

Sample Output 2

correct

There is no contradiction.

Problem Statement

You are given a horizontally written text. Convert it to vertical writing, filling spaces with *.

You are given N strings S_1, S_2, \dots, S_N consisting of lowercase English letters. Let M be the maximum length of these strings.

Print M strings T_1, T_2, \dots, T_M that satisfy the following conditions:

• Each T_i consists of lowercase English letters and *.
• Each T_i does not end with *.
• For each 1 \leq i \leq N, the following holds:
  • For each 1 \leq j \leq |S_i|, the (N-i+1)-th character of T_j exists, and the concatenation of the (N-i+1)-th characters of T_1, T_2, \dots, T_{|S_i|} in this order equals S_i.
  • For each |S_i| + 1 \leq j \leq M, the (N-i+1)-th character of T_j either does not exist or is *.

Here, |S_i| denotes the length of the string S_i.

Constraints

• N is an integer between 1 and 100, inclusive.
• Each S_i is a string of lowercase English letters with length between 1 and 100, inclusive.

Sample Input 1

3
abc
de
fghi

Sample Output 1

fda
geb
h*c
i

Placing * as the 2nd character of T_3 puts the c in the correct position. On the other hand, placing * as the 2nd and 3rd characters of T_4 would make T_4 end with *, which violates the condition.

Sample Input 2

3
atcoder
beginner
contest

Sample Output 2

cba
oet
ngc
tio
end
sne
ter
*r

Problem Statement

As KEYENCE headquarters have more and more workers, they decided to divide the departments in the headquarters into two groups and stagger their lunch breaks.

KEYENCE headquarters have N departments, and the number of people in the i-th department (1\leq i\leq N) is K_i.

When assigning each department to Group A or Group B, having each group take lunch breaks at the same time, and ensuring that the lunch break times of Group A and Group B do not overlap, find the minimum possible value of the maximum number of people taking a lunch break at the same time.
In other words, find the minimum possible value of the larger of the following: the total number of people in departments assigned to Group A, and the total number of people in departments assigned to Group B.

Constraints

• 2 \leq N \leq 20
• 1 \leq K_i \leq 10^8
• All input values are integers.

Sample Input 1

5
2 3 5 10 12

Sample Output 1

17

When assigning departments 1, 2, and 5 to Group A, and departments 3 and 4 to Group B, Group A has a total of 2+3+12=17 people, and Group B has a total of 5+10=15 people. Thus, the maximum number of people taking a lunch break at the same time is 17.

It is impossible to assign the departments so that both groups have 16 or fewer people, so print 17.

Sample Input 2

2
1 1

Sample Output 2

1

Multiple departments may have the same number of people.

Sample Input 3

6
22 25 26 45 22 31

Sample Output 3

89

For example, when assigning departments 1, 4, and 5 to Group A, and departments 2, 3, and 6 to Group B, the maximum number of people taking a lunch break at the same time is 89.