Problem Statement

Takahashi climbs an N-step staircase, ascending steps 1, 2, \ldots, N in order, starting from the ground. The height of the step (the difference in elevation from his immediately previous position) when climbing to step i is A_i.

Takahashi consumes stamina as he climbs the stairs. The stamina consumed at each step is determined as follows:

• When climbing to step 1 (from the ground to step 1), there is no previous step, so no extra burden is incurred, and he consumes stamina equal to the step height, which is A_1.
• For i \geq 2, if the step height A_i when climbing to step i is strictly greater than the step height A_{i-1} when climbing to step i-1 (i.e., A_i > A_{i-1}), the sudden increase in step height places extra burden on his legs, and he consumes 2 \times A_i stamina, which is twice the normal amount.
• For i \geq 2, if A_i \leq A_{i-1}, no extra burden is incurred, and he consumes A_i stamina.

Find the total stamina consumed when Takahashi finishes climbing all N steps.

Constraints

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

Sample Input 1

5
3 2 4 1 5

Sample Output 1

24

Sample Input 2

1
1000000000

Sample Output 2

1000000000

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10

Sample Output 3

109

Problem Statement

Takahashi is planning a hiking course that passes through N points arranged in a straight line.

The temperature at the j-th point is A_j.

When walking from the L-th point to the R-th point, the heat load received over that section is defined as the sum of temperatures A_L + A_{L+1} + \cdots + A_R. If the heat load is at least the threshold K, it is judged as "dangerous"; if it is less than K, it is judged as "safe".

M plans are given. In the i-th plan, one walks from the L_i-th point to the R_i-th point. The threshold for this plan is K_i. For each plan, determine whether it is "dangerous" or "safe".

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^5
• -10^4 \leq A_j \leq 10^4 （1 \leq j \leq N）
• 1 \leq L_i \leq R_i \leq N （1 \leq i \leq M）
• -2 \times 10^9 \leq K_i \leq 2 \times 10^9 （1 \leq i \leq M）
• All input values are integers

Sample Input 1

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

Sample Output 1

Dangerous
Safe
Dangerous
Safe

Sample Input 2

4 5
-2 7 -3 1
1 1 -2
1 2 6
2 3 4
3 4 -1
1 4 3

Sample Output 2

Dangerous
Safe
Dangerous
Safe
Dangerous

Sample Input 3

10 7
5 -4 8 0 -2 7 -6 3 1 -5
1 5 7
3 7 10
6 9 5
2 10 1
4 4 0
8 10 0
1 10 8

Sample Output 3

Dangerous
Safe
Dangerous
Dangerous
Dangerous
Safe
Safe

Sample Input 4

20 12
2 -1 3 5 -2 4 -3 6 -5 1 0 -4 7 -6 8 -7 9 -8 10 -9
1 4 9
5 10 1
7 13 2
12 20 5
1 20 10
14 19 7
15 17 10
2 18 8
8 8 6
9 12 -7
10 15 6
3 16 7

Sample Output 4

Dangerous
Dangerous
Dangerous
Safe
Dangerous
Safe
Dangerous
Safe
Dangerous
Safe
Dangerous
Dangerous

Sample Input 5

1 3
-10000
1 1 -2000000000
1 1 -10000
1 1 2000000000

Sample Output 5

Dangerous
Dangerous
Safe

Problem Statement

Takahashi has received requests for N jobs. Each job is numbered from 1 to N, and if he accepts job i, he receives a reward of A_i yen.

Takahashi plans to select and accept some of these jobs. Each job is either accepted or not accepted, and he must accept at least 1 job.

However, if he accepts both of two consecutively numbered jobs, additional costs are incurred due to the effort of adjusting his schedule. Specifically, for each i = 1, 2, \ldots, N-1, if he accepts both job i and job i + 1, an additional cost of K yen is incurred.

Takahashi's final profit is calculated by the following formula:

\text{(Profit)} = \text{(Total reward of accepted jobs)} - K \times \text{(Number of consecutively numbered pairs among accepted jobs)}

Here, "the number of consecutively numbered pairs" refers to the number of i satisfying 1 \leq i \leq N-1 such that both job i and job i+1 are accepted.

Find the maximum profit Takahashi can obtain when he selects and accepts one or more jobs from the N jobs.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^9
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

3 5
4 3 2

Sample Output 1

6

Sample Input 2

5 10
8 15 7 12 6

Sample Output 2

27

Sample Input 3

10 100
50 120 80 200 30 150 90 60 110 70

Sample Output 3

600

Problem Statement

In the town where Takahashi lives, there is a straight road running from east to west. Along this road, there are N installation spots for street lights lined up in a row, numbered from west to east as point 1, point 2, …, point N.

Currently, street lights are lit at M installation spots. Street light i (1 \leq i \leq M) is installed at point S_i. It is guaranteed that all street lights are installed at distinct points.

Takahashi wants to minimize the dark sections of the road. Specifically, when the point numbers where street lights are installed are sorted in ascending order, the maximum difference between the point numbers of adjacent street lights is defined as the "maximum dark interval."

However, if there is only one street light, the maximum dark interval is defined as 0.

Takahashi can choose exactly one of the currently lit street lights and relocate it from its current point to another empty installation spot (choosing not to relocate is not an option; exactly one street light must be relocated to a different empty point). Find the minimum possible value of the maximum dark interval after this operation.

Constraints

• 3 \leq N \leq 3 \times 10^5
• 2 \leq M \leq N - 1
• 1 \leq S_i \leq N (1 \leq i \leq M)
• All S_i are distinct
• All inputs are integers

Sample Input 1

10 4
2 6 9 4

Sample Output 1

2

Sample Input 2

7 3
1 4 7

Sample Output 2

2

Sample Input 3

50 12
3 8 15 16 23 31 37 40 41 45 48 50

Sample Output 3

7

Sample Input 4

200 35
2 7 13 19 25 31 38 44 51 58 66 73 81 90 99 108 117 126 135 144 153 161 168 174 180 185 189 192 194 196 197 198 199 200 1

Sample Output 4

9

Sample Input 5

3 2
1 2

Sample Output 5

1

Problem Statement

Takahashi is interested in examining the balance of the digits of integers.

When a positive integer is written in its standard decimal representation without leading zeros, let k be its number of digits, and let d_1, d_2, \ldots, d_k be its digits from left (most significant) to right (d_1 \geq 1). Define the sum of digits at odd-numbered positions (1st, 3rd, 5th, …) counting from the left as S_{\mathrm{odd}} = d_1 + d_3 + d_5 + \cdots, and the sum of digits at even-numbered positions (2nd, 4th, 6th, …) as S_{\mathrm{even}} = d_2 + d_4 + d_6 + \cdots. If no such positions exist (i.e., the sum has 0 terms), the sum is defined as 0. For example, for a single-digit positive integer, there are no even-numbered positions, so S_{\mathrm{even}} = 0.

Given a positive integer N and a non-negative integer D, a positive integer is said to be well-balanced if it satisfies

|S_{\mathrm{odd}} - S_{\mathrm{even}}| \leq D

That is, the absolute value of the difference between the sum of digits at odd-numbered positions and the sum of digits at even-numbered positions is at most D.

For example, when D = 2, consider the integer 31415. The digits at odd-numbered positions are d_1 = 3, d_3 = 4, d_5 = 5, giving S_{\mathrm{odd}} = 12, and the digits at even-numbered positions are d_2 = 1, d_4 = 1, giving S_{\mathrm{even}} = 2. The absolute value of the difference is |12 - 2| = 10, which exceeds D = 2, so this integer is not well-balanced. On the other hand, for the integer 123, S_{\mathrm{odd}} = 1 + 3 = 4, S_{\mathrm{even}} = 2, and the absolute value of the difference is 2, which is at most D = 2, so it is a well-balanced integer.

Find the number of positive integers between 1 and N, inclusive, that are well-balanced.

Constraints

• 1 \leq N \leq 10^{15}
• 0 \leq D \leq 100
• N is an integer
• D is an integer

Sample Input 1

123
2

Sample Output 1

52

Sample Input 2

50
0

Sample Output 2

4

Sample Input 3

100000
5

Sample Output 3

49917

Sample Input 4

987654321012345
20

Sample Output 4

901100492234266

Sample Input 5

1
0

Sample Output 5

0