Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Takahashi has issued a 15-digit code S, which is a string of length 15 consisting of 0, \ldots, 9.

The leftmost digit of this 15-digit code is a check digit, which can be computed from the other 14 digits.

To do this, we first find the sum of all odd-positioned digits in the first 14 digits, that is, the 1-st (leftmost), 3-rd, 5-th, \ldots, digits from the left, and multiply this sum by 3. To this multiplied value, we then add all even-positioned digits from the left in the code. Finally, we divide the result of these additions by 10, and if the remainder matches the 15-th digit, the code is valid; otherwise, the code is invalid.

Take Takahashi's place to write a program that determines whether the code S is valid.

Constraints

• S has a length of 15.
• S consists of 0, \ldots , 9.

Sample Input 1

123451234512345

Sample Output 1

No

The sum of all odd-positioned digits in the first 14 digits is 1+3+5+2+4+1+3=19, which will be 57 after multiplying by 3.

Adding all even-positioned digits to 57 results in 57+2+4+1+3+5+2+4=78.

The remainder when dividing 78 by 10 is 8, which does not match the 15-th digit: 5.

Sample Input 2

123451234512348

Sample Output 2

Yes

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have A balls and B balloons. Takahashi will repeatedly remove one ball until the number of balls is at most C times the number of balloons. Find the number of balls that will eventually remain, divided by the number of balloons.

Constraints

• 1 \leq A,B,C \leq 10^4
• A, B, and C are integers.

Sample Input 1

8 3 2

Sample Output 1

2.000000000000000

Initially, we have 8 balls.
Takahashi will repeatedly remove a ball until we have not more than 6 balls, after which we will have 6 balls.
Thus, the answer is \frac{6}{3}=2.

Sample Input 2

8 5 2

Sample Output 2

1.600000000000000

We already have 8\leq 5\times 2 in the beginning, so Takahashi will not remove any ball.
Thus, the answer is \frac{8}{5}=1.6.

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a string S consisting of digits between 0 and 9 (inclusive).
Determine whether S satisfies both of the conditions below as the decimal representation of an integer.

• It has no unnecessary leading zeroes.
• It is between L and R.

Constraints

• S is a string consisiting of digits between 0 and 9 (inclusive).
• 1 \leq |S| \leq 100
• 0 \leq L \leq R \leq 10^9
• L and R are integers.

Sample Input 1

13579
10000 20000

Sample Output 1

Yes

13579 has no unnecessary leading 0 and is between 10000 and 20000, satisfying the condition. Thus, we should print Yes.

Sample Input 2

12345678901234567890
0 1000000000

Sample Output 2

No

S may represent an integer greater than the maximum value that a 64-bit integer type can represent.

Sample Input 3

05
5 5

Sample Output 3

No

05 has an unnecessary leading zero, violating the condition. Thus, we should print No.

Sample Input 4

0
0 1

Sample Output 4

Yes

Note that the 0 at the beginning of 0 is not an unnecessary leading zero.

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a string S of length N.

You can do the following operation any number of times:

• Replace a (contiguous) substring of S that matches axa, ixi, uxu, exe, or oxo with ....

You want to do this operation as many times as possible.

Print a string S that results from doing the maximum number of operations possible.

Constraints

• 1 \leq N \leq 2 \times 10^5
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

9
ixixixixi

Sample Output 1

...x...xi

The other correct answers include ...xix....

Sample Input 2

6
auxuxa

Sample Output 2

a...xa

We cannot do any more operations on a...xa.

Sample Input 3

15
gxgaxixuxexoxxx

Sample Output 3

gxgaxixuxexoxxx

We may be unable to do a single operation.

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a variable X whose initial value was 1.

Takahashi did 30 operations on this variable, where each operation multiplied X by 3. However, it did not result in X being 3^{30}, but it became N, a different value.

A mischievous boy Aoki has confessed that he did the following:

• He chose a integer k such that 1 \leq k \leq 30 and added 1 to X just after the k-th operation by Takahashi.

Given N, find k. Here, if no choice of k would result in X being N after the operations, print -1.

Constraints

• 1 \leq N \leq 10^{15}
• N \neq 3^{30}
• All values in input are integers.

Sample Input 1

205894618879050

Sample Output 1

10

Let us simulate the process for the case k=10.

Multiplying 1 by 3 ten times results in 59049. Then, Aoki mischievously adds 1 to it, resulting in 59050.

Multiplying that value by 3 twenty more times results in 205894618879050.

Sample Input 2

314159265358979

Sample Output 2

-1

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You have plans to attend N online meetings. The i-th meeting is scheduled to take place from S_i o'clock to T_i o'clock on the 24-hour clock D_i days later.
Determine whether some of these schedules are overlapping. Here, if a meeting starts exactly when another meeting ends, we do not consider them to be overlapping.

Constraints

• All values in input are integers.
• 1 ≤ N ≤ 10^5
• 1 ≤ D_i ≤ 10^5
• 0 ≤ S_i < T_i ≤ 24

Sample Input 1

3
1 10 15
1 11 12
1 14 16

Sample Output 1

Yes

The first and second meetings are overlapping, and so are the first and third meetings.

Sample Input 2

3
1 20 22
1 22 24
2 0 2

Sample Output 2

No

The first meeting is immediately followed by the second meeting, which is immediately followed by the third meeting, but we do not consider them to be overlapping.

Sample Input 3

5
2 0 24
1 0 10
3 0 1
1 12 23
3 22 24

Sample Output 3

No

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Represent a positive integer N by additions and subtractions of distinct powers of 3.

Formally, construct a sequence A that satisfies all of the following conditions.

• 1 \leq M \leq 100, where M is the length of A.
• \sum_{i=1}^{M}A_i = N.
• |A_i| \leq 10^{18}.
• For each i\ (1 \leq i \leq M), |A_i| is a power of 3. That is, there is a non-negative integer x such that |A_i|=3^x.
• |A_i| \neq |A_j|\ (i \neq j).

It is guaranteed that such a sequence A exists under the Constraints of this problem.

Constraints

• 1 \leq N \leq 10^{15}
• N is an integer.

Sample Input 1

6

Sample Output 1

2
9 -3 

Both 9 and 3 are powers of 3, and we have 9+(-3)=6, so this output satisfies the conditions.

Sample Input 2

9193

Sample Output 2

9
2187 27 1 -243 3 9 -81 6561 729 

Sample Input 3

10120190919012

Sample Output 3

16
-1594323 9 -177147 -531441 1162261467 -4782969 387420489 -6561 -2187 2541865828329 -27 7625597484987 3486784401 10460353203 -94143178827 31381059609 

Input may not fit into a 32-bit integer type.

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Takahashi's teacher has given Takahashi homework that required him to draw a polyline as follows.

1. Given are N positive integers A_1, A_2, \ldots, A_N, where A_1 = A_N = 0.
2. For each i = 1, 2, \ldots, N, plot a point P_i at the coordinates (i, A_i) in a two-dimensional plane.
3. For each i = 1, 2, \ldots, N-1, draw a segment connecting P_i and P_{i+1}.

To get it done early, Takahashi is planning to secretly modify the values of A_1, A_2, \ldots, A_N to shorten the total length of segments to draw.

However, in order to keep this secret modification from being noticed by his teacher, all of the following conditions must hold, where B_1, B_2, \ldots, B_N are the new values for A_1, A_2, \ldots, A_N after modification, respectively.

• B_1, B_2, \ldots, B_N are all non-negative integers.
• The values of A_1 and A_N cannot be modified, that is, B_1 = B_N = 0.
• \sum_{i=1}^{N} A_i = \sum_{i=1}^{N} B_i.

Find the minimum possible total length of segments to draw when Takahashi modifies the values of A_1, A_2, \ldots, A_N so that his teacher will not notice it.

Constraints

• 2 \leq N \leq 100
• 0 \leq A_i \leq 100
• A_1 = A_N = 0
• \sum_{i=1}^N A_i \leq 100
• All values in input are integers.

Sample Input 1

4
0 3 0 0

Sample Output 1

5.0644951022459797

Takahashi can minimize the total length of segments to draw by changing A_2 to 1 and A_3 to 2.

Sample Input 2

7
0 1 2 3 4 5 0

Sample Output 2

10.3245553203367599

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There was a portrait of Takahashi on a two-dimensional plane. It consisted of the right eye, the left eye, and N moles, at the following positions.

• The right eye was at the coordinates (-E, 0), and the left eye was at the coordinates (E, 0), where E \gt 0.
• The i-th mole was at the coordinate (A_i, B_i).

However, a mischievous boy Aoki moved this portrait (without flipping it). More formally, he translated and rotated the portrait.

As a result, the parts moved to the following positions:

• The right eye moved to the coordinates (x_1, y_1), and the left eye moved to the coordinates (x_2, y_2).
• The i-th mole moved to the coordinate (a_i, b_i).

Given the coordinates of the eyes and the moles after the move, find the coordinates of the moles before the move, that is, (A_1, B_1), \dots, (A_N, B_N).

Note that the given values do not contain the coordinates of the eyes before the move, that is, E.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^5 \leq x_i, y_i, a_i, b_i \leq 10^5
• E \gt 0
• (x_1, y_1), (x_2, y_2), (a_1, b_1), \dots, (a_N, b_N) are distinct.
• (-E, 0) \neq (x_1, y_1) or (E, 0) \neq (x_2, y_2).
• All values in input are integers.

Sample Input 1

2
5 0
-5 0
-1 3
2 4

Sample Output 1

1 -3
-2 -4

In the figure below, "移動前" and "移動後" mean before and after the move, "右目" and "左目" mean right and left eyes, and "ホクロ1個目" and "ホクロ2個目" means the first and second moles.

Given in input are the coordinates of both eyes and the moles after the move.

Sample Input 2

4
4 4
12 10
12 4
8 7
-4 -2
100 10

Sample Output 2

1.4 -4.8
0 0
-15 0
75.4 -52.8

All values in input are integers, but note that the values to be printed and E may not be integers.

Sample Input 3

10
-40336 -25353
25518 98473
-66200 57666
23235 -64774
56870 -67151
-99509 73639
39965 -61027
-54385 -34598
-57063 14129
63186 -88708
88770 85106
-92520 69200

Sample Output 3

-8970.87249328212 61817.21737274555
-75079.28924877638 -74637.35403870217
-61384.55754506934 -105449.9760881721
-10508.55928227892 98726.04733711783
-63915.43362406853 -87648.93490309674
-84883.41976667292 8062.914405771756
-43119.58914921946 33307.21406245974
-77451.63868397648 -121148.543178062
88022.56926540422 -62121.98851386775
-11146.07084342446 90471.08392051774

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There are N cities in the Kingdom of Takahashi, called City 1, City 2, \ldots, City N.
There are also M one-way roads in this kingdom, and you can use the i-th road to get from City u_i to City v_i.
(Note that the roads are one-way, that is, the i-th road does not allow you to get from City v_i to City u_i.)

Aoki, a resident of the Kingdom of Aoki, has come to the Kingdom of Takahashi for sightseeing. During his stay, he will travel by repeating the following:

• If there are one or more cities that he can reach by using just one road from the city he is currently in, he will choose one of those reachable cities and get there.
• If there is no city that he can reach by using just one road from the city he is currently in, he will go back to the Kingdom of Aoki.

Determine whether it is possible for Aoki to continue traveling indefinitely without returning to his country by choosing the appropriate city from which he starts his travel and keep making appropriate choices for where to go during his travel.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• i \neq j \Rightarrow (u_i, v_i) \neq (u_j, v_j)
• All values in input are integers.

Sample Input 1

3 3
1 2
2 1
2 3

Sample Output 1

Yes

By starting in City 1 and keep traveling in the manner 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow \cdots, he can continue his travel indefinitely.

Sample Input 2

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

Sample Output 2

No

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There are N cities in the Kingdom of AtCoder called City 1, City 2, \ldots, City N, and M roads called Road 1, Road 2, \ldots, Road M that connect the cities bidirectionally, so that you can travel between any two cities using some number of roads. Specifically, Road i connects City U_i and City V_i, and it enables you to get from either city to the other city in T_i hours.
Additionally, each city has a fixed value called scenery; the scenery of City i is A_i. When you travel from a city to another city by using one or more roads, the time needed for that travel will be the sum of the times it takes to get through the individual roads, and the satisfaction of that travel will be the sum of the sceneries of the cities visited during the travel, including the starting point and the destination. Here, the scenery of a city contributes to the satisfaction only once, even if that city is visited more than once.

Takahashi is now in City 1 and wants to get to City N. Since he is in a hurry, he wants to minimize the time it takes to travel, and maximize the satisfaction of the travel on the condition that the time needed is minimized. Find the satisfaction of the travel that meets these criteria.

Constraints

• 2 \leq N \leq 10^5
• N-1 \leq M \leq 2\times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq U_i,V_i \leq N
• U_i \neq V_i
• 1 \leq T_i \leq 10^9
• All values in input are integers.
• It is possible to travel between any two cities using some number of roads.

Sample Input 1

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

Sample Output 1

12

If we follow the path 1\to 2\to 4, the time needed will be 5, which is the minimum possible, and the satisfaction will be 10.
If we follow the path 1\to 3\to 4, the time needed will be 5, which is the minimum possible, and the satisfaction will be 12.
There is no other path that minimizes the time needed.
For example, the path 1\to 2\to 3\to 4 will have the satisfaction of 17, but the time needed will be 6, which is not the minimum possible. Additionally, there is no path from City 1 to City 4 such that the time needed is 4 or less.
Thus, the answer is 12.

Sample Input 2

6 5
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000

Sample Output 2

6000000000

Note that the answer may not fit into a 32-bit integer.

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a sequence of N integers A=(A_1, A_2, \dots ,A_N).
You are to process Q queries on this sequence. In the i-th query, given T_i, X_i, and Y_i, do as follows.

• If T_i = 1:
  Replace A_{X_i} with Y_i.
• If T_i = 2:
  Let p be the smallest value among A_{X_i}, \ldots ,A_{Y_i}. List all indices j such that X_i \leq j \leq Y_i and A_j = p.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• T_i is 1 or 2.
• 1 \leq X_i \leq N and 0 \leq Y_i \leq 10^9, if T_i=1.
• 1 \leq X_i \leq Y_i \leq N if T_i=2.
• All values in input are integers.
• The total number of indices j to be listed does not exceed 2 \times 10^5.

Sample Input 1

6 7
3 20 3 10 15 10
2 1 6
2 4 5
1 3 10
1 1 1000000000
2 1 6
1 5 0
2 1 6

Sample Output 1

2 1 3 
1 4 
3 3 4 6 
1 5 

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a sequence of N integers A=(A_1, A_2, \dots ,A_N) and an integer C.
Let us define the score of the sequence of K\ (K \geq 1) integers B=(B_1, B_2, \dots ,B_K) as the following:

\displaystyle C + \sum_{i=1}^{K-1} |B_{i+1} - B_i|.

We will decompose the sequence A into some (not necessarily contiguous) subsequences while keeping the relative order of the elements.

Here, let us define the total score as the sum of the scores of the subsequences obtained.

Find the minimum possible total score.

Constraints

• 1 \leq N \leq 200
• 1 \leq C \leq 10^9
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

6 10
4 25 1000000000 9 19 22

Sample Output 1

44

We should divide it into (4, 9), (25, 19, 22), (1000000000). Their scores are 15, 19, 10, respectively.

Sample Input 2

5 100
3 1 4 1 5

Sample Output 2

112

The score of (3, 1, 4, 1, 5) is 112.

Sample Input 3

10 5301
6708 1391 3108 7953 7797 2370 7699 1098 2362 2359

Sample Output 3

17095

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Consider an infinite coordinate plane. Initially, the plane is entirely painted white.
Let us process the following Q queries on this plane. The i-th query is in the following form:

Invert the rectangular region whose corners are (A_i,B_i), (A_i,D_i), (C_i,B_i), and (C_i,D_i). That is, the parts within the region that are painted white before this query will be painted black, and vice versa.

Find the area of the whole region painted black after all the queries.

Constraints

• 1 \leq Q \leq 10^5
• -10^9 \leq A_i < C_i \leq 10^9
• -10^9 \leq B_i < D_i \leq 10^9
• All values in input are integers.

Sample Input 1

2
0 0 2 2
1 1 3 3

Sample Output 1

6

After the first query, a 2 \times 2 square region is painted black.
After the second query, a square region whose corners are (1,1), (1,2), (2,1), (2,2) is white again, so the final area of the whole region painted black is 6.

Sample Input 2

1
-1000000000 -1000000000 1000000000 1000000000

Sample Output 2

4000000000000000000

Note that the answer may not fit into a 32-bit integer type.

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given are an integer N and sequences A and B of N integers each.
For the next N days, the following will happen to Takahashi.

• On the morning of Day i: He gains A_i yen (Japanese currency).
• On the afternoon of Day i: He is given an opportunity to buy a computer by paying any amount of money he likes as long as it will not result in a negative cash balance. He is allowed to choose not to buy a computer. If a new computer is bought when he already has one, the old one will be thrown away.
• On the night of Day i: He does his job. To do it, he has to own a computer worth B_i yen or more.

Initially, Takahashi has zero yen and no computer.

Determine whether it is possible for Takahashi to do all the jobs.
If it is possible, find the maximum possible amount of money he has at the end of Day N on the condition that all jobs are done.

Constraints

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

Sample Input 1

3
5 1
2 4
4 6

Sample Output 1

4

Takahashi can buy a computer worth 1 yen on the afternoon of Day 1, another worth 6 yen on Day 2, and nothing on Day 3 to do all the jobs and have 4 yen at the end of Day 3.

Sample Input 2

3
3 2
1 2
3 6

Sample Output 2

-1

Regardless of what choices Takahashi makes, he cannot do all the jobs. Thus, we should print -1.