Problem Statement

Takahashi will print N documents. The i-th document has A_i pages, and he prints B_i pages per sheet of paper. The last sheet may contain fewer than B_i pages.

For each document, find the number of sheets needed.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 1000
• 1 \leq B_i \leq 1000
• All input values are integers.

Sample Input 1

3
7 2
10 5
5 3

Sample Output 1

4
2
2

Sample Input 2

1
1 1

Sample Output 2

1

Sample Input 3

2
9 2
3 2

Sample Output 3

5
2

Sample Input 4

2
9 2
1 2

Sample Output 4

5
1

Sample Input 5

3
7 2
10 5
6 3

Sample Output 5

4
2
2

Problem Statement

Takahashi's garden consists of N squares arranged in a row. The state of the i-th square from the left is represented by the i-th character of a string S. # means that the square has a mole hole, and . means that it does not.

Find the length of the longest contiguous segment of squares that have holes. If there are no holes at all, print 0.

Constraints

• 1 \leq N \leq 100
• S is a string of length N consisting of # and .

Sample Input 1

8
.##.###.

Sample Output 1

3

Sample Input 2

5
.....

Sample Output 2

0

Sample Input 3

3
#.#

Sample Output 3

1

Sample Input 4

45
#.###.#.###.###.#.######.##..##.#..###..##.##

Sample Output 4

6

Sample Input 5

15
.##..########.#

Sample Output 5

8

Problem Statement

At an amusement park, there is a Ferris wheel with N gondolas arranged in a circle. The gondolas are numbered from 1 to N, and the beauty of gondola i (1 \leq i \leq N) is A_i. Since the gondolas are arranged in a circle, gondola 1 comes after gondola N.

From the boarding platform, exactly M consecutive gondolas along the circumference are visible. Since the Ferris wheel can be rotated to any position, you can freely choose which set of gondolas is visible.

When the Ferris wheel is rotated to the optimal position, find the maximum possible sum of the beauty values of the M gondolas visible from the boarding platform.

Constraints

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

Sample Input 1

5 3
1 2 3 4 5

Sample Output 1

12

Sample Input 2

4 2
-5 -2 -3 -4

Sample Output 2

-5

Sample Input 3

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

Sample Output 3

21

Sample Input 4

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

Sample Output 4

36

Sample Input 5

1 1
-1000000000

Sample Output 5

-1000000000

Problem Statement

Takahashi is playing a game. This game has N stages, numbered Stage 1 through Stage N.

For each stage, Takahashi can freely choose whether to clear it or not (he may choose not to clear any stages at all).

The score at the start of the game is 0, and the final score is calculated based on the cleared stages as follows:

• If he clears Stage i (1 \le i \le N), A_i is added to the score (if A_i is negative, the score decreases).
• For each i (1 \le i \le N - 1), if he clears both Stage i and Stage i + 1, an additional C is added to the score as a combo bonus (for example, if he clears all of Stages 1, 2, 3, a bonus is granted for each of the pairs (1, 2) and (2, 3), adding a total of 2C).

Find the maximum possible final score Takahashi can obtain by optimally choosing which stages to clear.

Constraints

• 1 \le N \le 10^6
• 0 \le C \le 10^9
• -10^9 \le A_i \le 10^9 (1 \le i \le N)
• All input values are integers.

Sample Input 1

4 3
5 -4 6 -10

Sample Output 1

13

Sample Input 2

3 2
-5 -3 -4

Sample Output 2

0

Sample Input 3

12 10
-3 8 12 -15 7 0 -4 19 22 -30 15 -1

Sample Output 3

150

Sample Input 4

30 100
10 -20 30 -40 50 -60 70 -80 90 -100 110 -120 130 -140 150 -160 170 -180 190 -200 210 -220 230 -240 250 -260 270 -280 290 -300

Sample Output 4

3150

Sample Input 5

1 1000000000
-1000000000

Sample Output 5

0

Problem Statement

Takahashi manages the sales of N stores lined up in a shopping street. The stores are numbered from 1 to N from left to right, and the initial monthly sales of store i is V_i yen. Initially, all stores are open.

Takahashi performs Q operations in order. Each operation is one of the following 3 types:

• Operation 1 (1 l r x): Due to a seasonal campaign, increase the sales of all open stores from store l to store r by x yen. Even if closed stores are included in this range, their sales do not change.

• Operation 2 (2 p): Store p closes. The sales of a closed store are finalized at the value at that point in time (Operation 2 itself does not change the sales value). A closed store is not affected by sales increases from subsequent Operation 1s. It is guaranteed that store p is open at the time of this operation.

• Operation 3 (3 k): Determine and output a value according to the following procedure:

1. When the currently open stores are listed in increasing order of their numbers, let j be the number of the k-th store.
2. Among stores from store 1 to store j, collect all stores that have already closed.
3. For each of those closed stores, determine the sales at the time of closure (the sales at the time Operation 2 was performed on it), and output the total. If there are no such closed stores, output 0.

This total is called the "cumulative closed sales amount."

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 0 \leq V_i \leq 10^9 (1 \leq i \leq N)
• For Operation 1: 1 \leq l \leq r \leq N, 1 \leq x \leq 10^4
• For Operation 2: 1 \leq p \leq N, and store p is open at that time
• For Operation 3: 1 \leq k \leq (the number of currently open stores) (in particular, at least one store is open when Operation 3 is given)
• All input values are integers
• It is guaranteed that the values to be output are less than 2^{63} (they fit in a 64-bit signed integer)

Sample Input 1

5 9
10 20 30 40 50
3 1
1 2 4 5
2 3
3 2
1 1 5 10
2 2
3 2
2 1
3 1

Sample Output 1

0
0
70
90

Sample Input 2

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

Sample Output 2

3
3
3

Sample Input 3

10 18
100 200 300 400 500 600 700 800 900 1000
1 1 5 10
2 4
3 4
1 3 8 20
2 7
3 6
2 1
1 1 10 5
3 1
2 5
3 3
1 6 10 100
2 10
3 5
2 2
3 1
1 1 10 1
3 4

Sample Output 3

410
1130
110
1055
1775
325
1990

Sample Input 4

20 35
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
1 1 20 100
2 10
2 1
3 1
1 5 15 50
2 7
3 6
1 1 8 10
2 8
3 5
2 20
1 10 20 200
3 12
2 15
3 10
1 1 20 1
2 2
2 3
3 1
1 4 12 30
2 12
3 7
2 4
2 5
3 1
1 1 20 9999
2 19
3 8
2 6
3 1
2 9
2 11
3 3
1 13 18 123
3 5

Sample Output 4

105
290
105
640
640
352
1328
729
2130
11334
33010
33010

Sample Input 5

1 4
1000000000
3 1
1 1 1 10000
3 1
2 1

Sample Output 5

0
0