Problem Statement

Keyence has a culture of addressing everyone with the honorific "san," regardless of their role, age, or position. Even a new employee would call the president "Nakata-san." [Translator's note: this is a bit unusual in Japan.]

You are given a person's surname and first name as strings S and T, respectively.

Print the concatenation of the surname, a space ( ), and the honorific (san) in this order.

Constraints

• Each of S and T is a string that satisfies the following conditions.
  • The length is between 1 and 10, inclusive.
  • The first character is an uppercase English letter.
  • All characters except the first one are lowercase English letters.

Sample Input 1

Takahashi Chokudai

Sample Output 1

Takahashi san

Print the concatenation of the surname (Takahashi), a space ( ), and the honorific (san) in this order.

Sample Input 2

K Eyence

Sample Output 2

K san

Problem Statement

The following five days are called the five seasonal festivals (gosekku).

• January \color{red}{\mathbf{7}}
• March 3
• May 5
• July 7
• September 9

If month M, day D is one of the five seasonal festivals, output Yes; otherwise, output No.

Constraints

• M and D are integers.
• Month M, day D is a valid date in a leap year in the Gregorian calendar.

Sample Input 1

3 3

Sample Output 1

Yes

March 3 is one of the five seasonal festivals, so output Yes.

Sample Input 2

1 1

Sample Output 2

No

January 1 is not one of the five seasonal festivals, so output No.

Sample Input 3

4 4

Sample Output 3

No

Sample Input 4

11 7

Sample Output 4

No

Problem Statement

There are N countries numbered 1 to N. For each i = 1, 2, \ldots, N, Takahashi has A_i units of the currency of country i.

Takahashi can repeat the following operation any number of times, possibly zero:

• First, choose an integer i between 1 and N-1, inclusive.
• Then, if Takahashi has at least S_i units of the currency of country i, he performs the following action once:
  • Pay S_i units of the currency of country i and gain T_i units of the currency of country (i+1).

Print the maximum possible number of units of the currency of country N that Takahashi could have in the end.

Constraints

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

Sample Input 1

4
5 7 0 3
2 2
4 3
5 2

Sample Output 1

5

In the following explanation, let the sequence A = (A_1, A_2, A_3, A_4) represent the numbers of units of the currencies of the countries Takahashi has. Initially, A = (5, 7, 0, 3).

Consider performing the operation four times as follows:

• Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (5, 3, 3, 3).
• Choose i = 1, pay two units of the currency of country 1, and gain two units of the currency of country 2. Now, A = (3, 5, 3, 3).
• Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (3, 1, 6, 3).
• Choose i = 3, pay five units of the currency of country 3, and gain two units of the currency of country 4. Now, A = (3, 1, 1, 5).

At this point, Takahashi has five units of the currency of country 4, which is the maximum possible number.

Sample Input 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

Sample Output 2

45

Problem Statement

This problem shares a similar setting with Problem A. The way Takahashi chooses cookies and what you are required to find are different from Problem A.

There are N boxes arranged in a row, and some of these boxes contain cookies.

The state of these boxes is represented by a string S of length N. Specifically, the i-th box (1\leq i \leq N) from the left contains one cookie if the i-th character of S is @, and is empty if it is ..

Over the next D days, Takahashi will choose and eat one cookie per day from among the cookies in these boxes. On each day, he chooses the cookie in the rightmost box that contains a cookie at that point.

Determine, for each of the N boxes, whether it will contain a cookie after D days have passed.

It is guaranteed that S contains at least D occurrences of @.

Constraints

• 1 \leq D \leq N \leq 100
• N and D are integers.
• S is a string of length N consisting of @ and ..
• S contains at least D occurrences of @.

Sample Input 1

5 2
.@@.@

Sample Output 1

.@...

Takahashi acts as follows:

• Day 1: There are cookies in the 2nd, 3rd, and 5th boxes from the left. Among these, the rightmost is the 5th box. He eats the cookie in this box.
• Day 2: There are cookies in the 2nd and 3rd boxes. Among these, the rightmost is the 3rd box. He eats the cookie in this box.
• After two days have passed, only the 2nd box from the left contains a cookie.

Therefore, the correct output is .@....

Sample Input 2

3 3
@@@

Sample Output 2

...

Sample Input 3

10 4
@@@.@@.@@.

Sample Output 3

@@@.......

Problem Statement

There is a grid with H rows and W columns.
The cell at the i-th row from the top and j-th column from the left is painted black if S_{i,j} is #, and white if S_{i,j} is ..

Among the four-directionally connected regions consisting of white cells, find the number of those that are surrounded by black cells.

Below is a more formal statement.

We denote the cell at the i-th row from the top and j-th column from the left as cell (i, j).
Two cells (i, j) and (i', j') are said to be adjacent if and only if |i-i'|+|j-j'|=1.
A set C of white cells is said to be connected if and only if, for any two cells c and c' in C, it is possible to move from c to c' by repeatedly moving to an adjacent cell in C.
A non-empty connected set of white cells that is maximal is called a connected component of white cells.
Find the number of connected components of white cells that do not contain any cell on the outermost border of the grid (that is, in row 1, row H, column 1, or column W).

Constraints

• 3 \leq H, W \leq 10^3
• H and W are integers.
• S_{i,j} is # or ..

Sample Input 1

5 15
##########..###
#...#######.###
####....###..##
######.########
########....###

Sample Output 1

2

There are two such regions: the region consisting of the three cells in row 2 from the top and columns 2, 3, 4 from the left, and the region consisting of a total of five cells: columns 5, 6, 7, 8 from the left in row 3 from the top and column 7 from the left in row 4 from the top.

Sample Input 2

10 22
######################
####.#################
###...################
##.###.##.....########
##.....##.####.#######
.######.#......#.....#
.######.#.####.#.#####
#########.....##.#####
################.#####
################.....#

Sample Output 2

4