Problem Statement

Takahashi manages N flower beds.

The i-th flower bed currently contains A_i liters of water. Takahashi wants to make the amount of water in all flower beds equal.

Takahashi can perform the following operation any number of times (possibly 0 times):

• Choose one flower bed and add 1 liter of water to it. This operation costs 1 yen. The same flower bed may be chosen multiple times.

Since water cannot be removed from a flower bed, the amount of water in each flower bed after the operations will be at least the amount before the operations.

Takahashi's goal is to make the amount of water in all flower beds equal to some integer value. He is free to choose the target value.

Find the minimum cost (in yen) required to achieve this goal.

Constraints

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

Sample Input 1

3
2 5 3

Sample Output 1

5

Sample Input 2

5
10 10 10 10 10

Sample Output 2

0

Sample Input 3

6
1 100 50 25 75 200

Sample Output 3

749

Problem Statement

Takahashi is in charge of organizing a warehouse. There are N items of luggage lined up in a row in the warehouse, and the weight of the i-th item from the left is A_i.

Takahashi uses a truck to carry out the luggage. Takahashi can repeat the following carrying-out operation any number of times (including 0 times). Once an item has been carried out, it does not return to the row.

Carrying-out operation:

From the current remaining row of items, choose one contiguous interval consisting of 1 or more consecutive items in that row. However, the total weight of the items in the chosen interval must be at most K. Remove all items in the chosen interval from the row and carry them out. After the items are removed, the remaining items close the gaps while maintaining their original relative order and form a row again (if no items remain, the row becomes empty).

Note that only one interval can be chosen per carrying-out operation, and the upper limit on the total weight for each carrying-out operation is K every time (regardless of the amount carried out in previous operations).

For example, if the items are arranged as [A_1, A_2, A_3, A_4, A_5], and A_2 + A_3 \leq K, then in the first carrying-out operation, A_2 and A_3 can be carried out together. After this, the row becomes [A_1, A_4, A_5]. At this point, A_1 and A_4, which were not adjacent in the original row, are now adjacent, so in the next carrying-out operation, A_1 and A_4 can be selected together as one interval (provided that A_1 + A_4 \leq K).

Find the maximum number of items Takahashi can carry out when he tries to carry out as many items as possible.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{18}
• 1 \leq A_i \leq 10^{18}
• All input values are integers

Sample Input 1

5 4
3 1 3 1 3

Sample Output 1

5

Sample Input 2

3 2
3 3 3

Sample Output 2

0

Sample Input 3

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

Sample Output 3

10

Sample Input 4

20 15
7 3 12 5 8 1 6 14 2 9 4 11 3 7 10 2 13 5 8 6

Sample Output 4

20

Sample Input 5

1 1000000000000000000
1000000000000000000

Sample Output 5

1

Problem Statement

Takahashi will take N quizzes. His score on the i-th quiz is H_i points. Scores can be negative.

Takahashi can attend "supplementary lessons" any number of times from 0 to K times, inclusive. Each time he attends a supplementary lesson, he chooses one of the N quizzes and adds P to that quiz's score. He may choose the same quiz multiple times, and he may choose any quiz.

After all supplementary lessons have been assigned, the final score of each quiz is checked. A quiz whose final score is 0 or less is considered a "failing grade." Note that a quiz with a score of exactly 0 is also a failing grade.

Takahashi wants to minimize the number of quizzes with failing grades. Find the minimum number of quizzes with failing grades when the supplementary lessons are assigned optimally.

Constraints

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

Sample Input 1

5 3 2
-3 1 -1 0 5

Sample Output 1

1

Sample Input 2

4 2 3
-5 -2 3 -8

Sample Output 2

2

Sample Input 3

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

Sample Output 3

0

Sample Input 4

10 5 4
-7 -3 1 -15 0 -1 8 -10 -4 2

Sample Output 4

3

Sample Input 5

1 0 1
0

Sample Output 5

1

Problem Statement

Takahashi is trying to photograph a parade of N floats moving along a straight road.

He will choose one shooting day from the integer days between day 0 and day D (inclusive). Takahashi wants to make the camera's frame width as small as possible while fitting all the floats in the frame.

The center coordinate of float i on day d is X_i + V_i \cdot d. Here, X_i is the center coordinate on day 0, and V_i is the movement speed per day (if negative, the float moves in the direction of decreasing coordinates). Float i has a half-width of L_i extending in both directions from its center, so it occupies the interval

[X_i + V_i \cdot d - L_i, \ X_i + V_i \cdot d + L_i]

on the road.

The frame width required to capture all floats on day d is

F(d) = \max_{1 \le i \le N}(X_i + V_i \cdot d + L_i) - \min_{1 \le i \le N}(X_i + V_i \cdot d - L_i)

However, Aoki has sent Q modification instructions regarding the parade operation plan. In the j-th modification, the initial coordinate, movement speed, and half-width of float P_j are changed to A_j, B_j, C_j respectively.

Let version 0 be the initial data, and version j (1 \le j \le Q) be the data obtained by applying the j-th modification to version j-1. Denoting the initial coordinate, movement speed, and half-width of float i in version t as X_i^{(t)}, V_i^{(t)}, L_i^{(t)} respectively, the frame width on day d in version t is

F_t(d) = \max_{1 \le i \le N}(X_i^{(t)} + V_i^{(t)} \cdot d + L_i^{(t)}) - \min_{1 \le i \le N}(X_i^{(t)} + V_i^{(t)} \cdot d - L_i^{(t)})

For each version t (0 \le t \le Q), find the minimum frame width when the shooting day is chosen optimally:

G_t = \min_{\substack{d \in \mathbb{Z} \\ 0 \le d \le D}} F_t(d)

The shooting day can be chosen independently and optimally for each version.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq D \leq 10^9
• 0 \leq Q \leq 10^5
• N(Q+1) \leq 5 \times 10^5
• |X_i| \leq 10^6 (1 \leq i \leq N)
• |V_i| \leq 10^6 (1 \leq i \leq N)
• 1 \leq L_i \leq 10^6 (1 \leq i \leq N)
• 1 \leq P_j \leq N (1 \leq j \leq Q)
• |A_j| \leq 10^6 (1 \leq j \leq Q)
• |B_j| \leq 10^6 (1 \leq j \leq Q)
• 1 \leq C_j \leq 10^6 (1 \leq j \leq Q)
• All input values are integers.
• Under these constraints, all values to be output fit in a signed 64-bit integer.

Sample Input 1

2 5 2
0 1 1
10 -1 2
1 2 0 1
2 5 1 1

Sample Output 1

4
6
5

Sample Input 2

3 4 0
0 0 1
5 -1 2
-3 2 1

Sample Output 2

5

Sample Input 3

6 30 5
-10 3 2
15 -2 3
0 0 1
25 -1 4
-20 4 2
8 1 5
3 5 -3 2
6 -5 2 1
1 12 -1 3
4 0 0 6
2 -15 5 2

Sample Output 3

24
34
34
34
20
20

Sample Input 4

12 1000000000 10
1000000 -1000000 1000000
-1000000 1000000 999999
0 500000 12345
500000 0 777777
-500000 -250000 333333
123456 654321 111111
-654321 -123456 222222
999999 -1 1
-999999 1 2
314159 -271828 31415
-271828 314159 92653
42 -42 1000000
1 -1000000 1000000 1
12 1000000 -1000000 1000000
6 0 0 500000
9 500000 500000 10
4 -999999 999999 999999
7 12345 -54321 123456
2 222222 -333333 444444
11 -1 1 1
5 1000000 0 1000000
10 -1000000 -1000000 999999

Sample Output 4

2361110
2361110
2361110
2361110
2361110
2083343
2083343
2083343
2083343
3000000
3999999

Sample Input 5

2 1 0
-1000000 -1000000 1000000
1000000 1000000 1000000

Sample Output 5

4000000

Problem Statement

Takahashi is researching string search algorithms. His current topic is pattern matching on circular strings.

You are given a string S consisting of lowercase English letters. Let N be the length of S. This string is considered to be arranged in a circular manner. That is, the first character follows immediately after the last character of S.

You are also given a pattern string T consisting of lowercase English letters. Let M be the length of T.

The positions of each character in S are represented as 0, 1, \ldots, N-1 (0-indexed). For each position i (0 \leq i < N), define the string R_i as the string obtained by reading M consecutive characters on the circle starting from position i. Specifically, for each j (0 \leq j < M), the j-th character (0-indexed) of R_i is the character at position (i + j) \bmod N in S.

Note that this definition applies even when M > N. In that case, the circle is traversed multiple times, and characters at the same position are referenced repeatedly.

For each of the N starting positions i = 0, 1, \ldots, N-1, determine whether R_i = T, and find the number of starting positions where R_i = T.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq M \leq 5 \times 10^5
• S is a string of length N consisting of lowercase English letters only
• T is a string of length M consisting of lowercase English letters only

Sample Input 1

ababc
abc

Sample Output 1

1

Sample Input 2

abc
bcab

Sample Output 2

1

Sample Input 3

abracadabracadabra
cadabra

Sample Output 3

2

Sample Input 4

abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde
deabcdeabcdeabcdeabcdeabc

Sample Output 4

20

Sample Input 5

a
a

Sample Output 5

1