Problem Statement

Takahashi is going to classify a person into the following three types (A, B, or C):

• A: Their BMI is strictly less than 20.
• B: Their BMI is 20 or greater, and strictly less than 25.
• C: Their BMI is 25 or greater.

The BMI of a person of height h meters and weight w kilograms is represented as \frac{w}{h^2}.

Determine the type of a person of height H centimeters and weight W kilograms.

Constraints

• 100 \leq H \leq 200
• 30 \leq W \leq 200
• All input values are integers.

Sample Input 1

170 55

Sample Output 1

A

The BMI of a person of height 170 centimeters and weight 55 kilograms is 19.03114..., which is less than 20. Thus, they are classified as type A.

Sample Input 2

100 200

Sample Output 2

C

Their BMI is 200, which is greater than or equal to 25, so they are classified as type C.

Problem Statement

You are given a tuple of N strings: S = (S_1,S_2,\ldots,S_N). Each S_i is one of Perfect, Great, Good, Bad, and Miss.

If S only contains Perfect, print All Perfect; otherwise, if it consists of Perfect and Great, print Full Combo; otherwise, print Failed.

Constraints

• 1\leq N \leq 100
• N is an integer.
• S_i is one of Perfect, Great, Good, Bad, and Miss.

Sample Input 1

3
Perfect
Great
Perfect

Sample Output 1

Full Combo

S does not consist only of Perfect, but it consists of Perfect and Great. Thus, Full Combo should be printed.

Sample Input 2

1
Perfect

Sample Output 2

All Perfect

Sample Input 3

5
Bad
Miss
Perfect
Great
Good

Sample Output 3

Failed

Problem Statement

Takahashi has N cards.
For i = 1, 2, \ldots, N, his i-th card has an integer A_i between 1 and 10 written on it.

For x = 1, 2, \ldots, 10, a card with the integer x written on it can be changed into P_x yen (currency in Japan).
Find the total amount of money Takahashi can get by changing all his cards into money.

Constraints

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

Sample Input 1

4
3 10 7 3
31 41 59 26 53 58 97 93 23 84

Sample Output 1

299

• The 1-st card has an integer 3 written on it, which is worth P_3 = 59 yen.
• The 2-nd card has an integer 10 written on it, which is worth P_{10} = 84 yen.
• The 3-rd card has an integer 7 written on it, which is worth P_7 = 97 yen.
• The 4-th card has an integer 3 written on it, which is worth P_3 = 59 yen.

Thus, he can change all his cards into money to get a total of 59 + 84 + 97 + 59 = 299 yen.

Sample Input 2

10
7 7 7 7 7 7 7 7 7 7
1 1 1 1 1 1 1000000000 1 1 1

Sample Output 2

10000000000

The answer may not fit into a 32-bit integer type.

Problem Statement

You are going to use a feature of a web service for a year.
First of all, you must sign up to become a free member, a standard member, or a premium member.

• You can become a free member with no charge. A free member can use the feature at most three times a month, but subsequent usage costs A yen each time.
• To become a standard member, you need to pay an annual fee of B yen on registration. A standard member can use the feature up to 50 times a month, with each additional use costing A yen.
• To become a premium member, you need to pay an annual fee of C yen on registration. A premium member can use the feature any number of times for free.

For i=1,2,\ldots,12, you are going to use the feature x_i times in the i-th month.
Find the minimum total cost required for the registration and using the feature.

Constraints

• 1 \leq A \leq 1000
• 1 \leq B \lt C \leq 1000
• 1 \leq x_i \leq 1000
• All input values are integers.

Sample Input 1

5 20 30
1 2 3 4 5 6 7 8 9 10 11 12

Sample Output 1

20

Suppose that you become a free member. In the first three months, you will use the features at most three times a month, and no payment is required; for the remaining months, you will use it more than three times a month, so you need to pay A yen once, twice, \ldots, and nine times, for a total of 225 yen.
Now consider becoming a standard member. You need to pay the annual fee of 20 yen on registration, but you will use the feature no more than 50 times a month, so no further payment is required.
If you become a premium member, you first need to pay an annual fee of 30 yen. But a premium member can use the feature as many times as they want, so no more payment is required.
Therefore, the minimum cost is 20 yen, when you become a standard member.

Sample Input 2

5 20 30
100 100 100 100 100 100 100 100 100 100 100 100

Sample Output 2

30

Sample Input 3

1 999 1000
50 50 50 50 50 50 50 50 50 50 50 50

Sample Output 3

564

Problem Statement

Applying the run-length encoding to a string is achieved by splitting the string into chunks, each consisting of the same character, and representing them as a sequence of pairs of the characters and the lengths.
For example, applying the run-length encoding to S = AAABCCCC yields (\mathrm{A}, 3), (\mathrm{B}, 1), (\mathrm{C}, 4).

Given a string S consisting of uppercase English letters, apply the run-length encoding to S and print the resulting sequence in the specified format.

Constraints

• S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of uppercase English letters.

Sample Input 1

ABBCCC

Sample Output 1

A 1 B 2 C 3

Applying the run-length encoding to S = ABBCCC yields (\mathrm{A}, 1), (\mathrm{B}, 2), (\mathrm{C}, 3).

Sample Input 2

AAAAAAAAAAAAA

Sample Output 2

A 13

Sample Input 3

ABCDE

Sample Output 3

A 1 B 1 C 1 D 1 E 1

Problem Statement

There is a N-vertex rooted binary tree whose vertices are numbered 1 through N. The root is vertex 1, and the parent of vertex i (2 \leq i \leq N) is vertex p_i. Every vertex has exactly zero or two children.
Vertex i has S_i written on it. S_i is either an integer or a character. If the vertex is a leaf, S_i is an integer; otherwise, it is either + or x.

You will repeatedly perform the following two kinds of operations in any order, until you are unable to do so.

• Choose a vertex, with + written on it, whose children both have integers written on them. Let a and b be those integers. Replace the + written on the vertex with the integer a+b, and remove the children.
• Choose a vertex, with x written on it, whose children both have integers written on them. Let a and b be those integers. Replace the x written on the vertex with the integer a \times b, and remove the children.

Once you are done, there will be only one remaining vertex with an integer written on it. Find this integer, modulo 998244353. (One can prove that the integer written on the final vertex is unique regardless of the order of the operations.)

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq p_i \leq i - 1 (2 \leq i \leq N)
• Every vertex occurs exactly zero times or twice in p_2, p_3, \dots, p_N.
• S_i is:
  • an integer between 1 and 10^8, inclusive, if vertex i is a leaf;
  • either + or x if vertex i is not a leaf.

Sample Input 1

5
1 1 2 2
+ x 3 2 5

Sample Output 1

13

By the following steps, there will be left a vertex with 13 written on it, so the answer is 13.

• Choose vertex 2. Replace the x written on vertex 2 with 2 \times 5 = 10, and remove vertices 4 and 5.
• Choose vertex 1. Replace the + written on vertex 1 with 10 + 3 = 13, and remove vertices 2 and 3.

Sample Input 2

7
1 2 1 4 4 2
x + 31415 + 92653 58979 32384

Sample Output 2

689770791

Make sure to find the answer modulo 998244353.

Problem Statement

There is a grid with H horizontal rows and W vertical columns. We denote by (i,j) the cell in the i-th row from the top and j-th column from the left.
Each cell has a lowercase English letter written on it. The letter written on (i, j) is G_{i, j}.
You are given a string S of length N. Is there a sequence of cells (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N) that satisfies the following conditions? Print Yes if there is, and No otherwise.

• (a_1, b_1), (a_2, b_2), \dots, and (a_N, b_N) are pairwise distinct.
• (a_i, b_i) and (a_{i+1}, b_{i+1}) are adjacent in one of the eight directions. In other words, \max(\vert a_i - a_{i+1} \vert, \vert b_i - b_{i+1} \vert) = 1.
• The letter written on (a_i, b_i) coincides with the i-th character of S.

Constraints

• 1 \leq H, W \leq 10
• G_{i, j} is a lowercase English letter.
• 1 \leq N \leq 5
• S is a length-N string consisting of lowercase English letters.

Sample Input 1

3 3
ekz
sza
znz
5
snake

Sample Output 1

Yes

The sequence of cells (2, 1), (3, 2), (2, 3), (1, 2), (1, 1) satisfies all the conditions in the problem statement, so the answer is Yes.

Sample Input 2

2 5
qwert
asdfg
4
awrg

Sample Output 2

No

Sample Input 3

3 3
abc
zbc
zzc
5
abcba

Sample Output 3

No

Problem Statement

There are N courses in a university. The i-th course requires an effort of a_i, is scheduled at the b_i-th time slot, and counts for c_i credits.

You need to take some of the courses to earn a total of M credits. However, you cannot take multiple courses scheduled at the same time slot.

If you can earn M or more credits, print the minimum total effort required to do so; otherwise, print -1.

Constraints

• 1 \leq N, M \leq 5000
• 1 \leq a_i,b_i,c_i \leq 5000
• All input values are integers.

Sample Input 1

3 4
3 1 2
4 1 2
5 2 2

Sample Output 1

8

If you take the 1-st and 3-rd courses, the total effort required is 8, which is the minimum.
Note that you cannot take both the 1-st and 2-nd courses, because they are scheduled at the same slot.

Sample Input 2

3 100
1 100 1
1 200 1
1 300 1

Sample Output 2

-1

Even if you take all the courses, you cannot earn 100 or more credits.

Sample Input 3

2 100
10 5 99
10 5 99

Sample Output 3

-1

The two courses are scheduled at the same time slot, so you cannot earn 100 or more credits.

Sample Input 4

10 522
4575 1426 4445
3772 81 3447
629 3497 2202
2775 4325 3982
4784 3417 2156
1932 902 728
3537 3857 739
1918 4211 4679
3506 3340 1568
1868 16 2940

Sample Output 4

629

Problem Statement

You are given N strings S_1,\ldots,S_N.

Find the number of integer pairs (i,j) such that:

• 1 \leq i,j \leq N, and
• S_i is a subsequence of S_j.

Constraints

• 1 \leq N \leq 10^5
• N is an integer.
• S_i is a string of length between 1 and 5, inclusive, consisting of lowercase English letters.

Sample Input 1

3
ps
past
post

Sample Output 1

5

Among nine pairs of integers (i,j) such that 1 \leq i,j \leq N, the following five satisfy the condition that S_i is a subsequence of S_j.

• (i,j)=(1,1)
• (i,j)=(1,2)
• (i,j)=(1,3)
• (i,j)=(2,2)
• (i,j)=(3,3)

Sample Input 2

5
a
aa
aaa
aaaa
aaaaa

Sample Output 2

15

Sample Input 3

2
hoge
hoge

Sample Output 3

4

Problem Statement

N customers visited a cafe: customer 1, customer 2, \ldots, and customer N.
For i = 1, 2, \ldots, N, customer i stayed in the cafe from time A_i to time B_i (including time A_i and time B_i).
No customers other than these N visited the cafe.

For each of Q times t_1, t_2, \ldots, t_Q, find the number of customers who were staying in the cafe at that time.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq A_i \lt B_i \leq 10^9
• 1 \leq t_i \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

0
1
2
4
3
1
0

• At time 1, no one was in the cafe.
• At time 2, one customer was in the cafe: customer 1.
• At time 3, two customers were in the cafe: customers 1 and 3.
• At time 4, four customers were in the cafe: customers 1, 2, 3, and 4.
• At time 5, three customers were in the cafe: customers 2, 3, and 4.
• At time 6, one customer was in the cafe: customer 3.
• At time 7, no one was in the cafe.

Sample Input 2

1
1 1000000000
2
1000000000
1

Sample Output 2

1
1

Problem Statement

You are given a length-N string S consisting of digits and ?.
Determine if one can replace each occurrence of ? with a digit so that the following value is a multiple of 10. If it is possible, find one such replacement.

• \displaystyle \sum^{N}_{i=1} i \times (the i-th character of S interpreted as a one-digit integer).

Constraints

• N is an integer between 1 and 2 \times 10^5, inclusive.
• S is a length-N string consisting of digits and ?.

Sample Input 1

5
935?0

Sample Output 1

Yes
93550

Consider what digit should replace the 4-th character ? of 935?0.

• If the 4-th character ? is replaced by 5, the resulting string is T= 93550.
  • 1 \times 9 + 2 \times 3 + 3 \times 5 + 4 \times 5 + 5 \times 0 = 50, which is indeed a multiple of 10.

Alternatively, we can also satisfy the condition in the problem statement by replacing the 4-th character ? with 0, thus yielding 93500.

Sample Input 2

5
1?3?5

Sample Output 2

No

There are 100 ways to replace the two occurrences of ? in 1?3?5, but none of them satisfies the condition in the problem statement.

Sample Input 3

1
0

Sample Output 3

Yes
0

While the string 0 does not contain ? to replace, 1 \times 0 = 0 is already a multiple of 10.

Problem Statement

There are N cities numbered 1 through N.
Every pair of different cities is connected by a bidirectional toll road. There is a voucher that can be used on any road to get a discount on the toll.
The toll of the road between city i and city j (i \lt j) is a_{i,j} yen; with the voucher, it is b_{i,j} yen. (b_{i,j} \lt a_{i,j})

Find the following value for all pairs of cities (i, j) such that i \lt j:

• the minimum amount of money required to travel from city i to city j, using the voucher at most once in total.

Constraints

• 2 \leq N \leq 300
• 1 \leq b_{i,j} \lt a_{i,j} \leq 10^4 (i \lt j)
• All input values are integers.

Sample Input 1

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

Sample Output 1

1 4 1
5 2
1

For example, you can travel from city 1 to city 3 using the voucher at most once for a total cost of 4 yen, which is the minimum, as follows:

• Travel from city 1 to city 4 for a cost of 1 yen, using the voucher.
• Travel from city 4 to city 3 for a cost of 3 yen, without using the voucher.

Sample Input 2

6
2255 36 196 3623 6579
681 183 473 8830
7549 743 8216
1078 9
224
105 3 1 810 15
7 125 11 3
50 6 1781
537 4
85

Sample Output 2

43 3 1 42 10
7 12 11 3
37 6 46
94 4
85

Problem Statement

There are two rectangles A and B on a coordinate plane, each moving at a constant velocity in parallel translation.

Each side of each rectangle is parallel to x or y axis. At time t,
the bottom-left and top-right vertices of rectangle A are at (U_1\times t+P_1,V_1\times t+Q_1) and (U_1\times t+R_1,V_1\times t+S_1), respectively;
the bottom-left and top-right vertices of rectangle B are at (U_2\times t+P_2,V_2\times t+Q_2) and (U_2\times t+R_2,V_2\times t+S_2), respectively.
Here, it is guaranteed that (U_1,V_1)\neq (U_2, V_2).

Between time 0 and time t=10^{100}, find the duration that rectangles A and B overlap; in other words, the intersection of the two rectangles has a positive area.

Constraints

• -1000\leq P_i<R_i\leq 1000
• -1000\leq Q_i<S_i\leq 1000
• -1000\leq U_i,V_i\leq 1000
• (U_1,V_1)\neq (U_2, V_2)
• All input values are integers.

Sample Input 1

0 0 1 1 2 0
2 -1 4 2 1 0

Sample Output 1

3.000000000000000

The two rectangles overlap between time t=1 and t=4, but not otherwise. Thus, the duration of overlap is 3.

Sample Input 2

0 0 5 5 1 1
2 2 3 3 0 -1

Sample Output 2

1.500000000000000

Sample Input 3

-5 -5 0 5 0 0
0 0 1 1 0 1

Sample Output 3

0.000000000000000

Note that when two rectangles only share sides or vertices, the area of the intersection is 0, so they are not considered overlapping.

Problem Statement

Takahashi is going to update N apps numbered app 1, app 2, \ldots, and app N.
Updating app i (1\leq i\leq N) costs T_i units of time.

Takahashi can choose the order of the apps to update.
Starting at time 0, his computer updates the apps one by one in the specified order.
Formally, if he lets the i-th (1\leq i\leq N) app to be updated be app p_i, the computer behaves as follows:

• updates app p_k from time (T_{p_1}+T_{p_2}+\cdots+T_{p_{k-1}}) to time (T_{p_1}+T_{p_2}+\cdots+T_{p_{k-1}}+T_{p_k}).

He wants to choose the order so that, when he checks the progress during the updates, he can estimate the total duration required for the entire updates as correctly as possible.

However, during the updates, he only has access to a single integer k, which indicates that the k-th update is underway.
If he recognizes that the k-th update is underway at time t, he estimates that the duration of the entire updates is f(t)=\frac{N}{k-0.5}\cdot t.
Here, at the time when the i-th update starts, he recognizes that the i-th update is underway. Specifically, at time 0 he regards that the 1-st update is underway; at the time when the i-th update finishes and (i+1)-th update starts, he regards that the (i+1)-th update is underway.

Let S\left(=\displaystyle\sum_{i=1}^N T_i\right) be the total duration for the entire updates. Suppose he estimates the duration of the entire updates at time t, which is a random real variable chosen from 0 (inclusive) to t (exclusive) uniformly at random. Find the minimum expected value of \lvert f(t)-S\rvert when he chooses the permutation to minimize it.

Constraints

• 2\leq N\leq 18
• 1\leq T_i\leq 10^6
• All input values are integers.

Sample Input 1

2
3 7

Sample Output 1

3.066666666666667

The total duration of the entire updates is S=3+7=10.
When he specify the updating order of the apps to be 1\to 2, his estimated duration f(t) of the entire updates if he checks the progress at time t (0\leq t<10) is:

• f(t)=\frac{2}{1-0.5}\cdot t=4t if 0\leq t< 3;
• f(t)=\frac{2}{2-0.5}\cdot t=\frac{4}{3}t if 3\leq t< 10.

When t is chosen from the range 0\leq t\lt 10 uniformly at random, the expected value of \lvert f(t)-S\rvert is \frac{46}{15}=3.066\cdots, which is the minimum possible value.

Sample Input 2

3
3 1 1

Sample Output 2

1.420000000000000

The expected value of \lvert f(t)-S\rvert is minimum if he specifies the updating order of the apps to be 1\to 3\to 2.

Problem Statement

You are given an integer sequence A = (A_1,A_2,\ldots,A_N) of length N. We define an operation against this sequence as follows.

• Operation: choose an element of A, and add 1 or -1.

Given Q queries, process them in the given order. Each query is of one of the following two kinds.

• 1 k d: Add d to A_k (where d is 1 or -1).
• 2 x: Find the minimum number of operations to make all the elements of A equal x. The operations are not actually performed.

Constraints

• All input values are integers.
• 1\leq N,Q \leq 2\times 10^5
• |A_i| \leq 10^9
• For each query of the 1-st kind, 1\leq k \leq N.
• For each query of the 1-st kind, d is 1 or -1.
• For each query of the 2-nd kind, |x| \leq 10^9.
• There is at least one query of the 2-nd kind.

Sample Input 1

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

Sample Output 1

7
5

Initially, A = (3,5,7,2).

• For the 1-st query, it is optimal to add 1 to A_1 once, add -1 to A_2 once, add -1 to A_3 three times, and 1 to A_4 twice. Thus, 1+1+3+2=7 should be printed.
• For the 2-nd query, add 1 to A_1. Now, A=(4,5,7,2).
• For the 3-rd query, add -1 to A_2. Now, A=(4,4,7,2).
• For the 4-th query, it is optimal to add -1 to A_3 three times and 1 to A_4 twice. Thus, 3+2=5 should be printed.

Sample Input 2

10
403 -397 -538 -996 496 -499 80 768 714 -346
10
1 4 -1
2 -362
2 389
2 -470
1 2 -1
2 -58
1 5 1
1 10 1
2 -88
1 3 1

Sample Output 2

5270
5856
5632
5239
5239