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

There is a grid with H rows from top to bottom and W columns from left to right. Each square has a piece placed on it or is empty.

The state of the grid is represented by H strings S_1, S_2, \ldots, S_H, each of length W.
If the j-th character of S_i is #, the square at the i-th row from the top and j-th column from the left has a piece on it;
if the j-th character of S_i is ., the square at the i-th row from the top and j-th column from the left is empty.

How many squares in the grid have pieces on them?

Constraints

• 1\leq H,W \leq 10
• H and W are integers.
• S_i is a string of length W consisting of # and ..

Sample Input 1

3 5
#....
.....
.##..

Sample Output 1

3

The following three squares have pieces on them:

• the square at the 1-st row from the top and 1-st column from the left;
• the square at the 3-rd row from the top and 2-nd column from the left;
• the square at the 3-rd row from the top and 3-rd column from the left.

Thus, 3 should be printed.

Sample Input 2

1 10
..........

Sample Output 2

0

Since no square has a piece on it, 0 should be printed.

Sample Input 3

6 5
#.#.#
....#
..##.
####.
..#..
#####

Sample Output 3

16

Problem Statement

Takahashi has an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.
It is guaranteed that A is non-decreasing.

Takahashi performs M operations on this integer sequence. In the i-th operation (1\leq i\leq M), he performs the following operation:

If the sequence A contains B_i as an element, select one such element and delete it. If no such element exists, do nothing.

Note that since A is non-decreasing, the sequence after the operation is uniquely determined regardless of the choice of element, and remains non-decreasing.

Find A after performing M operations.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 1 \leq A_i,B_i \leq 10^9
• The integer sequence A is non-decreasing.
• All input values are integers.

Sample Input 1

8 5
1 2 2 3 3 3 5 6
2 2 7 3 2

Sample Output 1

1 3 3 5 6

Initially, A is A=(1,2,2,3,3,3,5,6).
The operations are performed as follows:

• Delete one 2 from A, and A becomes A=(1,2,3,3,3,5,6) after the operation.
• Delete one 2 from A, and A becomes A=(1,3,3,3,5,6) after the operation.
• Since A does not contain 7 as an element, do nothing. A remains A=(1,3,3,3,5,6) after the operation.
• Delete one 3 from A, and A becomes A=(1,3,3,5,6) after the operation.
• Since A does not contain 2 as an element, do nothing. A remains A=(1,3,3,5,6) after the operation.

Therefore, after all operations, A=(1,3,3,5,6), so output the elements in this order separated by spaces.

Sample Input 2

1 2
1
1 1

Sample Output 2

A becomes empty after the operations, so output nothing.

Problem Statement

You are given a sequence of N positive integers A = (A_1, A_2, \dots ,A_N). Takahashi repeats the following operation until A contains one or fewer positive elements:

• Sort A in descending order. Then, decrease both A_1 and A_2 by 1.

Find the number of times he performs this operation.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• All input values are integers.

Sample Input 1

4
1 2 3 3

Sample Output 1

4

The process goes as follows:

• After the 1st operation, A is (2, 2, 2, 1).
• After the 2nd operation, A is (1, 1, 2, 1).
• After the 3rd operation, A is (1, 0, 1, 1).
• After the 4th operation, A is (0, 0, 1, 0). A no longer contains more than one positive elements, so the process ends here.

Sample Input 2

3
1 1 100

Sample Output 2

2

Problem Statement

2N players, with ID numbers 1 through 2N, will participate in a rock-scissors-paper contest.

The contest has M rounds. Each round has N one-on-one matches, where each player plays in one of them.

For each i=0, 1, \ldots, M, the players' ranks at the end of the i-th round are determined as follows.

• A player with more wins in the first i rounds ranks higher.
• Ties are broken by ID numbers: a player with a smaller ID number ranks higher.

Additionally, for each i=1, \ldots, M, the matches in the i-th round are arranged as follows.

• For each k=1, 2, \ldots, N, a match is played between the players who rank (2k-1)-th and 2k-th at the end of the (i-1)-th round.

In each match, the two players play a hand just once, resulting in one player's win and the other's loss, or a draw.

Takahashi, who can foresee the future, knows that Player i will play A_{i, j} in their match in the j-th round, where A_{i,j} is G, C, or P.
Here, G stands for rock, C stands for scissors, and P stands for paper. (These derive from Japanese.)

Find the players' ranks at the end of the M-th round.

Constraints

• 1 \leq N \leq 50
• 1 \leq M \leq 100
• A_{i,j} is G, C, or P.

Sample Input 1

2 3
GCP
PPP
CCC
PPC

Sample Output 1

3
1
2
4

In the first round, matches are played between Players 1 and 2, and between Players 3 and 4. Player 2 wins the former, and Player 3 wins the latter.
In the second round, matches are played between Players 2 and 3, and between Players 1 and 4. Player 3 wins the former, and Player 1 wins the latter.
In the third round, matches are played between Players 3 and 1, and between Players 2 and 4. Player 3 wins the former, and Player 4 wins the latter.
Therefore, in the end, the players are ranked in the following order: 3,1,2,4, from highest to lowest.

Sample Input 2

2 2
GC
PG
CG
PP

Sample Output 2

1
2
3
4

In the first round, matches are played between Players 1 and 2, and between Players 3 and 4. Player 2 wins the former, and Player 3 wins the latter.
In the second round, matches are played between Players 2 and 3, and between Players 1 and 4. The former is drawn, and Player 1 wins the latter.
Therefore, in the end, the players are ranked in the following order: 1,2,3,4, from highest to lowest.

Problem Statement

You are given a simple undirected graph with N vertices and M edges, where the vertices are labeled 1 to N. The i-th edge connects vertices u_i and v_i.
What is the minimum number of edges that need to be deleted from this graph so that the graph becomes a forest?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min \left( \frac{N(N-1)}{2}, 2 \times 10^5\right)
• 1 \leq u_i < v_i \leq N
• The given graph is simple.
• All input values are integers.

Sample Input 1

4 4
1 2
1 3
2 4
3 4

Sample Output 1

1

For example, if you delete the first edge, the graph becomes a forest.

Sample Input 2

5 0

Sample Output 2

0

Sample Input 3

10 10
7 9
4 6
6 10
2 5
5 6
5 9
6 8
4 8
1 5
1 4

Sample Output 3

2

Problem Statement

For real numbers L and R, let us denote by [L,R) the set of real numbers greater than or equal to L and less than R. Such a set is called a right half-open interval.

You are given N right half-open intervals [L_i,R_i). Let S be their union. Represent S as a union of the minimum number of right half-open intervals.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq L_i \lt R_i \leq 2\times 10^5
• All values in input are integers.

Sample Input 1

3
10 20
20 30
40 50

Sample Output 1

10 30
40 50

The union of the three right half-open intervals [10,20),[20,30),[40,50) equals the union of two right half-open intervals [10,30),[40,50).

Sample Input 2

3
10 40
30 60
20 50

Sample Output 2

10 60

The union of the three right half-open intervals [10,40),[30,60),[20,50) equals the union of one right half-open interval [10,60).

Problem Statement

AtCoder Ski Area has N open spaces called Space 1, Space 2, \ldots, Space N. The altitude of Space i is H_i. There are M slopes that connect two spaces bidirectionally. The i-th slope (1 \leq i \leq M) connects Space U_i and Space V_i. It is possible to travel between any two spaces using some slopes.

Takahashi can only travel between spaces by using slopes. Each time he goes through a slope, his happiness changes. Specifically, when he goes from Space X to Space Y by using the slope that directly connects them, his happiness changes as follows.

• If the altitude of Space X is strictly higher than that of Space Y, the happiness increases by their difference: H_X-H_Y.
• If the altitude of Space X is strictly lower than that of Space Y, the happiness decreases by their difference multiplied by 2: 2(H_Y-H_X).
• If the altitude of Space X is equal to that of Space Y, the happiness does not change.

The happiness may be a negative value.

Initially, Takahashi is in Space 1, and his happiness is 0. Find his maximum possible happiness after going through any number of slopes (possibly zero), ending in any space.

Constraints

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq \min( 2\times 10^5,\frac{N(N-1)}{2})
• 0 \leq H_i\leq 10^8 (1 \leq i \leq N)
• 1 \leq U_i < V_i \leq N (1 \leq i \leq M)
• (U_i,V_i) \neq (U_j, V_j) if i \neq j.
• All values in input are integers.
• It is possible to travel between any two spaces using some slopes.

Sample Input 1

4 4
10 8 12 5
1 2
1 3
2 3
3 4

Sample Output 1

3

If Takahashi takes the route Space 1 \to Space 3 \to Space 4, his happiness changes as follows.

• When going from Space 1 (altitude 10) to Space 3 (altitude 12), it decreases by 2\times (12-10)=4 and becomes 0-4=-4.
• When going from Space 3 (altitude 12) to Space 4 (altitude 5), it increases by 12-5=7 and becomes -4+7=3.

If he ends the travel here, the final happiness will be 3, which is the maximum possible value.

Sample Input 2

2 1
0 10
1 2

Sample Output 2

0

His happiness is maximized by not moving at all.

Problem Statement

You are given an N \times M grid. Each cell contains either . or #.
The information about the symbols written in the cells is given as N strings S_1,S_2,\dots,S_N, where the same symbol as the j-th character of S_i is written in the cell at the i-th row from the top and j-th column from the left.
How many rectangular regions consisting of at most K cells have all cells containing .?

Formally, count the number of integer tuples (l_x,r_x,l_y,r_y) that satisfy the following conditions:

• 1 \le l_x \le r_x \le N
• 1 \le l_y \le r_y \le M
• (r_x-l_x+1) \times (r_y-l_y+1) \le K
• For all integer pairs (i,j) satisfying l_x \le i \le r_x and l_y \le j \le r_y, the cell at the i-th row from the top and j-th column from the left contains ..

Constraints

• N, M, and K are integers.
• 1 \le N,M \le 5 \times 10^5
• 1 \le N \times M \le 5 \times 10^6
• 1 \le K \le N \times M
• S_i is a string of length M consisting of . and #.

Sample Input 1

3 3 4
#..
...
..#

Sample Output 1

19

The rectangular regions to count are the following 19:

• A rectangular region represented by (l_x,r_x,l_y,r_y) = (1,2,2,3)
• A rectangular region represented by (l_x,r_x,l_y,r_y) = (2,3,1,2)
• A rectangular region represented by (l_x,r_x,l_y,r_y) = (2,2,1,3)
• A rectangular region represented by (l_x,r_x,l_y,r_y) = (1,3,2,2)
• 4 rectangular regions of 1 row and 2 columns consisting only of .
• 4 rectangular regions of 2 rows and 1 column consisting only of .
• 7 rectangular regions of 1 row and 1 column consisting only of .

Sample Input 2

7 5 35
.....
.....
.....
.....
.....
.....
.....

Sample Output 2

420

Sample Input 3

10 9 25
#.....#..
....#....
.......#.
.........
.......#.
.#.......
.........
#........
........#
.#.....#.

Sample Output 3

984