Problem Statement

Takahashi came to a store to buy a pen. Here, a red pen costs R yen, a green pen costs G yen, and a blue pen costs B yen.

Takahashi dislikes the color C. If C is Red, he cannot buy a red pen; if C is Green, he cannot buy a green pen; and if C is Blue, he cannot buy a blue pen.

Determine the minimum amount of money he needs to buy one pen.

Constraints

• 1\leq R,G,B\leq 100
• R, G, and B are integers.
• C is Red, Green, or Blue.

Sample Input 1

20 30 10
Blue

Sample Output 1

20

A red pen costs 20 yen, a green pen costs 30 yen, and a blue pen costs 10 yen. Takahashi cannot buy a blue pen, but he can buy a red pen for 20 yen.

Sample Input 2

100 100 100
Red

Sample Output 2

100

Sample Input 3

37 39 93
Blue

Sample Output 3

37

Problem Statement

In the xy-plane, there are three points A(x_A, y_A), B(x_B, y_B), and C(x_C, y_C) that are not collinear. Determine whether the triangle ABC is a right triangle.

Constraints

• -1000 \leq x_A, y_A, x_B, y_B, x_C, y_C \leq 1000
• The three points A, B, and C are not collinear.
• All input values are integers.

Sample Input 1

0 0
4 0
0 3

Sample Output 1

Yes

The triangle ABC is a right triangle.

Sample Input 2

-4 3
2 1
3 4

Sample Output 2

Yes

The triangle ABC is a right triangle.

Sample Input 3

2 4
-3 2
1 -2

Sample Output 3

No

The triangle ABC is not a right triangle.

Problem Statement

You are given N pairs of integers (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N).

Determine whether there exists a sequence of N integers X = (X_1, X_2, \ldots, X_N) that satisfies the following conditions, and print one such sequence if it exists.

• L_i \leq X_i \leq R_i for each i = 1, 2, \ldots, N.
• \displaystyle \sum_{i=1}^N X_i = 0.

Constraints

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

Sample Input 1

3
3 5
-4 1
-2 3

Sample Output 1

Yes
4 -3 -1

The sequence X = (4, -3, -1) satisfies all the conditions. Other valid sequences include (3, -3, 0) and (5, -4, -1).

Sample Input 2

3
1 2
1 2
1 2

Sample Output 2

No

No sequence X satisfies the conditions.

Sample Input 3

6
-87 12
-60 -54
2 38
-76 6
87 96
-17 38

Sample Output 3

Yes
-66 -57 31 -6 89 9

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges. Each vertex i\,(1\leq i \leq N) has a weight A_i. Each edge j\,(1\leq j \leq M) connects vertices U_j and V_j bidirectionally and has a weight B_j.

The weight of a path in this graph is defined as the sum of the weights of the vertices and edges that appear on the path.

For each i=2,3,\dots,N, solve the following problem:

• Find the minimum weight of a path from vertex 1 to vertex i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq U_j < V_j \leq N
• (U_i, V_i) \neq (U_j, V_j) if i \neq j.
• The graph is connected.
• 0 \leq A_i \leq 10^9
• 0 \leq B_j \leq 10^9
• All input values are integers.

Sample Input 1

3 3
1 2 3
1 2 1
1 3 6
2 3 2

Sample Output 1

4 9

Consider the paths from vertex 1 to vertex 2. The weight of the path 1 \to 2 is A_1 + B_1 + A_2 = 1 + 1 + 2 = 4, and the weight of the path 1 \to 3 \to 2 is A_1 + B_2 + A_3 + B_3 + A_2 = 1 + 6 + 3 + 2 + 2 = 14. The minimum weight is 4.

Consider the paths from vertex 1 to vertex 3. The weight of the path 1 \to 3 is A_1 + B_2 + A_3 = 1 + 6 + 3 = 10, and the weight of the path 1 \to 2 \to 3 is A_1 + B_1 + A_2 + B_3 + A_3 = 1 + 1 + 2 + 2 + 3 = 9. The minimum weight is 9.

Sample Input 2

2 1
0 1
1 2 3

Sample Output 2

4

Sample Input 3

5 8
928448202 994752369 906965437 942744902 907560126
2 5 975090662
1 2 908843627
1 5 969061140
3 4 964249326
2 3 957690728
2 4 942986477
4 5 948404113
1 3 988716403

Sample Output 3

2832044198 2824130042 4696218483 2805069468

Note that the answers may not fit in a 32-bit integer.

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N. For each k = 1, 2, \dots, N, find the number, modulo 998244353, of (not necessarily contiguous) subsequences of A of length k that are arithmetic sequences. Two subsequences are distinguished if they are taken from different positions, even if they are equal as sequences.

Constraints

• 1 \leq N \leq 80
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

5
1 2 3 2 3

Sample Output 1

5 10 3 0 0

• There are 5 subsequences of length 1, all of which are arithmetic sequences.
• There are 10 subsequences of length 2, all of which are arithmetic sequences.
• There are 3 subsequences of length 3 that are arithmetic sequences: (A_1, A_2, A_3), (A_1, A_2, A_5), and (A_1, A_4, A_5).
• There are no arithmetic subsequences of length 4 or more.

Sample Input 2

4
1 2 3 4

Sample Output 2

4 6 2 1

Sample Input 3

1
100

Sample Output 3

1

Problem Statement

You are given a tree T with N vertices. The vertices are numbered 1 to N, and the i-th edge (1 \leq i \leq N-1) connects vertices u_i and v_i bidirectionally.

Using T, define a complete graph G with N vertices as follows:

• The weight w(x,y) of the edge between vertices x and y in G is the shortest distance between vertices x and y in T.

Find one maximum weight maximum matching in G. That is, find a set of \lfloor N/2 \rfloor pairs of vertices M=\{(x_1,y_1),(x_2,y_2),\dots,(x_{\lfloor N/2 \rfloor},y_{\lfloor N/2 \rfloor})\} such that each vertex 1,2,\dots, N appears in M at most once, and \displaystyle \sum_{i=1}^{\lfloor N/2 \rfloor} w(x_i,y_i) is maximized.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq u_i < v_i \leq N
• The input graph is a tree.
• All input values are integers.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

2 4
1 3

In T, the distance between vertices 2 and 4 is 2, and the distance between vertices 1 and 3 is 2, so the weight of the matching \{(2,4),(1,3)\} is 4. There is no matching with a weight greater than 4, so this is a maximum weight maximum matching. Other acceptable outputs include:

2 3
1 4

Sample Input 2

3
1 2
2 3

Sample Output 2

1 3

In T, the distance between vertices 1 and 3 is 2, so the weight of the matching \{(1,3)\} is 2. There is no matching with a weight greater than 2, so this is a maximum weight maximum matching. Another acceptable output is:

3 1

Problem Statement

You are given a string S consisting of lowercase English letters.

You are also given Q queries to process sequentially. The i-th query is described as follows:

• A string T_i consisting of lowercase English letters is given. Print the number of substrings of S that equal T_i. Two substrings are distinguished if they are taken from different positions, even if they are equal as strings.

Constraints

• 1 \leq |S| \leq 5 \times 10^5
• 1 \leq Q \leq 5 \times 10^5
• 1 \leq |T_i| \leq |S|
• \displaystyle \sum_{i=1}^Q |T_i| \leq 5 \times 10^5
• S and T_i are strings consisting of lowercase English letters.
• Q is an integer.

Sample Input 1

missisippi
5
i
s
a
is
missisippi

Sample Output 1

4
3
0
2
1

Let S[l:r] denote the substring of S from the l-th character through the r-th character.

• For the 1st query, four substrings of S equal i: S[2:2], S[5:5], S[7:7], S[10:10].
• For the 2nd query, three substrings of S equal s: S[3:3], S[4:4], S[6:6].
• For the 3rd query, no substrings of S match a.
• For the 4th query, two substrings of S equal is: S[2:3], S[5:6].
• For the 5th query, one substring of S equals missisippi: S[1:10].

Sample Input 2

aaaaaa
6
a
aa
aaa
aaaa
aaaaa
aaaaaa

Sample Output 2

6
5
4
3
2
1