Problem Statement

You are given two integers A and B.

How many integers x satisfy the following condition?

• Condition: It is possible to arrange the three integers A, B, and x in some order to form an arithmetic sequence.

A sequence of three integers p, q, and r in this order is an arithmetic sequence if and only if q-p is equal to r-q.

Constraints

• 1 \leq A,B \leq 100
• All input values are integers.

Sample Input 1

5 7

Sample Output 1

3

The integers x=3,6,9 all satisfy the condition as follows:

• When x=3, for example, arranging x,A,B forms the arithmetic sequence 3,5,7.
• When x=6, for example, arranging B,x,A forms the arithmetic sequence 7,6,5.
• When x=9, for example, arranging A,B,x forms the arithmetic sequence 5,7,9.

Conversely, there are no other values of x that satisfy the condition. Therefore, the answer is 3.

Sample Input 2

6 1

Sample Output 2

2

Only x=-4 and 11 satisfy the condition.

Sample Input 3

3 3

Sample Output 3

1

Only x=3 satisfies the condition.

Problem Statement

Takahashi has a piano with 100 keys arranged in a row. The i-th key from the left is called key i.

He will play music by pressing N keys one by one. For the i-th press, he will press key A_i, using his left hand if S_i= L, and his right hand if S_i= R.

Before starting to play, he can place both of his hands on any keys he likes, and his fatigue level at this point is 0. During the performance, if he moves one hand from key x to key y, the fatigue level increases by |y-x| (conversely, the fatigue level does not increase for any reason other than moving hands). To press a certain key with a hand, that hand must be placed on that key.

Find the minimum possible fatigue level at the end of the performance.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 100
• N and A_i are integers.
• S_i is L or R.

Sample Input 1

4
3 L
6 R
9 L
1 R

Sample Output 1

11

For example, the performance can be done as follows:

• Initially, place the left hand on key 3 and the right hand on key 6.
• Press key 3 with the left hand.
• Press key 6 with the right hand.
• Move the left hand from key 3 to key 9. The fatigue level increases by |9-3| = 6.
• Move the right hand from key 6 to key 1. The fatigue level increases by |1-6| = 5.
• Press key 9 with the left hand.
• Press key 1 with the right hand.

In this case, the fatigue level at the end of the performance is 6+5 = 11, which is the minimum possible.

Sample Input 2

3
2 L
2 L
100 L

Sample Output 2

98

Sample Input 3

8
22 L
75 L
26 R
45 R
72 R
81 R
47 L
29 R

Sample Output 3

188

Problem Statement

You are given a sequence of N positive integers A=(A_1,A_2,\dots,A_N).

Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N such that the subsequence (A_l,A_{l+1},\dots,A_r) forms an arithmetic progression.

A sequence (x_1,x_2,\dots,x_{|x|}) is an arithmetic progression if and only if there exists a d such that x_{i+1}-x_i=d\ (1\leq i < |x|). In particular, a sequence of length 1 is always an arithmetic progression.

Constraints

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

Sample Input 1

4
3 6 9 3

Sample Output 1

8

There are eight pairs of integers (l,r) satisfying the condition: (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3).

Indeed, when (l,r)=(1,3), (A_l,\dots,A_r)=(3,6,9) is an arithmetic progression, so it satisfies the condition. However, when (l,r)=(2,4), (A_l,\dots,A_r)=(6,9,3) is not an arithmetic progression, so it does not satisfy the condition.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

15

All pairs of integers (l,r)\ (1\leq l\leq r\leq 5) satisfy the condition.

Sample Input 3

8
87 42 64 86 72 58 44 30

Sample Output 3

22

Problem Statement

Takahashi will encounter N monsters in order. The i-th monster (1\leq i\leq N) has a strength of A_i.

For each monster, he can choose to either let it go or defeat it.
Each action awards him experience points as follows:

• If he lets a monster go, he gains 0 experience points.
• If he defeats a monster with strength X, he gains X experience points.
  If it is an even-numbered defeated monster (2nd, 4th, ...), he gains an additional X experience points.

Find the maximum total experience points he can gain from the N monsters.

Constraints

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

Sample Input 1

5
1 5 3 2 7

Sample Output 1

28

If Takahashi defeats the 1st, 2nd, 3rd, and 5th monsters, and lets the 4th monster go, he gains experience points as follows:

• Defeats a monster with strength A_1=1. He gains 1 experience point.
• Defeats a monster with strength A_2=5. He gains 5 experience points. As it is the 2nd defeated monster, he gains an additional 5 points.
• Defeats a monster with strength A_3=3. He gains 3 experience points.
• Lets the 4th monster go. Takahashi gains no experience points.
• Defeats a monster with strength A_5=7. He gains 7 experience points. As it is the 4th defeated monster, he gains an additional 7 points.

Therefore, in this case, he gains 1+(5+5)+3+0+(7+7)=28 experience points.
Note that even if he encounters a monster, if he lets it go, it does not count as defeated.

He can gain at most 28 experience points no matter how he acts, so print 28.
As a side note, if he defeats all monsters in this case, he would gain 1+(5+5)+3+(2+2)+7=25 experience points.

Sample Input 2

2
1000000000 1000000000

Sample Output 2

3000000000

Beware that the answer may not fit in a 32-bit integer.

Problem Statement

There are N islands and M bidirectional bridges connecting two islands. The islands and bridges are numbered 1, 2, \ldots, N and 1, 2, \ldots, M, respectively.
Bridge i connects islands U_i and V_i, and the time it takes to cross it in either direction is T_i.
No bridge connects an island to itself, but it is possible for two islands to be directly connected by more than one bridge.
One can travel between any two islands using some bridges.

You are given Q queries, so answer each of them. The i-th query is as follows:

You are given K_i distinct bridges: bridges B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}.
Find the minimum time required to travel from island 1 to island N using each of these bridges at least once.
Only consider the time spent crossing bridges.
You can cross the given bridges in any order and in any direction.

Constraints

• 2 \leq N \leq 400
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq U_i < V_i \leq N
• 1 \leq T_i \leq 10^9
• 1 \leq Q \leq 3000
• 1 \leq K_i \leq 5
• 1 \leq B_{i,1} < B_{i,2} < \cdots < B_{i,K_i} \leq M
• All input values are integers.
• It is possible to travel between any two islands using some bridges.

Sample Input 1

3 5
1 2 10
1 3 20
1 3 30
2 3 15
2 3 25
2
1
1
2
3 5

Sample Output 1

25
70

For the first query, we need to find the minimum time to travel from island 1 to island 3 while using bridge 1. The minimum time is achieved by using bridge 1 to move from island 1 to island 2, then using bridge 4 to move from island 2 to island 3. The time taken is 10 + 15 = 25. Hence, print 25 on the first line.

For the second query, we need to find the minimum time to travel from island 1 to island 3 while using both bridges 3 and 5. The minimum time is achieved by using bridge 3 to move from island 1 to island 3, then using bridge 5 to move to island 2, and finally using bridge 4 to return to island 3. The time taken is 30 + 25 + 15 = 70. Hence, print 70 on the second line.

Sample Input 2

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

Sample Output 2

5
3

For each query, you can cross the specified bridges in either direction.

Sample Input 3

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

Sample Output 3

4000000000

Beware that the answer may not fit in a 32-bit integer.

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left.

There are N coins on this grid, and the i-th coin can be picked up by passing through the cell (R_i,C_i).

Your goal is to start from cell (1,1), repeatedly move either down or right by one cell, and reach cell (H,W) while picking up as many coins as possible.

Find the maximum number of coins you can pick up and one of the paths that achieves this maximum.

Constraints

• 2\leq H,W \leq 2\times 10^5
• 1\leq N \leq \min(HW-2, 2\times 10^5)
• 1\leq R_i \leq H
• 1\leq C_i \leq W
• (R_i,C_i)\neq (1,1)
• (R_i,C_i)\neq (H,W)
• (R_i,C_i) are pairwise distinct.
• All input values are integers.

Sample Input 1

3 4 4
3 3
2 1
2 3
1 4

Sample Output 1

3
DRRDR

As shown in the figure above, by moving (1,1)\rightarrow (2,1)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (3,4), you can pick up three coins at (2,1),(2,3),(3,3).

Sample Input 2

2 2 2
2 1
1 2

Sample Output 2

1
DR

The path RD is also acceptable.

Sample Input 3

10 15 8
2 7
2 9
7 9
10 3
7 11
8 12
9 6
8 1

Sample Output 3

5
DRRRRRRRRDDDDDRRDRDDRRR

Problem Statement

You are given a tree with N vertices. The vertices are numbered 1, 2, \ldots, N.
The i-th edge (1\leq i\leq N-1) connects vertices U_i and V_i, with a length of L_i.

For each K=1,2,\ldots, N, solve the following problem.

Takahashi and Aoki play a game. The game proceeds as follows.

• First, Aoki specifies K distinct vertices on the tree.
• Then, Takahashi constructs a walk that starts and ends at vertex 1, and passes through all the vertices specified by Aoki.

The score is defined as the length of the walk constructed by Takahashi. Takahashi wants to minimize the score, while Aoki wants to maximize it. Find the score when both players play optimally.

Constraints

• 2\leq N\leq 2\times 10^5
• 1\leq U_i<V_i\leq N
• 1\leq L_i\leq 10^9
• All input values are integers.
• The given graph is a tree.

Sample Input 1

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

Sample Output 1

16
22
26
26
26

For K=1, Aoki's optimal move is to specify vertex 3, and Takahashi's optimal move is to construct a path vertex 1 \to vertex 2 \to vertex 3 \to vertex 2 \to vertex 1, resulting in a score of 16.

For K=2, Aoki's optimal move is to specify vertices 3 and 5, and Takahashi's optimal move is to construct a path such as vertex 1 \to vertex 5 \to vertex 1 \to vertex 2 \to vertex 3 \to vertex 2 \to vertex 1, resulting in a score of 22.

For K\geq 3, the score when both players play optimally is 26.

Sample Input 2

3
1 2 1000000000
2 3 1000000000

Sample Output 2

4000000000
4000000000
4000000000

Beware that the answer may not fit in a 32-bit integer.