A mistake was made in the test case, requiring a re-judgment.

Problem Statement

Takahashi is shopping at a supermarket.

Takahashi has placed K items in his shopping basket. Each item has a price tag, and the price of the i-th item (1 \leq i \leq K) is L_i yen.

This supermarket is running a campaign where, at checkout, customers receive points equal to the remainder when the total amount is divided by a positive integer M.

That is, if the total sum of all item prices is S = L_1 + L_2 + \cdots + L_K, the points Takahashi receives are the remainder when S is divided by M. Note that if S is a multiple of M, the points received are 0.

Find the number of points Takahashi will receive.

Constraints

• 1 \leq K \leq 10^5
• 1 \leq M \leq 10^9
• 1 \leq L_i \leq 10^4 (1 \leq i \leq K)
• All inputs are integers

Sample Input 1

3 100
150 80 45

Sample Output 1

75

Sample Input 2

5 1000
1200 350 890 460 720

Sample Output 2

620

Sample Input 3

10 500000000
9999 8765 4321 5678 1234 7777 3333 6666 2222 8888

Sample Output 3

58883

Problem Statement

Takahashi challenges himself to explore a dungeon.

The dungeon has N rooms arranged in a row. The i-th room from the left contains 1 monster. The i-th monster has strength H_i, and upon being defeated, it drops an item that restores P_i health points.

Takahashi visits all rooms exactly once, from room 1 to room N in order of increasing room number. Takahashi's initial health is S. There is no upper limit on health.

When visiting each room i, the following rules are automatically applied. Takahashi has no choice in the matter.

• If his current health is greater than or equal to H_i, Takahashi defeats the monster. First, his health decreases by H_i, and immediately after, it recovers by P_i. That is, the net change in health is -H_i + P_i. Since his health was at least H_i just before the battle, it is guaranteed that his health is non-negative immediately after the H_i decrease.
• If his current health is less than H_i, Takahashi cannot defeat the monster and passes through the room. In this case, his health does not change.

For each room where a monster was not defeated, Takahashi must pay a penalty of C.

After visiting all N rooms, determine the total penalty Takahashi must pay. That is, if the number of rooms where the monster was not defeated is k, output k \times C.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq S \leq 10^9
• 1 \leq C \leq 10^9
• 1 \leq H_i \leq 10^9
• 0 \leq P_i \leq 10^9
• All input values are integers.

Sample Input 1

3 10 5
3 1
12 5
5 3

Sample Output 1

5

Sample Input 2

5 7 100
5 2
3 10
20 5
11 0
1 0

Sample Output 2

200

Sample Input 3

8 15 1000000000
10 8
5 3
20 0
8 7
10 10
100 50
1 0
9 5

Sample Output 3

2000000000

Problem Statement

Takahashi is working a part-time job harvesting apples at an orchard. The orchard has N apples, each located at a different height on the tree.

The i-th apple is at a height of H_i centimeters from the ground. Takahashi's height is T centimeters, but by stretching on his toes, he can reach up to a maximum height of T + K centimeters.

To harvest an apple, the apple's height must be within his reach (at most T + K centimeters). For apples he cannot reach, he would need to use a stepladder.

Since Takahashi finds using a stepladder troublesome, he wants to maximize the number of apples he can harvest by stretching alone. Fortunately, the trees in this orchard are planted in special mobile planters, and he can dig a hole of depth D centimeters in the ground to sink an entire planter (D is any non-negative integer). When a tree is sunk, the heights of all its apples are uniformly reduced by D.

However, there is a constraint that the height of the lowest apple must not become less than 1 centimeter. In other words, for all i, the condition H_i - D \geq 1 must be satisfied.

Find the maximum number of apples Takahashi can harvest by stretching alone.

Constraints

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

Sample Input 1

5 150 30
100 160 180 200 250

Sample Output 1

5

Sample Input 2

5 100 10
50 80 120 200 300

Sample Output 2

3

Sample Input 3

10 200 50
10 30 50 100 150 200 260 300 350 400

Sample Output 3

6

Sample Input 4

15 500 100
1 50 100 200 300 400 500 550 580 590 600 650 700 800 1000

Sample Output 4

11

Sample Input 5

1 1 0
1

Sample Output 5

1

Problem Statement

Takahashi is trying to plant N flower seeds in his garden.

Days are numbered as day 1, day 2, and so on. Starting from day 1, Takahashi decides for each day whether he can plant a seed or not.

According to the weather forecast, there are M rainy periods scheduled. The i-th rainy period lasts from day L_i to day R_i (inclusive). A day is a rainy day if it is included in at least one of the M rainy periods. On rainy days, the ground is muddy and work cannot be done, so no seeds can be planted. On days that are not rainy, exactly 1 seed is planted.

Note that rainy periods may overlap with each other or one may be entirely contained within another. Even in such cases, any day that falls within any rainy period is treated as a rainy day.

Since the rainy periods are finite, all days after the last rainy period ends will be sunny, and given enough days, all seeds will eventually be planted.

Determine on which day all N seeds will have been planted.

Constraints

• 1 \leq N \leq 10^9
• 0 \leq M \leq 10^5
• 1 \leq L_i \leq R_i \leq 10^{18}
• The rainy periods are not necessarily sorted
• All input values are integers

Sample Input 1

5 2
2 4
7 7

Sample Output 1

9

Sample Input 2

10 3
3 8
5 12
20 25

Sample Output 2

26

Sample Input 3

1000000000 3
1 500000000
500000000001 999999999999
1000000000002 1000000000002

Sample Output 3

1500000000

Problem Statement

Takahashi is working a part-time job at a weather observatory. His job is to analyze past temperature data.

The observatory has temperature records for N days. Each day is numbered from 1 to N, and the temperature on day i was A_i ℃.

Takahashi's supervisor asked him to investigate the temperature fluctuation range within specified periods. Here, the temperature fluctuation range of a certain period refers to the difference between the maximum and minimum temperatures within that period. For example, if the period consists of only 1 day, the fluctuation range is 0.

Q queries are given. In the i-th query (i = 1, 2, \ldots, Q), two integers L_i, R_i are specified. Takahashi must determine and report the temperature fluctuation range in the period from day L_i to day R_i (inclusive).

For each query, find the temperature fluctuation range within the specified period.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• -10^9 \leq A_i \leq 10^9
• 1 \leq L_i \leq R_i \leq N
• All input values are integers

Sample Input 1

5 3
20 18 25 22 19
1 3
2 5
4 4

Sample Output 1

7
7
0

Sample Input 2

7 5
-5 12 8 -3 15 7 10
1 7
3 6
1 2
2 4
5 7

Sample Output 2

20
18
17
15
8

Sample Input 3

10 8
1000000000 -1000000000 500 -200 300 0 999999999 -999999999 100 -100
1 2
1 10
3 6
7 8
5 5
2 8
4 9
1 1

Sample Output 3

2000000000
2000000000
700
1999999998
0
1999999999
1999999998
0