Problem Statement

You are given a string S ending with er or ist.
If S ends with er, print er; if it ends with ist, print ist.

Constraints

• 2 \le |S| \le 20
• S consists of lowercase English letters.
• S ends with er or ist.

Sample Input 1

atcoder

Sample Output 1

er

S="atcoder" ends with er.

Sample Input 2

tourist

Sample Output 2

ist

Sample Input 3

er

Sample Output 3

er

Problem Statement

We have a grid with H horizontal rows and W vertical columns, where each square contains an integer. The integer written on the square at the i-th row from the top and j-th column from the left is A_{i, j}.

Determine whether the grid satisfies the condition below.

A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds for every quadruple of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W.

Constraints

• 2 \leq H, W \leq 50
• 1 \leq A_{i, j} \leq 10^9
• All values in input are integers.

Sample Input 1

3 3
2 1 4
3 1 3
6 4 1

Sample Output 1

Yes

There are nine quadruples of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W. For all of them, A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds. Some examples follow.

• For (i_1, i_2, j_1, j_2) = (1, 2, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 2, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 2, 2, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 3, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 3, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.

We can also see that the property holds for the other quadruples: (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3).
Thus, we should print Yes.

Sample Input 2

2 4
4 3 2 1
5 6 7 8

Sample Output 2

No

We should print No because the condition is not satisfied.
This is because, for example, we have A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} for (i_1, i_2, j_1, j_2) = (1, 2, 1, 4).

Problem Statement

In the xy-plane, we have N points numbered 1 through N.
Point i is at the coordinates (X_i,Y_i). Any two different points are at different positions.
Find the number of ways to choose three of these N points so that connecting the chosen points with segments results in a triangle with a positive area.

Constraints

• All values in input are integers.
• 3 \le N \le 300
• -10^9 \le X_i,Y_i \le 10^9
• (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.

Sample Input 1

4
0 1
1 3
1 1
-1 -1

Sample Output 1

3

The figure below illustrates the points.

There are three ways to choose points that form a triangle: \{1,2,3\},\{1,3,4\},\{2,3,4\}.

Sample Input 2

20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0

Sample Output 2

1124

Problem Statement

Takahashi found a puzzle along some road.
It is composed of an undirected graph with nine vertices and M edges, and eight pieces.

The nine vertices of the graph are called Vertex 1, Vertex 2, \ldots, Vertex 9. For each i = 1, 2, \ldots, M, the i-th edge connects Vertex u_i and Vertex v_i.
The eight pieces are called Piece 1, Piece 2, \ldots, Piece 8. For each j = 1, 2, \ldots, 8, Piece j is on Vertex p_j.
Here, it is guaranteed that all pieces are on distinct vertices. Note that there is exactly one empty vertex without a piece.

Takahashi can do the following operation on the puzzle any number of times (possibly zero).

Choose a piece on a vertex adjacent to the empty vertex, and move it to the empty vertex.

By repeating this operation, he aims to complete the puzzle. The puzzle is considered complete when the following holds.

• For each j = 1, 2, \ldots, 8, Piece j is on Vertex j.

Determine whether it is possible for Takahashi to complete the puzzle. If it is possible, find the minimum number of operations needed to do so.

Constraints

• 0 \leq M \leq 36
• 1 \leq u_i, v_i \leq 9
• The given graph has no multi-edges or self-loops.
• 1 \leq p_j \leq 9
• j \neq j' \Rightarrow p_j \neq p_{j'}
• All values in input are integers.

Sample Input 1

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

Sample Output 1

5

The following procedure completes the puzzle in five operations.

1. Move Piece 2 from Vertex 9 to Vertex 1.
2. Move Piece 3 from Vertex 2 to Vertex 9.
3. Move Piece 2 from Vertex 1 to Vertex 2.
4. Move Piece 1 from Vertex 3 to Vertex 1.
5. Move Piece 3 from Vertex 9 to Vertex 3.

On the other hand, it is impossible to complete the puzzle in less than five operations. Thus, we should print 5.
Note that the given graph may not be connected.

Sample Input 2

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

Sample Output 2

0

The puzzle is already complete from the beginning. Thus, the minimum number of operations needed to complete the puzzle is 0.

Sample Input 3

12
8 5
9 6
4 5
4 1
2 5
8 9
2 1
3 6
8 7
6 5
7 4
2 3
1 2 3 4 5 6 8 7

Sample Output 3

-1

No sequence of operations can complete the puzzle, so we should print -1.

Sample Input 4

12
6 5
5 4
4 1
4 7
8 5
2 1
2 5
6 9
3 6
9 8
8 7
3 2
2 3 4 6 1 9 7 8

Sample Output 4

16

Problem Statement

We have a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

Each square contains an integer. For each i = 1, 2, \ldots, N, the square (r_i, c_i) contains a positive integer a_i. The other square contains a 0.

Initially, there is a piece on the square (R, C). Takahashi can move the piece to a square other than the square it occupies now, any number of times. However, when moving the piece, both of the following conditions must be satisfied.

• The integer written on the square to which the piece is moved is strictly greater than the integer written on the square from which the piece is moved.
• The squares to and from which the piece is moved are in the same row or the same column.

For each i = 1, 2, \ldots, N, print the maximum number of times Takahashi can move the piece when (R, C) = (r_i, c_i).

Constraints

• 2 \leq H, W \leq 2 \times 10^5
• 1 \leq N \leq \min(2 \times 10^5, HW)
• 1 \leq r_i \leq H
• 1 \leq c_i \leq W
• 1 \leq a_i \leq 10^9
• i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)
• All values in input are integers.

Sample Input 1

3 3 7
1 1 4
1 2 7
2 1 3
2 3 5
3 1 2
3 2 5
3 3 5

Sample Output 1

1
0
2
0
3
1
0

The grid contains the following integers.

4 7 0
3 0 5
2 5 5

• When (R, C) = (r_1, c_1) = (1, 1), you can move the piece once by moving it as (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_2, c_2) = (1, 2), you cannot move the piece at all.
• When (R, C) = (r_3, c_3) = (2, 1), you can move the piece twice by moving it as (2, 1) \rightarrow (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_4, c_4) = (2, 3), you cannot move the piece at all.
• When (R, C) = (r_5, c_5) = (3, 1), you can move the piece three times by moving it as (3, 1) \rightarrow (2, 1) \rightarrow (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_6, c_6) = (3, 2), you can move the piece once by moving it as (3, 2) \rightarrow (1, 2).
• When (R, C) = (r_7, c_7) = (3, 3), you cannot move the piece at all.

Sample Input 2

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

Sample Output 2

2
4
1
5
3
6
6
2
7
0
0
4
1
5
3
0
5
2
4
0

Problem Statement

Given is a string S consisting of digits from 1 through 9.
From this string S, let us make a formula T by the following operations.

• Initially, let T=S.
• Choose a (possibly empty) set A of different integers where each element is between 1 and |S|-1 (inclusive).
• For each element x in descending order, do the following.
  • Insert a + between the x-th and (x+1)-th characters of T.

For example, when S= 1234 and A= \lbrace 2,3 \rbrace, we will have T= 12+3+4.

Consider evaluating all possible formulae T obtained by these operations. Find the sum, modulo 998244353, of the evaluations.

Constraints

• 1 \le |S| \le 2 \times 10^5
• S consists of 1, 2, 3, 4, 5, 6, 7, 8, and 9.

Sample Input 1

1234

Sample Output 1

1736

There are eight formulae that can be obtained as T: 1234, 123+4, 12+34, 12+3+4, 1+234, 1+23+4, 1+2+34, and 1+2+3+4.
The sum of the evaluations of these formulae is 1736.

Sample Input 2

1

Sample Output 2

1

S may have a length of 1, in which case the only possible choice for A is the empty set.

Sample Input 3

31415926535897932384626433832795

Sample Output 3

85607943

Be sure to find the sum modulo 998244353.

Problem Statement

We have a N-face die (singular of dice) that shows integers from 1 through N with equal probability.
Below, the die is said to be showing an integer X when it is placed so that the top face is the face with the integer X.
Initially, the die shows the integer S.

You can do the following two operations on this die any number (possibly zero) of times in any order.

• Pay A yen (the Japanese currency) to "increase" the value shown by the die by 1, that is, reposition it to show X+1 when it currently shows X. This operation cannot be done when the die shows N.
• Pay B yen to recast the die, after which it will show an integer between 1 and N with equal probability.

Consider making the die show T from the initial state where it shows S.
Print the minimum expected value of the cost required to do so when the optimal strategy is used to minimize this expected value.

Constraints

• 1 \leq N \leq 10^9
• 1 \leq S, T \leq N
• 1 \leq A, B \leq 10^9
• All values in input are integers.

Sample Input 1

5 2 4 10 4

Sample Output 1

15.0000000000000000

When the optimal strategy is used to minimize the expected cost, it will be 15 yen.

Sample Input 2

10 6 6 1 2

Sample Output 2

0.0000000000000000

The die already shows T in the initial state, which means no operation is needed.

Sample Input 3

1000000000 1000000000 1 1000000000 1000000000

Sample Output 3

1000000000000000000.0000000000000000

Your output will be considered correct when its absolute or relative error is at most 10^{-5}.

Problem Statement

We have a bipartite graph with L vertices to the left and R vertices to the right.
Takahashi will install surveillance cameras in these vertices.
Installing cameras incurs the following cost.

• A_i yen (the Japanese currency) for each camera installed in the i-th (1 \le i \le L) vertex to the left;
• B_j yen (the Japanese currency) for each camera installed in the j-th (1 \le j \le R) vertex to the right.

It is allowed to install multiple cameras on the same vertex.

Find the minimum amount of money needed to install cameras to satisfy the following condition.

• For every pair of integers (i, j) such that 1 \le i \le L, 1 \le j \le R, there is a total of C_{i,j} or more cameras installed in the i-th vertex to the left and j-th vertex to the right.

Constraints

• All values in input are integers.
• 1 \le L,R \le 100
• 1 \le A_i,B_i \le 10
• 0 \le C_{i,j} \le 100

Sample Input 1

3 4
4 3 6
5 2 3 4
1 2 3 2
2 1 2 3
3 2 1 2

Sample Output 1

37

You can achieve the objective for 37 yen as follows, which is the minimum amount required.

• Install 2 cameras on the 1-st vertex in the left.
• Install 3 cameras on the 2-nd vertex in the left.
• Install 2 cameras on the 3-rd vertex in the left.
• Install 1 camera on the 1-st vertex in the right.
• Install 1 camera on the 3-rd vertex in the right.

Sample Input 2

1 1
10
10
0

Sample Output 2

0

No camera may be needed.

Sample Input 3

5 6
3 2 6 7 5
4 9 8 6 2 3
2 0 2 1 1 0
2 3 2 1 0 0
2 2 4 0 2 2
4 1 0 3 0 2
1 0 0 2 2 5

Sample Output 3

79