Warning

Do not make any mention of this problem until May 2, 2020, 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 is a building with 18 floors called B9, B8, ..., B1, 1F, 2F, ..., 9F.

The elevator in this building always takes one second to travel between two adjacent floors. For example, it takes 17 seconds to travel from B9 to 9F or vice versa.

Given two floors S and T, find the shortest time required for the elevator to travel from S and T.

Constraints

• Each of S and T is B1, B2, B3, B4, B5, B6, B7, B8, B9, 1F, 2F, 3F, 4F, 5F, 6F, 7F, 8F, or 9F.
• S and T are not equal.

Sample Input 1

1F 5F

Sample Output 1

4

It takes 4 seconds to travel from 1F to 5F.

Sample Input 2

B1 B7

Sample Output 2

6

It takes 6 seconds to travel from B1 to B7.

Sample Input 3

1F B1

Sample Output 3

1

1F and B1 are adjacent, and it takes 1 second to travel between them.

Sample Input 4

B9 9F

Sample Output 4

17

It takes 17 second to travel from B9 to 9F.

Warning

Do not make any mention of this problem until May 2, 2020, 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

A country held an election. There were three candidates: a, b, and c.

Given is a string S representing all the votes cast. S consists of the lowercase English letters a, b, and c, and the i-th character of S represents the candidate the i-th voter voted for. Find the candidate who received the most votes. It is guaranteed that there was exactly one candidate who received the most votes.

Constraints

• 1 \leq |S| \leq 1000
• S consists of a, b, and c.
• There was exactly one candidate who received the most votes.

Sample Input 1

abbc

Sample Output 1

b

The candidates a, b, and c received 1, 2, and 1 vote(s), respectively. Thus, b received the most votes.

Sample Input 2

cacca

Sample Output 2

c

The candidate b received no votes.

Sample Input 3

b

Sample Output 3

b

There was only one voter, and that person voted for b. Thus, b received the most votes.

Sample Input 4

babababacaca

Sample Output 4

a

Warning

Do not make any mention of this problem until May 2, 2020, 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 an N \times (2N - 1) grid (N vertical, 2N - 1 horizontal) for an integer 1 \leq N \leq 50.

Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

The squares are painted black and white so that the black part looks like a mountain. More specifically, for 1 \leq i \leq N and 1 \leq j \leq 2N - 1 such that |j - N| < i, (i, j) is painted black, and the other squares are painted white.

Below is the grid for the case N = 5. (# and . stand for a black square and a white square, respectively.)

....#....
...###...
..#####..
.#######.
#########

Now, we will write an X in some of the black squares.

The grid after this operation is given as a two-dimensional array of characters S of size N \times (2N - 1), where S_{i, j} corresponds to the square (i, j). If S_{i, j} is X, (i, j) is a black square with an X written on it; if S_{i, j} is #, (i, j) is a black square without an X written on it; if S_{i, j} is ., (i, j) is a white square.

Then, for each i = N - 1, N - 2, \cdots, 1 in this order, we will do the following operation:

• For each 2 \leq j \leq 2N - 2, if (i, j) is painted black, has no X written on it, and at least one of the squares (i+1, j-1), (i+1, j), and (i+1, j+1) has X written in it, write X in (i, j)

Compute the final state of the grid after all the operations.

Constraints

• 2 \leq N \leq 50
• S_{i, j} is ., #, or X.
• The state of the grid corresponding to S can be obtained by writing an X in one or more black squares in a grid painted black and white as described in Problem Statement.

Sample Input 1

5
....#....
...##X...
..#####..
.#X#####.
#########

Sample Output 1

....X....
...XXX...
..XX###..
.#X#####.
#########

Sample Input 2

2
.#.
#X#

Sample Output 2

.X.
#X#

Sample Input 3

10
.........#.........
........###........
.......#####.......
......#######......
.....#########.....
....###########....
...#############...
..###############..
.#################.
X#X########X#X####X

Sample Output 3

.........X.........
........XXX........
.......XXXXX.......
......XXXXXXX......
.....XXXXXXXXX.....
....XXXXXXXXXXX....
...XXX##XXXXXXXX...
..XXX####XXXXXXXX..
.XXX######XXXXX##X.
X#X########X#X####X

Warning

Do not make any mention of this problem until May 2, 2020, 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 lowercase English letters.

A non-empty string T of length at most 3 consisting of lowercase English letters and periods (.) is said to match S if and only if the following holds:

• Let K be the length of T. S has a contiguous substring of length K that can be equal to T after replacing each period in T with one lowercase English letter.

Among all non-empty strings of length at most 3 consisting of lowercase English letters and periods, how many match S?

Constraints

• 1 \leq |S| \leq 100
• S consists of lowercase English letters.

Sample Input 1

ab

Sample Output 1

7

Seven strings match S: a, b, ., .., .b, a., and ab, as follows:

• a: coincides with the 1-st character of S.
• b: coincides with the 2-nd character of S.
• .: coincides with the 1-st character of S after replacing the period with a, for example.
• ..: coincides with the 1-st and 2-nd characters of S after changing it to ab.
• .b: coincides with the 1-st and 2-nd characters of S after changing it to ab.
• a.: coincides with the 1-st and 2-nd characters of S after changing it to ab.
• ab: coincides with the 1-st and 2-nd characters of S.

Sample Input 2

aa

Sample Output 2

6

Six strings match S: a, ., .., .a, a., and aa.

Sample Input 3

aabbaabb

Sample Output 3

33

Warning

Do not make any mention of this problem until May 2, 2020, 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 permutation A_1, A_2, \ldots, A_N of 1, 2, \ldots, N.

For each integer 1 \leq i \leq N, find the minimum integer j not less than 1 that satisfies the following condition:

• If we let x = i and then replace x with A_x exactly j times, we have x = i.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq N
• A_i \neq A_j (i \neq j)
• All values in input are integers.

Sample Input 1

6
1 3 2 5 6 4

Sample Output 1

1 2 2 3 3 3

• For i = 1: Since A_1 = 1, j = 1 is the minimum value of j satisfying the condition.
• For i = 2: Since A_2 = 3, A_3 = 2, j = 2 is the minimum value of j satisfying the condition.
• For i = 3: Since A_3 = 2, A_2 = 3, j = 2 is the minimum value of j satisfying the condition.
• For i = 4: Since A_4 = 5, A_5 = 6, A_6 = 4, j = 3 is the minimum value of j satisfying the condition.
• For i = 5: Since A_5 = 6, A_6 = 4, A_4 = 5, j = 3 is the minimum value of j satisfying the condition.
• For i = 6: Since A_6 = 4, A_4 = 5, A_5 = 6, j = 3 is the minimum value of j satisfying the condition.

Sample Input 2

3
3 2 1

Sample Output 2

2 1 2

Sample Input 3

2
1 2

Sample Output 3

1 1

Warning

Do not make any mention of this problem until May 2, 2020, 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 N tasks. Let today be Day 1. You can do the i-th task on or after Day A_i, and finishing the task gives you B_i points.

Each day, starting with today, you choose one task and finish it. For each integer k from 1 through N, find the maximum total number of points that can be earned in the k days starting with today.

It is guaranteed that there are at least k tasks that you can do in the first k days for each integer k from 1 through N.

Constraints

• 1 \leq N \leq 2\times10^5
• 1 \leq A_i \leq N
• 1 \leq B_i \leq 100
• All values in input are integers.

Sample Input 1

3
1 3
2 2
2 4

Sample Output 1

3
7
9

On Day 1, only the first task is available. You do that task and earn 3 points, which is the answer for k=1. On Day 2, all three tasks are available. For k=2, do the first task on Day 1 and the third task on Day 2 to earn the maximum number of points: 3+4=7. For k=3, you can finish all the tasks in three days, so the answer is 3+2+4=9.

Sample Input 2

5
5 3
4 1
3 4
2 1
1 5

Sample Output 2

5
6
10
11
14

Sample Input 3

6
1 8
1 6
2 9
3 1
3 2
4 1

Sample Output 3

8
17
23
25
26
27

Warning

Do not make any mention of this problem until May 2, 2020, 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

Let us perform Q operations on a string S, which is initially empty.

The type of the i-th operation is represented by an integer T_i (1 \leq i \leq Q), as follows:

• If T_i = 1:
  • Given a lowercase English letter C_i and an integer X_i, append X_i copies of C_i to the end of S.
• If T_i = 2:
  • Given an integer D_i, erase the first D_i characters in S. If the length of S is D_i or less, S becomes empty. Then, find the number of as deleted in this operation, bs deleted in this operation, \cdots, and zs deleted in this operation. Let del_a, del_b, \cdots, del_z be the numbers of characters deleted. We ask you to print the value {del_a}^2 + {del_b}^2 + \cdots + {del_z}^2.

Constraints

• 1 \leq Q \leq 10^5
• T_i = 1 or 2.
• C_i is a lowercase English letters.
• 1 \leq X_i \leq 10^5
• 1 \leq D_i \leq 10^5
• Q, T_i, X_i, and D_i are integers.
• There is at least one operation with T_i = 2.

Sample Input 1

6
1 a 5
2 3
1 t 8
1 c 10
2 21
2 4

Sample Output 1

9
168
0

Initially, S is empty.

• After the 1-st operation, S is aaaaa.
• After the 2-nd operation, S is aa. Here, just three as get deleted.
• After the 3-rd operation, S is aatttttttt.
• After the 4-th operation, S is aattttttttcccccccccc.
• After the 5-th operation, S is empty, since the length of S is 20 before this operation. Here, two as, ten cs, and eight ts get deleted.
• After the 6-th operation, S is still empty. No characters get deleted.

Therefore, for the second operation, print 3^2 + 0^2 + \cdots + 0^2 = 9; for the fifth operation, print 2^2 + 10^2 + 8^2 = 168; for the sixth operation where no characters get deleted, print 0.

Sample Input 2

4
1 x 5
1 y 8
2 7
1 z 8

Sample Output 2

29

Initially, S is empty.

• After the 1-st operation, S is xxxxx.
• After the 2-nd operation, S is xxxxxyyyyyyyy.
• After the 3-rd operation, S is yyyyyy. Here, five xs and two ys get deleted, and 5^2 + 2^2 = 29.
• After the 4-th operation, S is yyyyyyzzzzzzzz.

Sample Input 3

3
1 p 3
1 q 100000
2 100000

Sample Output 3

9999400018

Warning

Do not make any mention of this problem until May 2, 2020, 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 an N \times M grid (N vertical, M horizontal), where each square contains one of the following characters: S, G, and the digits from1 through 9. There is only one square with S and only one square with G.

This grid is described by a two-dimensional array of characters A of size N \times M, where A_{i, j} is the character contained in the square at the i-th row from the top and j-th column from the left.

We now want to start at the square with S and reach the square with G. From each square, we can make a move to a horizontally or vertically (but not diagonally) adjacent square. It is not allowed to go out of the grid.

Find the minimum possible number of moves in such a path from the S square to the G square that contains the squares with 1, 2, \cdots, 9 in this order. If no such path exists, print -1.

Here, a path is said to contain the squares with 1, 2, \cdots, 9 in this order when the following holds: Assume that the path has k moves, and it visited squares with the characters c_0 = S, c_1, c_2, \cdots, c_k = G. There exists integers 1 \leq i_1 \leq i_2 \cdots \leq i_9 < k such that c_{i_1} = 1, c_{i_2} = 2, \cdots, c_{i_9} = 9.

A path may visit the same square multiple times, including the squares with S and G.

Constraints

• 1 \leq N, M \leq 50
• A consists of S, G, and digits from1 through 9.
• There is exactly one square with S and exactly one square with E.

Sample Input 1

3 4
1S23
4567
89G1

Sample Output 1

17

In this grid, only 1 appears twice. Let (i, j) denote the square at the i-th row from the top and the j-th square from the left. Then, the following path has the minimum possible number of moves, which is 17:

• (1, 2), (1, 1), (1, 2), (1, 3), (1, 4), (1, 3), (1, 2), (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (2, 3), (2, 2), (2, 1), (3, 1), (3, 2), (3, 3)

The squares shown by bold characters, for example, contain 1, 2, \cdots, 9, respectively.

Sample Input 2

1 11
S134258976G

Sample Output 2

20

Sample Input 3

3 3
S12
4G7
593

Sample Output 3

-1

The grid has no 6, so there is no path we are seeking, and we should print -1.

Warning

Do not make any mention of this problem until May 2, 2020, 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

2^N players with integer IDs - Player 1, Player 2, ..., Player 2^N - stood in a line and played an elimination tournament, as follows:

• Round 1: For each i such that 1 \leq i \leq 2^{N-1}, Player 2i-1 and Player 2i fight until one of them wins and survives.
• Round i (i \geq 2): The players survived Round i-1 stand in a line in ascending order of ID. Then, for each i such that 1 \leq i \leq 2^{N-i}, the (2i-1)-th and the $(2i)-th players from the left fight until one of them wins and survives.

While the record of each fight is now lost, our record says that the strength of Player i was A_i. Here, when two players fight, the player with the greater strength wins.

For each of the players, find the last round in which that player fought.

Constraints

• 1 \leq N \leq 16
• 1 \leq A_i \leq 2^N
• The elements of A are distinct.

Sample Input 1

2
2 4 3 1

Sample Output 1

1
2
2
1

• Round 1: Player 2 (strength: 4) fought against Player 1 (strength: 2) and won. Also, Player 3 (strength: 3) fought against Player 4 (strength: 1) and won.
• Round 2: Player 2 fought against Player 3 and won.

Thus, the last rounds in which Player 1,2,3,4 fought are Round 1,2,2,1, respectively.

Sample Input 2

1
2 1

Sample Output 2

1
1

There were just two players, in which case Round 1 was the last round for both of them.

Sample Input 3

3
4 7 5 1 6 3 2 8

Sample Output 3

1
3
2
1
2
1
1
3

Warning

Do not make any mention of this problem until May 2, 2020, 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 lowercase English letters a through z, (, and ). For strings a and b, let a+b be the concatenation of a and b in this order. Also, for a string a, let rev(a) be the reversal of a. Print the string S after repeating the following operation until it cannot be applied.

• If S has a substring of the form ( + a + ) where a is a string that does not contain (s or )s, replace that substring with a+rev(a).

Here, it is guaranteed that parentheses in S are balanced, that is, the final string will not contain (s or )s. Also, under this condition, it can be shown that the final string is uniquely determined.

Constraints

• S is a string of length between 1 and 1000 (inclusive) consisting of lowercase English letters a through z, (, and ).
• S contains one or more lowercase English letters.
• The string S after repeating the operation until it cannot be applied has a length of at most 1000 and does not contain (s or )s.

Sample Input 1

(ab)c

Sample Output 1

abbac

After replacing (ab) with ab +rev( ab ), that is, abba, S is abbac. We can do no more operations, so we should print this string.

Sample Input 2

past

Sample Output 2

past

The input may contain no parentheses.

Sample Input 3

(d(abc)e)()

Sample Output 3

dabccbaeeabccbad

There can be an empty string between parentheses.

Warning

Do not make any mention of this problem until May 2, 2020, 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 of length N consisting of (s and )s. Let S_i denote the i-th character of S.

We want to make S a balanced string (defined below) in the following procedure.

First, we do the operation below zero or more times:

• Choose an integer 1 \leq i \leq N. If S_i is (, replace it with ); if S_i is ), replace it with (. The cost of this operation is C_i.

Then, we do the operation below:

• Choose zero or more (possibly all) characters in S and delete them. Then, concatenate the remaining characters in S without changing the order.

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

A balanced string is a string that is one of the following:

• An empty string;
• The concatenation of A and B in this order, for some non-empty balanced strings A and B;
• The concatenation of (, A, and ) in this order, for some balanced string A/

Constraints

• 1 \leq N \leq 3000
• The length of S is N.
• Each character of S is ( or ).
• 1 \leq C_i \leq 10^9
• 1 \leq D_i \leq 10^9
• N, C_i, and D_i are integers.

Sample Input 1

3
))(
3 5 7
2 6 5

Sample Output 1

8

S is initially ))(. One way to make it a balanced string is:

• In the "modifying" step, change S_1 at the cost of 3. S becomes ()(.
• In the "deleting" step, delete S_3 at the cost of 5. S becomes ().

The total cost here is 3+5=8, and this is the minimum possible value.

Sample Input 2

1
(
10
20

Sample Output 2

20

S is initially (, and the only choice is to make it an empty string.

Sample Input 3

10
))())((()(
13 18 17 3 20 20 6 14 14 2
20 1 19 5 2 19 2 19 9 4

Sample Output 3

18

Sample Input 4

4
()()
17 8 3 19
5 3 16 3

Sample Output 4

0

S is already a balanced string.

Warning

Do not make any mention of this problem until May 2, 2020, 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 an integer sequence of length N: A_1, A_2, \cdots, A_N. Consider choosing K of its elements and arrange them in a row to form a new sequence without changing the relative order of the elements. Here, choosing A_i and A_j (i \neq j) at the same time is only allowed when |i - j| \geq D.

Find the lexicographically smallest sequence obtained in this way. If it is impossible to obtain a sequence in this way, print -1.

Here, a sequence of length K: x_1,x_2,\cdots,x_K is said to be lexicographically smaller than another sequence y_1,y_2,\cdots,y_K if and only if the sequences are different and x_i < y_i holds for the minimum integer i such that x_i \neq y_i.

Constraints

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

Sample Input 1

3 2 2
3 1 4

Sample Output 1

3 4

A = \{ 3, 1, 4\}. Under D = 2, there is one way to choose K = 2 elements to form a sequence, as follows:

• Choose the 1-st and 3-rd elements of A to form \{ 3, 4\}.

Thus, we should print \{ 3, 4\}.

Sample Input 2

3 3 2
3 1 4

Sample Output 2

-1

A = \{ 3, 1, 4\}. Under D = 2, there is no way to choose K = 3 elements to form a sequence.

Thus, we should print -1.

Sample Input 3

3 2 1
3 1 4

Sample Output 3

1 4

A = \{ 3, 1, 4\}. Under D = 1, there are three ways to choose K = 2 elements to form a sequence, as follows:

• Choose the 1-st and 2-nd elements of A to form \{ 3, 1\}.
• Choose the 1-st and 3-rd elements of A to form \{ 3, 4\}.
• Choose the 2-nd and 3-rd elements of A to form \{ 1, 4\}.

Thus, we should print -1.

Sample Input 4

4 2 2
3 6 5 5

Sample Output 4

3 5

A = \{ 3, 6, 5, 5\}. Under D = 2, there are three ways to choose K = 2 elements to form a sequence, as follows:

• Choose the 1-st and 3-rd elements of A to form \{ 3, 5\}.
• Choose the 1-st and 4-th elements of A to form \{ 3, 5\}.
• Choose the 2-nd and 4-th elements of A to form \{ 6, 5\}.

Thus, we should print \{ 3, 5\}.

Warning

Do not make any mention of this problem until May 2, 2020, 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

The menu in some company cafeteria is based on a D-day cycle. Its dishes are represented by integers, and it serves Dish C_i on Day i, Day i + D, Day i + 2D, and so on, where today is Day 1.

The N employees who use this cafeteria are particular about food, and Employee j loves Dish K_j. Each employee always uses the cafeteria on a day when the favorite dish is served and gets it. On the other days, an employee uses the cafeteria only if the last day when he/she used it is L days ago. However, the above does not apply when it is the first time for him/her to use it (described below).

For each integer 1 \leq j \leq N, answer the question below:

• Assume that Employee j uses the cafeteria on Day F_j for the first time. (For this day only, he/she uses it even if the served dish is not his/her favorite. Also, assume that he/she cannot use the cafeteria before this day even when his/her favorite dish is served.) Find the number of times Employee j gets the favorite dish until he/she uses the cafeteria T_j times in total.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq D \leq 10^5
• 1 \leq L \leq 10^9
• 1 \leq C_i, K_j \leq 10^5
• 1 \leq F_j \leq D
• 1 \leq T_j \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
0
3

The cafeteria serves the dishes with a 4-day cycle: \{ 2, 3, 1, 3 \}.

• Employee 1 loves Dish 1. He first eats Dish 3 on Day 2, then eats Dish 1 on Day 3. Thus, he gets his favorite dish once, and we should print 1.
• Employee 2 loves Dish 3. He eats Dish 1 on Day 3, and that is it. Thus, he gets his favorite dish zero times, and we should print 0.
• Employee 3 loves Dish 3. He first eats Dish 3 on Day 4, then eats Dish 3 on Day 6, then eats Dish 3 on Day 8. Thus, we should print 3.

Sample Input 2

3 1 3
1 1 1
2 1 3
1 2 3
1 3 3

Sample Output 2

0
3
3

The cafeteria serves Dish 1 every day.

• Employee 1 loves Dish 2. He first eats Dish 1 on Day 1, then also eats Dish 1 on Day 2 and 3 since L = 1. The cafeteria never offers his favorite, so we should print 0.
• Employee 2 and 3 love Dish 1, and they get their favorite every day, so we should print 3 for each of them.

Sample Input 3

10 4 4
4 4 4 3 1 1 5 2 2 1
2 5 2
2 9 10
2 3 3
2 7 13

Sample Output 3

1
5
1
6

Warning

Do not make any mention of this problem until May 2, 2020, 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

In a two-dimensional plane, there are N square plots of land whose sides are parallel to the x- or y-axis. The i-th plot can be represented as the region xmin_i \leq x \leq xmin_i + D_i, ymin_i \leq y \leq ymin_i + D_i. Each of these plots has a fixed cost, and the cost of the i-th plot is C_i.

Here, Q construction plans are considered. The j-th plan aims to construct a building at coordinates (A_j, B_j).

The cost of each plan is the sum of the costs of all the plots covering (or touching) the construction point.

Find the cost of each plan.

Constraints

• 1 \leq N \leq 50000
• 1 \leq Q \leq 100000
• -10^9 \leq xmin_i, ymin_i \leq 10^9
• 1 \leq D_i \leq 10^9
• 0 \leq C_i \leq 10^9
• -10^9 \leq A_i, B_i \leq 10^9
• All values in input are integers.

Sample Input 1

2 4
1 3 6 10
3 6 6 20
4 7
-1 -1
1 4
7 13

Sample Output 1

30
0
10
0

• For the 1-st plan, both plots cover the construction point, so we should print 10 + 20 = 30.
• For the 2-nd plan, neither plot covers the construction point, so we should print 0.
• For the 3-rd plan, the 1-st plot covers the construction point, so we should print 10.
• For the 4-th plan, neither plot covers the construction point, so we should print 0.

Sample Input 2

2 3
-3 5 4 100
1 9 7 30
1 9
1 8
8 10

Sample Output 2

130
100
30

• For the 1-st plan, both plots cover the construction point, so we should print 100 + 30 = 130.
• For the 2-nd plan, the 1-st plot covers the construction point, so we should print 100.
• For the 3-rd plan, the 2-nd plot covers the construction point, so we should print 30.

Sample Input 3

10 10
17 2 17 1000000000
7 12 12 1000000000
2 12 8 1000000000
2 12 2 1000000000
3 9 16 1000000000
8 13 15 1000000000
8 1 3 1000000000
15 9 17 1000000000
16 5 5 1000000000
13 12 9 1000000000
17 3
4 10
1 9
5 3
17 12
14 19
19 17
17 11
16 17
12 16

Sample Output 3

1000000000
1000000000
0
0
5000000000
4000000000
6000000000
3000000000
5000000000
3000000000

Warning

Do not make any mention of this problem until May 2, 2020, 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 simple connected undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the edges are numbered 1 to M.

Edge i connects Vertex A_i and B_i, and the weight of this edge is C_i.

For each edge from 1 to M, find a minimum-weight spanning tree containing that edge, and print the weight of that tree.

Notes

• A spanning tree in a connected undirected graph (V, E) is a tree that can be written as (V, T) for some subset of edges T \subseteq E.
• The weight of a spanning tree (V, T) is the sum of the weights of all edges in T.

Constraints

• 2 \leq N \leq 10^5
• N - 1 \leq M \leq \mathrm{min}(10^5, N(N - 1)/2)
• 1 \leq A_i, B_i \leq N (1 \leq i \leq M)
• A_i \neq B_i (1 \leq i \leq M)
• 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
• The given graph is simple and connected.

Sample Input 1

3 3
1 2 2
2 3 5
3 1 3

Sample Output 1

5
7
5

Sample Input 2

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

Sample Output 2

20
21
19
19
19
21
19

Sample Input 3

8 10
1 2 314159265
2 3 358979323
3 4 846264338
1 3 327950288
1 4 419716939
2 4 937510582
1 5 97494459
1 6 230781640
1 7 628620899
1 8 862803482

Sample Output 3

2881526972
2912556007
3308074371
2881526972
2881526972
3399320615
2881526972
2881526972
2881526972
2881526972

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