Problem Statement

Takahashi works at a shipping company. Today, he is in charge of loading cargo onto N trucks.

The items to be loaded onto truck i (1 \leq i \leq N) all have the same weight of P_i kilograms each. Takahashi loads these items one by one.

Every truck has a common weight capacity of T kilograms. When loading k items onto truck i, the total weight of the items must not exceed T kilograms. That is, P_i \times k \leq T must hold.

Furthermore, there is a common upper limit of R items on the number of items that can be loaded onto each truck. Even if the weight capacity has not been reached, loading for that truck ends once R items have been loaded.

For each truck i, determine the maximum number of items r_i that can be loaded while satisfying both the weight capacity and the item count limit.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq R \leq 10^9
• 1 \leq T \leq 10^{18}
• 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

3 5 20
3 5 7

Sample Output 1

5 4 2

Sample Input 2

4 10 15
1 4 8 16

Sample Output 2

10 3 1 0

Sample Input 3

10 100 1000
1 2 5 10 50 100 200 333 500 1001

Sample Output 3

100 100 100 100 20 10 5 3 2 0

Sample Input 4

20 1000000000 1000000000000000000
1 2 3 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 999999999 500000000 250000000 123456789 777777777 42 314159265 271828182

Sample Output 4

1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Input 5

1 1000000000 1
1000000000

Sample Output 5

0

Problem Statement

Takahashi and Aoki are participating in a marathon race. The marathon course has N checkpoints, and runners pass through them in order from the 1-st to the N-th.

The distance from the i-th checkpoint to the (i + 1)-th checkpoint is D_i meters (1 \leq i \leq N-1).

At the start of the race (time 0 seconds), both of them started simultaneously from the 1-st checkpoint.

Takahashi runs at a constant pace without taking any breaks, advancing at a speed of V meters per second. Therefore, the time at which Takahashi arrives at the i-th checkpoint (2 \leq i \leq N) is \displaystyle\frac{D_1 + D_2 + \cdots + D_{i-1}}{V} seconds. This value is not necessarily an integer.

On the other hand, Aoki runs at an uneven pace, and it is known that he arrives at the i-th checkpoint at exactly time T_i seconds. Here, T_1 = 0. Aoki's arrival times satisfy T_1 < T_2 < T_3 < \cdots < T_N.

For each checkpoint i from the 2-nd onward (2 \leq i \leq N), if Takahashi's arrival time is strictly less than Aoki's arrival time T_i, that is, if

D_1 + D_2 + \cdots + D_{i-1} < T_i \times V

holds, then Takahashi is said to have arrived first at checkpoint i ahead of Aoki. If they arrive at the same time, it does not count as arriving first.

Find all checkpoint numbers where Takahashi arrives first ahead of Aoki, and output them in ascending order. If there are no such checkpoints, output -1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq V \leq 10^9
• 1 \leq D_i \leq 10^9 (1 \leq i \leq N-1)
• T_1 = 0
• 1 \leq T_i \leq 10^{18} (2 \leq i \leq N)
• T_i < T_{i+1} (1 \leq i \leq N-1)
• All input values are integers.

Sample Input 1

5 10
30 50 40 60
4 10 15 20

Sample Output 1

2 3 4 5

Sample Input 2

4 5
100 100 100
10 20 30

Sample Output 2

-1

Sample Input 3

8 100
500 300 700 200 400 600 800
4 8 20 25 35 50 80

Sample Output 3

4 5 6 7 8

Problem Statement

Takahashi is heading to the station to catch the last train.

Takahashi is at coordinate 0 on a number line, and the station is at coordinate G (G > 0). Meanwhile, the last train is currently at coordinate M and is heading toward Takahashi's direction, toward the station. After arriving at the station, the train will depart and leave.

Normally, Takahashi can move at a speed of 1 per second, but by performing a "full sprint," his speed becomes D times faster for that second. However, due to stamina limitations, he can only sprint for a total of K seconds.

The last train is moving toward the station at a speed of V per second. Since the stopping time between the train's arrival at the station and its departure is instantaneous, if the last train passes through the station before Takahashi arrives, he cannot board the train.

Determine whether Takahashi can catch the last train if he uses his full sprints optimally.

Note that Takahashi and the last train start moving simultaneously. Takahashi can board the last train if the train has also arrived at the station by the moment Takahashi reaches the station (including the case where they arrive at the same time).

Constraints

• 1 \leq G \leq 10^9
• G \leq M \leq 10^{15}
• 2 \leq D \leq 10^9
• 0 \leq K \leq 10^9
• 1 \leq V \leq 10^9
• All inputs are integers

Sample Input 1

10 30 3 2 1

Sample Output 1

Yes

Sample Input 2

100 120 2 3 10

Sample Output 2

No

Sample Input 3

1000000000 1000000000000000 1000000000 1 1

Sample Output 3

Yes

Problem Statement

Takahashi works part-time at a delivery company. There are N delivery hubs in this area, numbered from 1 to N.

There are M roads in this area, and the i-th road connects hub A_i and hub B_i bidirectionally. Traveling along this road takes C_i minutes in either direction.

Today, Takahashi must depart from hub 1, where the headquarters is located, deliver a package to a customer at hub T, and then return to hub 1.

Specifically, Takahashi starts at hub 1, travels along roads in sequence, visits hub T at least once during the journey, and ultimately returns to hub 1. He may pass through other hubs along the way, and he is allowed to traverse the same road or visit the same hub multiple times. If the same road is traversed multiple times, the travel time for that road is added each time it is traversed.

Find the minimum possible total travel time of the roads traversed from the time Takahashi departs hub 1 until he returns to hub 1.

If no valid route exists (a route that departs from hub 1, visits hub T at least once, and returns to hub 1), output -1.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 2 \times 10^5
• 2 \leq T \leq N
• 1 \leq A_i < B_i \leq N (in particular, there are no self-loops)
• 1 \leq C_i \leq 10^9
• There is at most one road connecting any pair of hubs
• All input values are integers

Sample Input 1

4 4 3
1 2 5
2 3 3
3 4 2
1 4 10

Sample Output 1

16

Sample Input 2

5 3 5
1 2 100
3 4 50
4 5 30

Sample Output 2

-1

Sample Input 3

6 8 4
1 2 10
1 3 15
2 3 5
2 4 20
3 4 8
3 5 12
4 6 6
5 6 3

Sample Output 3

46

Problem Statement

Takahashi manages N flower beds arranged in a horizontal row. Each flower bed is numbered from 1 to N, and flower bed i initially stores C_i liters of water.

Takahashi will perform Q operations in order. Each operation is performed on the state resulting from all previous operations. There are 2 types of operations:

• Operation 1 (Watering): 1 l r v — Add v liters of water to each flower bed with a number from l to r, inclusive.
• Operation 2 (Query): 2 l r — Output the total amount of water stored across all flower beds with numbers from l to r, inclusive.

Find the answers to all operation 2 queries in the order they are given.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 0 \leq C_i \leq 10^4 (1 \leq i \leq N)
• For operation 1, 1 \leq l \leq r \leq N and 1 \leq v \leq 10^4
• For operation 2, 1 \leq l \leq r \leq N
• At least one operation 2 is given
• All input values are integers
• It is guaranteed that the answer to each operation 2 is between 0 and 2^{63} - 1 (the maximum value of a signed 64-bit integer), inclusive

Sample Input 1

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

Sample Output 1

14
15
23

Sample Input 2

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

Sample Output 2

30
23
49
62

Sample Input 3

10 10
10 20 30 40 50 60 70 80 90 100
2 1 10
1 1 5 10
2 1 5
2 6 10
1 3 8 20
2 1 10
1 1 10 5
2 1 10
2 5 5
2 1 1

Sample Output 3

550
200
400
720
770
85
25