Problem Statement

Takahashi measured his body temperature and found it to be X {}^\circC.

Body temperature is classified into the following:

• Higher than or equal to 38.0 {}^\circC: “High fever”
• Higher than or equal to 37.5 {}^\circC and lower than 38.0 {}^\circC: “Fever”
• Lower than 37.5 {}^\circC: “Normal”

Which classification does Takahashi's body temperature fall into? Present the answer as an integer according to the Output section.

Constraints

• 30 \leq X \leq 50
• X is given to one decimal place.

Sample Input 1

40.0

Sample Output 1

1

His body temperature is 40.0 {}^\circC, which is classified as a high fever. Thus, print 1.

Sample Input 2

37.7

Sample Output 2

2

His body temperature is 37.7 {}^\circC, which is classified as a fever. Thus, print 2.

Sample Input 3

36.6

Sample Output 3

3

His body temperature is 36.6 {}^\circC, which is classified as a normal temperature. Thus, print 3.

Problem Statement

Takahashi is playing a game. This game has eight worlds, and each world has eight stages. The stages have an order, and the first stage is the 1st stage in the 1st world. The next stage after the j-th stage (1\le j\le 8) in the i-th world (1\le i\le 8) is as follows:

• When j\lt8, the next stage is the (j+1)-th stage in the i-th world.
• When i\lt8,j=8, the next stage is the 1st stage in the (i+1)-th world.
• When i=8,j=8, there is no next stage. This stage is the last stage.

The name of the j-th stage (1\le j\le 8) in the i-th world (1\le i\le 8) is i-j. For example, the name of the first stage is 1-1, and the name of the last stage is 8-8.

Given the stage name S of the stage Takahashi is currently playing, output the stage name of the next stage.

Constraints

• S is the stage name of one of the stages.
• S is not 8-8.

Sample Input 1

4-2

Sample Output 1

4-3

The next stage after the 2nd stage in the 4th world is the 3rd stage in the same world.

Sample Input 2

1-8

Sample Output 2

2-1

1-8 is the last stage in the 1st world, so the next stage is the 1st stage in the 2nd world.

Sample Input 3

3-3

Sample Output 3

3-4

Problem Statement

You are given a positive integer X.

Find the minimum value among all positive integers that can be obtained by rearranging the digits appearing in the decimal representation of X (without leading zeros) such that there is no leading zero.

Constraints

• 1\leq X < 10^5
• X is an integer.

Sample Input 1

903

Sample Output 1

309

There are four positive integers that can be obtained by rearranging the digits appearing in the decimal representation of X such that there is no leading zero: 903, 930, 309, 390; the minimum value among them is 309.

Sample Input 2

432

Sample Output 2

234

Sample Input 3

100

Sample Output 3

100

Problem Statement

You are given a string T consisting of lowercase English letters and ?, and a string U consisting of lowercase English letters.

The string T is obtained by taking some lowercase-only string S and replacing exactly four of its characters with ?.

Determine whether it is possible that the original string S contained U as a contiguous substring.

Constraints

• T is a string of length between 4 and 10, inclusive, consisting of lowercase letters and ?.
• T contains exactly four occurrences of ?.
• U is a string of length between 1 and |T|, inclusive, consisting of lowercase letters.

Sample Input 1

tak??a?h?
nashi

Sample Output 1

Yes

For example, if S is takanashi, it contains nashi as a contiguous substring.

Sample Input 2

??e??e
snuke

Sample Output 2

No

No matter what characters replace the ?s in T, S cannot contain snuke as a contiguous substring.

Sample Input 3

????
aoki

Sample Output 3

Yes

Problem Statement

There are N mochi (rice cakes) arranged in ascending order of size. The size of the i-th mochi (1 \leq i \leq N) is A_i.

Given two mochi A and B, with sizes a and b respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi A on top of mochi B if and only if a is at most half of b.

You choose two mochi out of the N mochi, and place one on top of the other to form one kagamimochi.

Find how many different kinds of kagamimochi can be made.

Two kagamimochi are distinguished if at least one of the mochi is different, even if the sizes of the mochi are the same.

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
• A_i \leq A_{i+1} \ (1 \leq i < N)
• All input values are integers.

Sample Input 1

6
2 3 4 4 7 10

Sample Output 1

8

The sizes of the given mochi are as follows:

In this case, you can make the following eight kinds of kagamimochi:

Note that there are two kinds of kagamimochi where a mochi of size 4 is topped by a mochi of size 2, and two kinds where a mochi of size 10 is topped by a mochi of size 4.

Sample Input 2

3
387 388 389

Sample Output 2

0

It is possible that you cannot make any kagamimochi.

Sample Input 3

32
1 2 4 5 8 10 12 16 19 25 33 40 50 64 87 101 149 175 202 211 278 314 355 405 412 420 442 481 512 582 600 641

Sample Output 3

388

Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N consisting of non-negative integers.

Determine if there is an even number represented as the sum of two different elements of A. If it exists, find the maximum such number.

Constraints

• 2\leq N \leq 2\times 10^5
• 0\leq A_i\leq 10^9
• The elements of A are distinct.
• All values in the input are integers.

Sample Input 1

3
2 3 4

Sample Output 1

6

The values represented as the sum of two distinct elements of A are 5, 6, and 7. We have an even number here, and the maximum is 6.

Sample Input 2

2
1 0

Sample Output 2

-1

The value represented as the sum of two distinct elements of A is 1. We have no even number here, so -1 should be printed.

Problem Statement

There are N pieces of a chocolate bar placed on a table. Piece i\ (1 \leq i \leq N) is a rectangle of h_i blocks tall and w_i blocks wide.

It is known that these pieces were obtained by the following procedure.

• Start by holding a chocolate bar of H blocks tall and W blocks wide. Nothing is placed on the table.
• Repeat the following operation N-1 times.
  • Split the piece currently in hand into two pieces. Both pieces after splitting must be rectangles along the block boundaries.
  • Place one of the pieces on the table, and keep the other piece in hand.
• Finally, place the piece in hand on the table.

Find one way to arrange the N pieces into a rectangle of H blocks tall and W blocks wide satisfying the following conditions.

• Different pieces do not overlap.
• Pieces must not be rotated. That is, for h \neq w, a piece of h blocks tall and w blocks wide cannot be placed as a piece of w blocks tall and h blocks wide.

Constraints

• 1 \leq H \leq 10^9
• 1 \leq W \leq 10^9
• 2 \leq N \leq 2\times 10^5
• 1 \leq h_i \leq H
• 1 \leq w_i \leq W
• It is guaranteed that the input was obtained by the procedure described in the problem statement.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2 2
4 1
1 1
1 2
1 4
1 5

The arrangement in the sample output is illustrated below.

Sample Input 2

100 100 20
72 7
4 74
17 67
20 67
96 3
1 95
5 81
87 3
3 87
16 67
95 8
100 2
92 1
3 98
92 5
87 3
1 98
19 67
11 74
87 1

Sample Output 2

7 89
90 22
62 22
7 22
4 96
99 1
94 15
7 19
4 9
27 22
4 1
1 99
7 14
1 1
7 9
7 16
100 1
43 22
79 22
7 15

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N.

Find \displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\left\lfloor\frac{\max(A_i,A_j)}{\min(A_i,A_j)}\right\rfloor.

Here, \lfloor x \rfloor represents the greatest integer not greater than x. For example, \lfloor 3.14 \rfloor=3 and \lfloor 2 \rfloor=2.

Constraints

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

Sample Input 1

3
3 1 4

Sample Output 1

8

The sought value is

\left\lfloor\frac{\max(3,1)}{\min(3,1)}\right\rfloor + \left\lfloor\frac{\max(3,4)}{\min(3,4)}\right\rfloor + \left\lfloor\frac{\max(1,4)}{\min(1,4)}\right\rfloor\\ =\left\lfloor\frac{3}{1}\right\rfloor + \left\lfloor\frac{4}{3}\right\rfloor + \left\lfloor\frac{4}{1}\right\rfloor\\ =3+1+4\\ =8.

Sample Input 2

6
2 7 1 8 2 8

Sample Output 2

53

Sample Input 3

12
3 31 314 3141 31415 314159 2 27 271 2718 27182 271828

Sample Output 3

592622

Problem Statement

There is a road extending east and west, and N persons are on the road. The road extends infinitely long to the east and west from a point called the origin.

The i-th person (1\leq i\leq N) is initially at a position X_i meters east from the origin.

The persons can move along the road to the east or west. Specifically, they can perform the following movement any number of times.

• Choose one person. If there is no other person at the destination, move the chosen person 1 meter east or west.

They have Q tasks in total, and the i-th task (1\leq i\leq Q) is as follows.

• The T_i-th person arrives at coordinate G_i.

Find the minimum total number of movements required to complete all Q tasks in order.

Constraints

• 1\leq N\leq2\times10^5
• 0\leq X_1 < X_2 < \dotsb < X_N \leq10^8
• 1\leq Q\leq2\times10^5
• 1\leq T_i\leq N\ (1\leq i\leq Q)
• 0\leq G_i\leq10^8\ (1\leq i\leq Q)
• All input values are integers.

Sample Input 1

5
10 20 30 40 50
4
3 45
4 20
1 35
2 60

Sample Output 1

239

An optimal sequence of movements for the persons is as follows (the positions of the persons are not necessarily drawn to scale):

For each task, the persons move as follows.

• The 4th person moves 6 steps east, and the 3rd person moves 15 steps east.
• The 2nd person moves 2 steps west, the 3rd person moves 26 steps west, and the 4th person moves 26 steps west.
• The 4th person moves 18 steps east, the 3rd person moves 18 steps east, the 2nd person moves 18 steps east, and the 1st person moves 25 steps east.
• The 5th person moves 13 steps east, the 4th person moves 24 steps east, the 3rd person moves 24 steps east, and the 2nd person moves 24 steps east.

The total number of movements is 21+54+79+85=239.

You cannot complete all tasks with a total movement count of 238 or less, so print 239.

Sample Input 2

8
0 1 2 3 4 5 6 100000000
6
1 100000000
8 0
1 100000000
8 4
1 100000000
5 21006578

Sample Output 2

4294967297

Note that some persons may need to move to the west of the origin or more than 10^8 meters to the east of it.

Also, note that the answer may exceed 2^{32}.

Sample Input 3

12
1558 3536 3755 3881 4042 4657 5062 7558 7721 8330 8542 9845
8
9 1694
7 3296
12 5299
5 5195
5 5871
1 2491
8 1149
8 2996

Sample Output 3

89644