Problem Statement

You are given a string S consisting of <, =, and >.
Determine whether S is a bidirectional arrow string.
A string S is a bidirectional arrow string if and only if there is a positive integer k such that S is a concatenation of one <, k =s, and one >, in this order, with a length of (k+2).

Constraints

• S is a string of length between 3 and 100, inclusive, consisting of <, =, and >.

Sample Input 1

<====>

Sample Output 1

Yes

<====> is a concatenation of one <, four =s, and one >, in this order, so it is a bidirectional arrow string.
Hence, print Yes.

Sample Input 2

==>

Sample Output 2

No

==> does not meet the condition for a bidirectional arrow string.
Hence, print No.

Sample Input 3

<>>

Sample Output 3

No

Problem Statement

You are given a string S. Here, the first character of S is an uppercase English letter, and the second and subsequent characters are lowercase English letters.

Print the string formed by concatenating the first character of S and UPC in this order.

Constraints

• S is a string of length between 1 and 100, inclusive.
• The first character of S is an uppercase English letter.
• The second and subsequent characters of S are lowercase English letters.

Sample Input 1

Kyoto

Sample Output 1

KUPC

The first character of Kyoto is K, so concatenate K and UPC, and print KUPC.

Sample Input 2

Tohoku

Sample Output 2

TUPC

Problem Statement

Takahashi ate N plates of sushi at a sushi restaurant. The color of the i-th plate is represented by a string C_i.

The price of a sushi corresponds to the color of the plate. For each i=1,\ldots,M, the sushi on a plate whose color is represented by a string D_i is worth P_i yen a plate (yen is the currency of Japan). If the color does not coincide with any of D_1,\ldots, and D_M, it is worth P_0 yen a plate.

Find the total amount of the prices of sushi that Takahashi ate.

Constraints

• 1\leq N,M\leq 100
• C_i and D_i are strings of length between 1 and 20, inclusive, consisting of lowercase English letters.
• D_1,\ldots, and D_M are distinct.
• 1\leq P_i\leq 10000
• N, M, and P_i are integers.

Sample Input 1

3 2
red green blue
blue red
800 1600 2800

Sample Output 1

5200

A blue plate, red plate, and green plate are worth P_1 = 1600, P_2 = 2800, and P_0 = 800 yen, respectively.

The total amount of the prices of the sushi that he ate is 2800+800+1600=5200 yen.

Sample Input 2

3 2
code queen atcoder
king queen
10 1 1

Sample Output 2

21

Problem Statement

Among the 81 integers that appear in the 9-by-9 multiplication table, find the sum of those that are not X.

There is a grid of size 9 by 9.
Each cell of the grid contains an integer: the cell at the i-th row from the top and the j-th column from the left contains i \times j.
You are given an integer X. Among the 81 integers written in this grid, find the sum of those that are not X. If the same value appears in multiple cells, add it for each cell.

Constraints

• X is an integer between 1 and 81, inclusive.

Sample Input 1

1

Sample Output 1

2024

The only cell with 1 in the grid is the cell at the 1st row from the top and 1st column from the left. Summing all integers that are not 1 yields 2024.

Sample Input 2

11

Sample Output 2

2025

There is no cell containing 11 in the grid. Thus, the answer is 2025, the sum of all 81 integers.

Sample Input 3

24

Sample Output 3

1929

Problem Statement

On a two-dimensional plane, Takahashi is initially at point (0, 0), and his initial health is H. M items to recover health are placed on the plane; the i-th of them is placed at (x_i,y_i).

Takahashi will make N moves. The i-th move is as follows.

1. Let (x,y) be his current coordinates. He consumes a health of 1 to move to the following point, depending on S_i, the i-th character of S:

   • (x+1,y) if S_i is R;
   • (x-1,y) if S_i is L;
   • (x,y+1) if S_i is U;
   • (x,y-1) if S_i is D.

2. If Takahashi's health has become negative, he collapses and stops moving. Otherwise, if an item is placed at the point he has moved to, and his health is strictly less than K, then he consumes the item there to make his health K.

Determine if Takahashi can complete the N moves without being stunned.

Constraints

• 1\leq N,M,H,K\leq 2\times 10^5
• S is a string of length N consisting of R, L, U, and D.
• |x_i|,|y_i| \leq 2\times 10^5
• (x_i, y_i) are pairwise distinct.
• All values in the input are integers, except for S.

Sample Input 1

4 2 3 1
RUDL
-1 -1
1 0

Sample Output 1

Yes

Initially, Takahashi's health is 3. We describe the moves below.

• 1-st move: S_i is R, so he moves to point (1,0). His health reduces to 2. Although an item is placed at point (1,0), he do not consume it because his health is no less than K=1.

• 2-nd move: S_i is U, so he moves to point (1,1). His health reduces to 1.

• 3-rd move: S_i is D, so he moves to point (1,0). His health reduces to 0. An item is placed at point (1,0), and his health is less than K=1, so he consumes the item to make his health 1.

• 4-th move: S_i is L, so he moves to point (0,0). His health reduces to 0.

Thus, he can make the 4 moves without collapsing, so Yes should be printed. Note that the health may reach 0.

Sample Input 2

5 2 1 5
LDRLD
0 0
-1 -1

Sample Output 2

No

Initially, Takahashi's health is 1. We describe the moves below.

• 1-st move: S_i is L, so he moves to point (-1,0). His health reduces to 0.

• 2-nd move: S_i is D, so he moves to point (-1,-1). His health reduces to -1. Now that the health is -1, he collapses and stops moving.

Thus, he will be stunned, so No should be printed.

Note that although there is an item at his initial point (0,0), he does not consume it before the 1-st move, because items are only consumed after a move.

Problem Statement

In the AtCoder Kingdom, there are N castle walls numbered from 1 through N. There are also M turrets.

Turret i guards castle walls numbered from L_i through R_i.

When a turret is destroyed, the castle walls that were guarded by that turret are no longer guarded by that turret.

What is the minimum number of turrets that need to be destroyed so that at least one castle wall is not guarded by any turret?

Constraints

• 1 \leq N \leq 10^6
• 1 \leq M \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

10 4
1 6
4 5
5 10
7 10

Sample Output 1

1

If turret 1 is destroyed, no turret guards castle wall 3. Also, if no turrets are destroyed, all castle walls are guarded by some turret. Therefore, output 1.

Sample Input 2

5 2
1 2
3 4

Sample Output 2

0

Since no turret guards castle wall 5, there already exists a castle wall not guarded by any turret without destroying any turrets. Therefore, output 0.

Sample Input 3

5 10
2 5
1 5
1 2
2 4
2 2
5 5
2 4
1 2
2 2
2 3

Sample Output 3

3

Problem Statement

You are given a string S of length N consisting of 0 and 1.

A string T of length N consisting of 0 and 1 is a good string if and only if it satisfies the following condition:

• There is exactly one integer i such that 1 \leq i \leq N - 1 and the i-th and (i + 1)-th characters of T are the same.

For each i = 1,2,\ldots, N, you can choose whether or not to perform the following operation once:

• If the i-th character of S is 0, replace it with 1, and vice versa. The cost of this operation, if performed, is C_i.

Find the minimum total cost required to make S a good string.

Constraints

• 2 \leq N \leq 2 \times 10^5
• S is a string of length N consisting of 0 and 1.
• 1 \leq C_i \leq 10^9
• N and C_i are integers.

Sample Input 1

5
00011
3 9 2 6 4

Sample Output 1

7

Performing the operation for i = 1, 5 and not performing it for i = 2, 3, 4 makes S = 10010, which is a good string. The cost incurred in this case is 7, and it is impossible to make S a good string for less than 7, so print 7.

Sample Input 2

4
1001
1 2 3 4

Sample Output 2

0

Sample Input 3

11
11111100111
512298012 821282085 543342199 868532399 690830957 973970164 928915367 954764623 923012648 540375785 925723427

Sample Output 3

2286846953

Problem Statement

There are N squares called Square 1 though Square N. You start on Square 1.

Each of the squares from Square 1 through Square N-1 has a die on it. The die on Square i is labeled with the integers from 0 through A_i, each occurring with equal probability. (Die rolls are independent of each other.)

Until you reach Square N, you will repeat rolling a die on the square you are on. Here, if the die on Square x rolls the integer y, you go to Square x+y.

Find the expected value, modulo 998244353, of the number of times you roll a die.

Notes

It can be proved that the sought expected value is always a rational number. Additionally, if that value is represented \frac{P}{Q} using two coprime integers P and Q, there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.

Constraints

• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le N-i(1 \le i \le N-1)
• All values in input are integers.

Sample Input 1

3
1 1

Sample Output 1

4

The sought expected value is 4, so 4 should be printed.

Here is one possible scenario until reaching Square N:

• Roll 1 on Square 1, and go to Square 2.
• Roll 0 on Square 2, and stay there.
• Roll 1 on Square 2, and go to Square 3.

This scenario occurs with probability \frac{1}{8}.

Sample Input 2

5
3 1 2 1

Sample Output 2

332748122

Problem Statement

You are given a sequence of integers A=(A_1,\ldots,A_N). For a tree T with N vertices, define f(T) as follows:

• Let d_i be the degree of vertex i in T. Then, f(T)=\sum_{i=1}^N {d_i}^2 A_i.

Find the minimum possible value of f(T).

The constraints guarantee the answer to be less than 2^{63}.

Constraints

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

Sample Input 1

4
3 2 5 2

Sample Output 1

24

Consider a tree T with an edge connecting vertices 1 and 2, an edge connecting vertices 2 and 4, and an edge connecting vertices 4 and 3.

Then, f(T) = 1^2\times 3 + 2^2\times 2 + 1^2\times 5 + 2^2\times 2 = 24. It can be proven that this is the minimum value of f(T).

Sample Input 2

3
4 3 2

Sample Output 2

15

Sample Input 3

7
10 5 10 2 10 13 15

Sample Output 3

128