Problem Statement

The window of Takahashi's room has a width of A. There are two curtains hung over the window, each of which has a horizontal length of B. (Vertically, the curtains are long enough to cover the whole window.)

We will close the window so as to minimize the total horizontal length of the uncovered part of the window. Find the total horizontal length of the uncovered parts of the window then.

Constraints

• 1 \leq A \leq 100
• 1 \leq B \leq 100
• A and B are integers.

Sample Input 1

12 4

Sample Output 1

4

We have a window with a horizontal length of 12, and two curtains, each of length 4, that cover both ends of the window, for example. The uncovered part has a horizontal length of 4.

Sample Input 2

20 15

Sample Output 2

0

If the window is completely covered, print 0.

Sample Input 3

20 30

Sample Output 3

0

Each curtain may be longer than the window.

Problem Statement

It's now the season of TAKOYAKI FESTIVAL!

This year, N takoyaki (a ball-shaped food with a piece of octopus inside) will be served. The deliciousness of the i-th takoyaki is d_i.

As is commonly known, when you eat two takoyaki of deliciousness x and y together, you restore x \times y health points.

There are \frac{N \times (N - 1)}{2} ways to choose two from the N takoyaki served in the festival. For each of these choices, find the health points restored from eating the two takoyaki, then compute the sum of these \frac{N \times (N - 1)}{2} values.

Constraints

• All values in input are integers.
• 2 \leq N \leq 50
• 0 \leq d_i \leq 100

Sample Input 1

3
3 1 2

Sample Output 1

11

There are three possible choices:

• Eat the first and second takoyaki. You will restore 3 health points.
• Eat the second and third takoyaki. You will restore 2 health points.
• Eat the first and third takoyaki. You will restore 6 health points.

The sum of these values is 11.

Sample Input 2

7
5 0 7 8 3 3 2

Sample Output 2

312

Problem Statement

There are N slimes lining up from left to right. The colors of these slimes will be given as a string S of length N consisting of lowercase English letters. The i-th slime from the left has the color that corresponds to the i-th character of S.

Adjacent slimes with the same color will fuse into one larger slime without changing the color. If there were a slime adjacent to this group of slimes before fusion, that slime is now adjacent to the new larger slime.

Ultimately, how many slimes will be there?

Constraints

• 1 \leq N \leq 10^5
• |S| = N
• S consists of lowercase English letters.

Sample Input 1

10
aabbbbaaca

Sample Output 1

5

Ultimately, these slimes will fuse into abaca.

Sample Input 2

5
aaaaa

Sample Output 2

1

All the slimes will fuse into one.

Sample Input 3

20
xxzaffeeeeddfkkkkllq

Sample Output 3

10

Problem Statement

Takahashi has N sticks that are distinguishable from each other. The length of the i-th stick is L_i.

He is going to form a triangle using three of these sticks. Let a, b, and c be the lengths of the three sticks used. Here, all of the following conditions must be satisfied:

• a < b + c
• b < c + a
• c < a + b

How many different triangles can be formed? Two triangles are considered different when there is a stick used in only one of them.

Constraints

• All values in input are integers.
• 3 \leq N \leq 2 \times 10^3
• 1 \leq L_i \leq 10^3

Sample Input 1

4
3 4 2 1

Sample Output 1

1

Only one triangle can be formed: the triangle formed by the first, second, and third sticks.

Sample Input 2

3
1 1000 1

Sample Output 2

0

No triangles can be formed.

Sample Input 3

7
218 786 704 233 645 728 389

Sample Output 3

23

Problem Statement

There are N towns numbered 1 to N and M roads. The i-th road connects Town A_i and Town B_i bidirectionally and has a length of C_i.

Takahashi will travel between these towns by car, passing through these roads. The fuel tank of his car can contain at most L liters of fuel, and one liter of fuel is consumed for each unit distance traveled. When visiting a town while traveling, he can full the tank (or choose not to do so). Travel that results in the tank becoming empty halfway on the road cannot be done.

Process the following Q queries:

• The tank is now full. Find the minimum number of times he needs to full his tank while traveling from Town s_i to Town t_i. If Town t_i is unreachable, print -1.

Constraints

• All values in input are integers.
• 2 \leq N \leq 300
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq L \leq 10^9
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• \left(A_i, B_i\right) \neq \left(A_j, B_j\right) (if i \neq j)
• \left(A_i, B_i\right) \neq \left(B_j, A_j\right) (if i \neq j)
• 1 \leq C_i \leq 10^9
• 1 \leq Q \leq N\left(N-1\right)
• 1 \leq s_i, t_i \leq N
• s_i \neq t_i
• \left(s_i, t_i\right) \neq \left(s_j, t_j\right) (if i \neq j)

Sample Input 1

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

Sample Output 1

0
1

To travel from Town 3 to Town 2, we can use the second road to reach Town 2 without fueling the tank on the way.

To travel from Town 1 to Town 3, we can first use the first road to get to Town 2, full the tank, and use the second road to reach Town 3.

Sample Input 2

4 0 1
1
2 1

Sample Output 2

-1

There may be no road at all.

Sample Input 3

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

Sample Output 3

0
0
1
2
0
0
1
2
0
0
0
1
1
1
0
0
2
2
1
0

Problem Statement

Takahashi has N cards. The i-th of these cards has an integer A_i written on it.

Takahashi will choose an integer K, and then repeat the following operation some number of times:

• Choose exactly K cards such that the integers written on them are all different, and eat those cards. (The eaten cards disappear.)

For each K = 1,2, \ldots, N, find the maximum number of times Takahashi can do the operation.

Constraints

• 1 \le N \le 3 \times 10^5
• 1 \le A_i \le N
• All values in input are integers.

Sample Input 1

3
2 1 2

Sample Output 1

3
1
0

For K = 1, we can do the operation as follows:

• Choose the first card to eat.
• Choose the second card to eat.
• Choose the third card to eat.

For K = 2, we can do the operation as follows:

• Choose the first and second cards to eat.

For K = 3, we cannot do the operation at all. Note that we cannot choose the first and third cards at the same time.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

5
2
1
1
1

Sample Input 3

4
1 3 3 3

Sample Output 3

4
1
0
0