Problem Statement

Takahashi is playing an RPG game.

In this game, there is a dungeon consisting of N rooms arranged in a row. The rooms are numbered 1, 2, \ldots, N from the entrance toward the back, and each room has one monster waiting inside. The strength of the monster in room i (1 \leq i \leq N) is V_i.

Takahashi controls a slime with an initial strength of W to conquer this dungeon. The slime visits each room exactly once in order from room 1 to room N, visiting them in the order 1, 2, \ldots, N. It cannot turn back or skip rooms.

The "current strength" of the slime at the time it visits a room is defined as the initial strength W plus the total strength of all monsters absorbed before visiting that room.

When the slime visits room i, exactly one of the following two cases occurs:

• If the monster's strength V_i is less than or equal to the slime's current strength (including the case where V_i equals the slime's current strength), the slime absorbs the monster. V_i is immediately added to the slime's strength, and the value after the addition becomes the current strength for subsequent rooms.
• If the monster's strength V_i is strictly greater than the slime's current strength, the slime cannot absorb the monster, and the slime's strength does not change.

Find the slime's strength after it has visited all rooms from room 1 to room N in order.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq W \leq 10^9
• 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.
• It is guaranteed that the answer fits in less than 2^{63} (it fits in a signed 64-bit integer). However, it may exceed the range of a signed 32-bit integer (2^{31}-1 or less).

Sample Input 1

5 3
2 4 1 3 7

Sample Output 1

20

Sample Input 2

8 5
3 6 2 10 4 8 1 20

Sample Output 2

59

Sample Input 3

10 1
1 3 2 5 100 4 6 3 2 1000000000

Sample Output 3

19

Problem Statement

Takahashi works at a meteorological observatory and records the daily average temperature. Temperatures are recorded as simplified integer values ranging from 1 to 9 (9 levels).

One day, Takahashi decided to analyze temperature data from a consecutive N-day period in the past. Takahashi focuses on the total temperature over consecutive K-day windows, and wants to calculate the total for every consecutive K-day window, then find the difference between the maximum and minimum values among them. A larger difference indicates more intense temperature fluctuations during the period.

Specifically, given the temperature records for N days as A_1, A_2, \dots, A_N, there are N - K + 1 total values of consecutive K-day windows. That is, for i = 1, 2, \dots, N - K + 1, we compute:

S_i = \sum_{j=0}^{K-1} A_{i+j}

Find the difference between the maximum and minimum values among S_1, S_2, \dots, S_{N-K+1}.

Constraints

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

Sample Input 1

5 3
2 5 3 1 4

Sample Output 1

2

Sample Input 2

10 4
3 1 4 1 5 9 2 6 5 3

Sample Output 2

13

Sample Input 3

20 5
1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9

Sample Output 3

8

Problem Statement

There are N cities along a straight road running from west to east. The i-th city is located at distance X_i from the western end (the cities are not necessarily numbered from west to east).

Takahashi is trying to build a disaster-resistant communication network by installing bidirectional communication lines between these cities. A communication line can be installed directly between any two cities, and the cost of installing a communication line between city i and city j is |X_i - X_j|. However, the following conditions apply:

• Multiple communication lines cannot be installed between the same pair of cities.
• Each communication line connects only the two cities at its endpoints. Even if another city is geographically located between the two cities, it is not connected to that line.

The constructed network must satisfy the following disaster resilience condition:

• For any single city v, even if city v and all communication lines directly connected to city v are removed from the network, all remaining cities can still communicate with each other.

Here, "can communicate with each other" means that in the network consisting of the remaining cities and remaining communication lines, any two cities can be reached from one another either through a direct communication line or by relaying through other cities.

Find the minimum total cost of installing communication lines needed to construct a network satisfying this condition.

Constraints

• 3 \leq N \leq 10^6
• 0 \leq X_i \leq 10^9
• X_i \neq X_j (i \neq j)
• All inputs are integers

Sample Input 1

4
0 2 5 9

Sample Output 1

18

Sample Input 2

5
10 1 7 3 20

Sample Output 2

38

Sample Input 3

10
42 5 100 17 63 88 29 74 1 56

Sample Output 3

198

Sample Input 4

25
1000 250 4300 120 9800 7600 3150 640 8750 5200 60 7000 1500 2400 9999 3600 8100 4700 5900 9300 2050 6800 7350 1110 5550

Sample Output 4

19878

Sample Input 5

3
0 1000000000 500000000

Sample Output 5

2000000000

Problem Statement

At Takahashi's company, they need to order bento boxes for the company trip. Each bento is made in a custom-order style by combining 3 types of parts: a main dish, a side dish, and a dessert.

There are A choices for the main dish, B choices for the side dish, and C choices for the dessert. A bento is represented as a triplet (main dish, side dish, dessert). Since the main dish, side dish, and dessert can each be chosen independently, there are A \times B \times C types of bento in total, and any of them can be ordered.

N employees will participate in the company trip. Since the bentos are custom-made, they want to assign a distinct bento to each of the N employees so that no two employees receive the same bento.

Here, the N employees are distinguished from each other. That is, even if the set of N chosen bentos is the same, if the assignment of which employee gets which bento differs, it is counted as a different assignment.

Determine how many ways there are to assign bentos to the N employees.

Since the answer can be very large, output the remainder when divided by 10^9 + 7.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq A \leq 10^6
• 1 \leq B \leq 10^6
• 1 \leq C \leq 10^6
• N \leq A \times B \times C (that is, it is guaranteed that the total number of bentos is at least the number of employees)
• All inputs are integers

Sample Input 1

2 2 1 2

Sample Output 1

12

Sample Input 2

3 2 2 1

Sample Output 2

24

Sample Input 3

10 3 3 3

Sample Output 3

590793709

Sample Input 4

100000 100 100 100

Sample Output 4

431436174

Sample Input 5

1 1 1 1

Sample Output 5

1

Problem Statement

Takahashi is exploring a cave. The cave is represented as a grid with H rows and W columns.

Each cell is one of the following:

• S: Takahashi's starting point
• G: The exit
• O: A passable normal corridor
• V: A passable but water-filled corridor
• X: An impassable wall

A connected component formed by connecting only V cells through up/down/left/right adjacency is called an "underground waterway."

Takahashi can perform the following actions in any order:

• Make a normal move to an adjacent passable cell (up, down, left, or right). A normal move takes 1 minute.
• If the destination of a normal move is a V cell, it takes an additional 1 minute due to wading through water.
• Even if he enters the same V cell or the same underground waterway multiple times, the additional 1 minute is incurred each time he enters a V cell via a normal move.
• If the current cell is V, he can ride the water current to move to any V cell belonging to the same underground waterway in 0 minutes.
• Since this movement is not a normal move, the additional 1 minute is not incurred even though the destination is a V cell.

Find the minimum time required to move from the starting point S to the exit G.

If it is impossible to reach the exit, output NO.

Constraints

• 1 \leq H \leq 10^5
• 1 \leq W \leq 10^5
• H \times W \leq 2 \times 10^5
• C_i is a string of length W consisting only of S, G, O, V, X
• There is exactly one S in the entire grid
• There is exactly one G in the entire grid

Sample Input 1

3 5
SOVVG
OOXXO
OOOOO

Sample Output 1

4

Sample Input 2

3 3
SXX
XXX
XXG

Sample Output 2

NO

Sample Input 3

8 12
SOVVOOOXOOOO
XOXXOXOXOXXO
XOVVVXOVVVXO
XOXOXXOXOXOO
XOXOOOOVOXVX
XOVXXXXVOXVX
XOOOOVVVOXVO
XXXXOOOOOOGX

Sample Output 3

16

Sample Input 4

15 20
SOVVVVVOOOOOOOOOOOOO
OXXXXXXOXOOOXOOOXXXO
OOVVVXXOXVVOXOVVVVVO
OXXVXXXOXVXXXXOOXXVO
OXXVVVVOXVOOOOXOXXVO
OOOXXXOOXVXXXXXOXXVO
XVVOOOOXVVVVVVXOXXVO
OVXXXXXXOXXXXOXOXXVO
OVVVVVVOOOOXXOXOOOVO
OXXXXXXOXXOXXOXVXXVO
OOOOOOOOVVOOOOXVXXVO
OXXXXXOXXXXXXXVVXXVO
OVVVVVOOOOOOOOOVVVVO
OXXXXXXXXXXXXXXOXXVO
OOOOOOOOOOXXXXOOOVVG

Sample Output 4

15

Sample Input 5

1 2
SG

Sample Output 5

1