Problem Statement

Takahashi is in charge of inspecting goods in a large warehouse. In the warehouse, N shelves are lined up in a straight line, numbered 1 to N in order. Moving from shelf i to shelf j takes |i - j| \times D minutes, where D is a positive integer representing the travel time (in minutes) between adjacent shelves.

Each shelf has goods to be inspected, and inspecting the goods on shelf i takes T_i minutes. The inspection must be performed while standing in front of the shelf; it cannot be done while moving. Furthermore, Takahashi must start moving to the next shelf only after finishing the inspection of the current shelf; inspection and movement cannot be performed simultaneously. Although he may pass by other shelves during movement, merely passing by does not count as inspecting them. To inspect them, he must move to that shelf again and stop.

Takahashi is initially in front of shelf S. He can freely choose which shelf to inspect first. Takahashi moves from the front of shelf S to the first shelf to be inspected, and performs the inspection there. If he chooses to inspect shelf S first, he can start the inspection immediately with a travel time of 0 minutes.

Takahashi must inspect the goods on all N shelves exactly once. The order in which he inspects the shelves can be chosen freely. The work is complete once the inspection of the last shelf is finished, and he does not need to return to his starting position.

Find the minimum total time (the sum of all travel times and all inspection times) required to finish inspecting the goods on all shelves.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq D \leq 10^9
• 1 \leq S \leq N
• 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

4 2 2
3 1 4 2

Sample Output 1

18

Sample Input 2

5 3 5
2 8 1 6 4

Sample Output 2

33

Sample Input 3

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

Sample Output 3

144

Sample Input 4

30 100000000 17
12 999999999 345678901 1 500000000 234567890 876543210 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999998 123456789 987654321 314159265 271828182 161803398 141421356 173205080 223606797 707106781 1000000000 42 424242424 606060606 808080808

Sample Output 4

18099415856

Sample Input 5

1 1000000000 1
1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi is growing N potted plants arranged in a row. They are numbered 1, 2, \ldots, N from left to right, and plant i currently contains A_i milliliters of water.

Due to the summer heat, water evaporates from all potted plants every day. Specifically, as each day passes, the amount of water in each plant decreases by D milliliters (however, the amount of water will never drop below 0; it stops at 0).

Meanwhile, the mischievous Aoki is planning to ruin Takahashi's flowerbed. Aoki can perform an action at most once at the beginning of each day: he can choose any single potted plant and set its water amount to 0 (a prank of discarding the water). Aoki can perform this action up to K times in total. He may choose the same potted plant multiple times. Aoki's pranks are executed before the evaporation for that day occurs.

Takahashi has no way to refill the water, nor can he prevent evaporation or Aoki's pranks. He wants to keep the number of potted plants with at least 1 milliliter of water remaining after M days (after all M days of evaporation and Aoki's pranks are completed) as large as possible.

Aoki acts optimally to achieve the worst possible outcome for Takahashi. In other words, Aoki chooses the targets of his pranks to minimize the number of potted plants with at least 1 milliliter of water remaining after M days.

Find the number of potted plants with at least 1 milliliter of water remaining after M days, assuming Aoki acts optimally.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq M \leq 10^9
• 1 \leq D \leq 10^9
• 0 \leq K \leq N
• 0 \leq A_i \leq 10^{18}
• All input values are integers.

Sample Input 1

5 3 2 1
1 5 6 7 10

Sample Output 1

1

Sample Input 2

4 2 3 0
0 5 6 7

Sample Output 2

1

Sample Input 3

12 10 7 3
0 1 69 70 71 100 150 35 80 500 70 72

Sample Output 3

3

Sample Input 4

40 123456789 98765 15
0 100 1000000000 5000000000 10000000000 12190000000000 12193209765584 12193209765585 12193209765586 15000000000000 20000000000000 999999999999999999 123456789012345678 42 7777777777777 8888888888888 9999999999999 11111111111111 22222222222222 33333333333333 44444444444444 55555555555555 66666666666666 77777777777777 88888888888888 99999999999999 314159265358979323 271828182845904523 1000000000000000000 999999999999999998 12193209765583 12193209765584 12193209765585 1 2 3 4 5 6 7

Sample Output 4

2

Sample Input 5

1 1 1 1
1000000000000000000

Sample Output 5

0

Problem Statement

Takahashi has assembled a device consisting of N gears arranged in a row. The gears are numbered from 1 to N in order, and adjacent gears i and i+1 (1 \leq i \leq N-1) mesh with each other.

Each gear i (1 \leq i \leq N) has T_i teeth. When gear i and gear i+1 are meshed, if one rotates, the other rotates accordingly. Since two meshing gears advance the same number of teeth, while gear i makes one full rotation (T_i teeth), gear i+1 rotates \frac{T_i}{T_{i+1}} times. In other words, the ratio of the number of rotations of gear i to gear i+1 is T_{i+1} : T_i (a gear with more teeth rotates more slowly).

Each gear has exactly one marked tooth. When a gear rotates exactly a positive integer number of times, all teeth return to their original positions, so the marked tooth also returns to its original position. Conversely, if the number of rotations is not a positive integer, the mark does not return to its original position. Note that adjacent gears rotate in opposite directions, but whether the mark returns to its original position depends only on the number of rotations, not on the direction of rotation.

When gear 1 is rotated, gears 2, 3, \ldots, N also rotate accordingly through the meshing. Let R (R > 0) be the number of rotations of gear 1. Find the smallest positive R such that the marks on all gears simultaneously return to their respective original positions. Here, the number of rotations is a positive real number representing how many times the gear has rotated, regardless of the direction of rotation.

It can be proven that R is always a positive rational number. Express R as an irreducible fraction \frac{P}{Q} (P, Q are positive integers, \gcd(P, Q) = 1), and output P and Q separated by /. If R is an integer, output it in the format P/1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq T_i \leq 10^9
• All inputs are integers.
• It is guaranteed that when the answer is expressed as an irreducible fraction \frac{P}{Q}, both P and Q are at most 10^{18}.

Sample Input 1

3
8 12 6

Sample Output 1

3/1

Sample Input 2

2
6 10

Sample Output 2

5/1

Sample Input 3

10
18 24 30 45 60 72 90 120 150 180

Sample Output 3

100/1

Sample Input 4

30
840 1260 1680 2100 2520 3150 3360 4200 5040 6300 6720 7560 8400 10080 12600 15120 16800 20160 25200 27720 30240 33600 37800 42000 50400 55440 60480 75600 83160 100800

Sample Output 4

19800/1

Sample Input 5

1
1000000000

Sample Output 5

1/1

Problem Statement

Takahashi runs a fruit shop.

The shop has N types of fruits, one of each, and the i-th fruit (1 \leq i \leq N) has a cost price C_i and a selling price P_i. Takahashi wants to select some of these fruits to display in today's recommended section. Each fruit is either selected or not selected, and at least 1 fruit must be selected.

However, if the price range of the fruits displayed in the recommended section varies too much, customers will be confused. Therefore, the difference between the maximum and minimum selling prices among the selected fruits must be at most D, where D is a non-negative integer given in the input. Note that if only 1 fruit is selected, the maximum and minimum selling prices are equal, so the difference is 0, and this condition is always satisfied.

The profit of each fruit is determined by the selling price minus the cost price, P_i - C_i. The profit can be negative.

Takahashi wants to maximize the total profit of the selected fruits while satisfying the above condition. Note that even if the profit of every fruit is negative, at least 1 fruit must be selected.

Find the maximum total profit.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq D \leq 10^9
• 1 \leq C_i \leq 10^9
• 1 \leq P_i \leq 10^9
• All inputs are integers.

Sample Input 1

4 3
3 5
4 7
10 9
2 12

Sample Output 1

10

Sample Input 2

3 10
10 5
8 6
20 13

Sample Output 2

-2

Sample Input 3

10 5
8 10
5 12
20 15
1 17
9 20
25 22
7 23
30 26
10 27
15 30

Sample Output 3

33

Sample Input 4

25 100
1000 500
100 550
200 610
800 650
300 700
900 720
150 760
500 790
400 810
1200 850
350 900
600 940
100 980
1100 1020
700 1050
200 1100
1300 1150
250 1190
800 1230
300 1280
900 1320
100 1360
1500 1400
500 1450
200 1500

Sample Output 4

2660

Sample Input 5

1 0
1000000000 1

Sample Output 5

-999999999

Problem Statement

Takahashi manages N transmitters. The transmitters are numbered from 1 to N.

Each transmitter i has two operating modes: in Mode A, it outputs a signal value V_i, and in Mode B, it outputs a signal value W_i. Here, both V_i and W_i are non-negative integers. Takahashi first sets the operating mode of each transmitter to either A or B. Once a mode is set, it cannot be changed afterwards.

If some of the transmitters are operated simultaneously, the XOR (bitwise exclusive OR) of their output signal values is obtained as the combined signal. The set of transmitters to operate can be chosen freely, and the combined signal when the empty set is chosen is 0.

Takahashi has M target signal values T_1, T_2, \ldots, T_M. He operates them according to the following procedure:

1. First, decide the operating mode of each transmitter to be either A or B (this decision is made only once and cannot be changed afterwards).
2. Then, for each of the M target signal values, choose a subset of transmitters to operate so that the combined signal of the subset matches the target signal value. The subset of transmitters to operate may differ for each target signal value.

Takahashi wants to be able to realize all M target signal values. That is, after appropriately deciding the operating modes in Step 1, he wants to ensure that for every target signal value T_j (1 \leq j \leq M), there exists a subset of transmitters whose combined signal is equal to that value.

Find the number of such operating mode decisions (among the 2^N possible assignments of A or B to each transmitter) that satisfy the condition, modulo 10^9 + 7.

Constraints

• 1 \leq N \leq 15
• 1 \leq M \leq 100
• 0 \leq V_i \leq 2^{60} - 1 (1 \leq i \leq N)
• 0 \leq W_i \leq 2^{60} - 1 (1 \leq i \leq N)
• 0 \leq T_j \leq 2^{60} - 1 (1 \leq j \leq M)
• All input values are integers.

Sample Input 1

2 2
1 2
2 3
1 3

Sample Output 1

3

Sample Input 2

1 2
1 2
1 3

Sample Output 2

0

Sample Input 3

8 12
5 9
3 6
10 12
7 1
15 8
4 14
2 11
13 0
0 1 2 3 5 8 13 21 31 6 10 15

Sample Output 3

0

Sample Input 4

15 25
1 1099511627776
2 1099511627777
4 281474976710656
8 281474976710664
16 1125899906842624
32 1125899906842656
64 72057594037927936
128 72057594037928064
256 1152921504606846975
512 1152921504606846463
1024 123456789012345
2048 98765432109876
4096 555555555555555
8192 333333333333333
16384 777777777777777
0 1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 1099511627776 281474976710656 1125899906842624 72057594037927936 1152921504606846975 123456789012345 98765432109876 555555555555555 777777777777777

Sample Output 4

0

Sample Input 5

1 1
0 1152921504606846975
0

Sample Output 5

2