Problem Statement

In the Kingdom of AtCoder, there is a standardized test of competitive programming proficiency.

An examinee will get a score out of 100 and obtain a rank according to the score, as follows:

• Novice, for a score not less than 0 but less than 40;
• Intermediate, for a score not less than 40 but less than 70;
• Advanced, for a score not less than 70 but less than 90;
• Expert, for a score not less than 90.

Takahashi took this test and got X points.

Find the minimum number of extra points needed to go up one rank higher. If, however, his rank was Expert, print expert, as there is no higher rank than that.

Constraints

• 0 \leq X \leq 100
• X is an integer.

Sample Input 1

56

Sample Output 1

14

He got 56 points and was certified as Intermediate. In order to reach the next rank of Advanced, he needs at least 14 more points.

Sample Input 2

32

Sample Output 2

8

Sample Input 3

0

Sample Output 3

40

Sample Input 4

100

Sample Output 4

expert

He got full points and was certified as Expert. There is no rank higher than that, so print expert.

Problem Statement

The value calculated by the following formula is called \mathrm{BMI}[\mathrm{kg}/\mathrm{m}^2]. (\div denotes division.)

• \text{Weight}[\mathrm{kg}] \div \text{Height}[\mathrm{m}] \div \text{Height}[\mathrm{m}]

In Japan, a person whose \mathrm{BMI} is 25 \; \mathrm{kg}/\mathrm{m}^2 or more is considered obese.
Determine whether a person with height H[\mathrm{cm}] and weight W[\mathrm{kg}] is considered obese in Japan.

Constraints

• 1 \leq H \leq 300
• 1 \leq W \leq 300
• All input values are integers.

Sample Input 1

180 60

Sample Output 1

No

Since the height is 180 \; \mathrm{cm}=1.8 \; \mathrm{m}, the \mathrm{BMI} is 60 \; \mathrm{kg} \div 1.8 \; \mathrm{m} \div 1.8 \; \mathrm{m}=18.5\dots \; \mathrm{kg}/\mathrm{m}^2, so this person is not considered obese.

Sample Input 2

182 188

Sample Output 2

Yes

Sample Input 3

180 81

Sample Output 3

Yes

Problem Statement

A real number X is given to the third decimal place.

Print the real number X under the following conditions.

• The decimal part must not have trailing 0s.
• There must not be an unnecessary trailing decimal point.

Constraints

• 0 \le X < 100
• X is given to the third decimal place.

Sample Input 1

1.012

Sample Output 1

1.012

1.012 can be printed as it is.

Sample Input 2

12.340

Sample Output 2

12.34

Printing 12.340 without the trailing 0 results in 12.34.

Sample Input 3

99.900

Sample Output 3

99.9

Printing 99.900 without the trailing 0s results in 99.9.

Sample Input 4

0.000

Sample Output 4

0

Printing 0.000 without trailing 0s or an unnecessary decimal point results in 0.

Problem Statement

There are N balls. Each ball is painted in one of N colors: color 1 through color N. The color of the i-th ball (1\le i\le N) is C_i.

In one operation, you can change the color of any one ball to any of the N colors.

Find the minimum number of operations required to make all the balls the same color.

Constraints

• 1\le N\le 100
• 1\le C_i\le N
• All input values are integers.

Sample Input 1

4
3 1 2 1

Sample Output 1

2

By changing the color of the first ball to 1 and the color of the third ball to 1, you can make all the balls the same color.

It is impossible to make all the balls the same color by changing the colors of fewer than two balls, so output 2.

Sample Input 2

5
3 3 3 3 3

Sample Output 2

0

All balls may have the same color from the beginning.

Sample Input 3

9
4 2 3 3 4 1 2 7 1

Sample Output 3

7

Problem Statement

There are N pieces of shari (vinegared rice) and M pieces of neta (toppings) as ingredients for sushi.

The weight of the i-th shari is A_i, and the weight of the j-th neta is B_j.

You will make sushi by combining shari and neta.

To make one piece of sushi, you need to combine one shari with one neta. Here, the weight of the neta must be at most twice the weight of the shari. Also, the same shari or neta cannot be used in multiple pieces of sushi.

Find the maximum number of sushi that can be made.

Constraints

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

Sample Input 1

4 5
4 2 1 8
14 9 3 2 9

Sample Output 1

3

By combining the 1st shari with the 3rd neta, the 2nd shari with the 4th neta, and the 4th shari with the 1st neta, for example, you can make three pieces of sushi. It is impossible to make four or more pieces of sushi, so output 3.

Sample Input 2

3 3
5 5 3
11 1000 1000

Sample Output 2

0

Sample Input 3

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

Sample Output 3

5

Problem Statement

You have an empty sequence and N balls. The size of the i-th ball (1 \leq i \leq N) is 2^{A_i}.

You will perform N operations.
In the i-th operation, you add the i-th ball to the right end of the sequence, and repeat the following steps:

1. If the sequence has one or fewer balls, end the operation.
2. If the rightmost ball and the second rightmost ball in the sequence have different sizes, end the operation.
3. If the rightmost ball and the second rightmost ball in the sequence have the same size, remove these two balls and add a new ball to the right end of the sequence with a size equal to the sum of the sizes of the two removed balls. Then, go back to step 1 and repeat the process.

Determine the number of balls remaining in the sequence after the N operations.

Constraints

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

Sample Input 1

7
2 1 1 3 5 3 3

Sample Output 1

3

The operations proceed as follows:

• After the first operation, the sequence has one ball, of size 2^2.
• After the second operation, the sequence has two balls, of sizes 2^2 and 2^1 in order.
• After the third operation, the sequence has one ball, of size 2^3. This is obtained as follows:
  • When the third ball is added during the third operation, the sequence has balls of sizes 2^2, 2^1, 2^1 in order.
  • The first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^1 + 2^1 = 2^2 is added. Now, the sequence has balls of sizes 2^2, 2^2.
  • Again, the first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^2 + 2^2 = 2^3 is added, leaving the sequence with a ball of size 2^3.
• After the fourth operation, the sequence has one ball, of size 2^4.
• After the fifth operation, the sequence has two balls, of sizes 2^4 and 2^5 in order.
• After the sixth operation, the sequence has three balls, of sizes 2^4, 2^5, 2^3 in order.
• After the seventh operation, the sequence has three balls, of sizes 2^4, 2^5, 2^4 in order.

Therefore, you should print 3, the final number of balls in the sequence.

Sample Input 2

5
0 0 0 1 2

Sample Output 2

4

The operations proceed as follows:

• After the first operation, the sequence has one ball, of size 2^0.
• After the second operation, the sequence has one ball, of size 2^1.
• After the third operation, the sequence has two balls, of sizes 2^1 and 2^0 in order.
• After the fourth operation, the sequence has three balls, of sizes 2^1, 2^0, 2^1 in order.
• After the fifth operation, the sequence has four balls, of sizes 2^1, 2^0, 2^1, 2^2 in order.

Therefore, you should print 4, the final number of balls in the sequence.

Problem Statement

You are given a string S consisting of three different characters: A, B, and C.

As long as S contains the string ABC as a consecutive substring, repeat the following operation:

Remove the leftmost occurrence of the substring ABC from S.

Print the final string S after performing the above procedure.

Constraints

• S is a string of length between 1 and 2 \times 10^5, inclusive, consisting of the characters A, B, and C.

Sample Input 1

BAABCBCCABCAC

Sample Output 1

BCAC

For the given string S = BAABCBCCABCAC, the operations are performed as follows.

• In the first operation, the ABC from the 3-rd to the 5-th character in S = BAABCBCCABCAC is removed, resulting in S = BABCCABCAC.
• In the second operation, the ABC from the 2-nd to the 4-th character in S = BABCCABCAC is removed, resulting in S = BCABCAC.
• In the third operation, the ABC from the 3-rd to the 5-th character in S = BCABCAC is removed, resulting in S = BCAC.

Therefore, the final S is BCAC.

Sample Input 2

ABCABC

Sample Output 2

In this example, the final S is an empty string.

Sample Input 3

AAABCABCABCAABCABCBBBAABCBCCCAAABCBCBCC

Sample Output 3

AAABBBCCC

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

There is a town represented as an xy-plane, where Santa lives, along with N children numbered 1 to N. Santa's house is at coordinates (S_X,S_Y), and the house of child i\ (1\leq i\leq N) is at (X_i,Y_i).

Santa wants to deliver one present to each of the N children in numerical order. To deliver a present to child i, Santa must visit the house of child i with at least one present in hand. However, Santa can only carry up to K presents at a time, and he must return to his own house to replenish presents (there are enough presents at Santa's house).

Find the minimum distance Santa must travel to leave his house, deliver presents to all N children, and return to his house.

Constraints

• 1\leq K\leq N \leq 2\times 10^5
• -10^9\leq S_X,S_Y,X_i,Y_i \leq 10^9
• (S_X,S_Y)\neq (X_i,Y_i)
• (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
• All input values are integers.

Sample Input 1

3 2
1 1
3 1
1 2
3 2

Sample Output 1

9.236067977499790

In the figure above, the red circle represents Santa's house, and the circles with numbers represent the houses of the children with those numbers.

Consider Santa acting as follows:

1. Leave his house with two presents.
2. Go to child 1's house and deliver a present.
3. Return to his house and replenish one present.
4. Go to child 2's house and deliver a present.
5. Go to child 3's house and deliver a present.
6. Return to his house.

In this case, Santa travels the distance of 2+2+1+2+\sqrt{5}=7+\sqrt{5}=9.236\dots, which is the minimum.

Sample Input 2

2 1
0 1
-1 1
1 1

Sample Output 2

4.000000000000000

Sample Input 3

8 3
735867677 193944314
586260100 -192321079
95834122 802780784
418379342 -790013317
-445130206 189801569
-354684803 -49687658
-204491568 -840249197
853829789 470958158
-751917965 762048217

Sample Output 3

11347715738.116592407226562