Problem Statement

Takahashi is in charge of inspecting temperature sensors installed in a factory. The factory has N temperature sensors arranged in a row, and each sensor is numbered from 1 to N in the order they are arranged. Sensors whose numbers differ by exactly 1 are adjacent to each other.

The temperature measured by the i-th sensor is A_i.

During the inspection, a "local temperature index" M_i is calculated for each sensor. The local temperature index M_i of sensor i is the sum of the measurements of sensor i itself and all sensors adjacent to it, defined as follows:

• When 2 \leq i \leq N-1: M_i = A_{i-1} + A_i + A_{i+1}
• When i = 1: M_1 = A_1 + A_2
• When i = N: M_N = A_{N-1} + A_N

Note that when N = 2, no sensor falls under the second condition, and only the first and third conditions apply.

Takahashi needs to report the maximum value among the local temperature indices of all sensors.

Given the measurements of N sensors, find the maximum value of the local temperature indices \displaystyle \max_{1 \leq i \leq N} M_i.

Constraints

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

Sample Input 1

5
3 1 4 1 5

Sample Output 1

10

Sample Input 2

2
100 -50

Sample Output 2

50

Sample Input 3

10
-5 12 8 -3 20 15 -10 7 25 18

Sample Output 3

50

Problem Statement

Takahashi is preparing a champagne tower for a party. However, this time it is a simple structure with N glasses arranged in a single column from top to bottom. The glasses are numbered from the top as level 1, level 2, \ldots, level N.

The capacity of the glass at level i from the top is C_i milliliters.

Initially, all glasses are empty. Takahashi performs Q operations in order. Each operation is one of the following two types:

• Operation 1 (pour): Pour V milliliters of champagne into the glass at level 1. The poured champagne is added to the current amount of champagne in the level 1 glass. As a result, if the amount of champagne in the glass at level i (1 \leq i \leq N-1) exceeds its capacity C_i (is strictly greater than the capacity), all the excess immediately flows down to the glass at level i + 1. This check is performed sequentially from level 1 in a cascading manner, and all processing is completed instantaneously. Champagne that overflows from the bottom glass (level N) is lost and does not accumulate anywhere. Upon completion of the operation, the amount of champagne in each glass is guaranteed to be at most its capacity.
• Operation 2 (query): Output the amount of champagne (in milliliters) currently in the glass at level k.

For each operation 2, output the answer.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
• For operation 1: 1 \leq V \leq 10^9
• For operation 2: 1 \leq k \leq N
• Operation 2 is given at least once
• All input values are integers

Sample Input 1

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

Sample Output 1

0
4
5
2
0

Sample Input 2

4 8
2 2 2 2
1 1
2 1
1 10
2 1
2 2
2 3
2 4
2 4

Sample Output 2

1
2
2
2
2
2

Sample Input 3

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

Sample Output 3

0
3
1
3
7
2
10
10
5
8
6

Sample Input 4

25 40
100 1 50 200 3 400 5 600 7 800 9 1000 11 1200 13 1400 15 1600 17 1800 19 2000 21 2200 23
1 75
2 1
2 2
1 1000
2 1
2 3
2 4
1 5000
2 5
2 8
2 10
1 12345
2 12
2 15
2 20
1 999999999
2 1
2 2
2 3
2 10
2 25
1 1
2 25
1 2500
2 6
2 7
2 11
2 13
1 777
2 14
2 16
2 18
1 424242
2 19
2 21
2 22
2 23
2 24
1 314159265
2 25

Sample Output 4

75
0
100
50
200
3
600
800
1000
13
1800
100
1
50
800
23
23
400
5
9
11
1200
1400
1600
17
19
2000
21
2200
23

Sample Input 5

1 7
1000000000
2 1
1 1
2 1
1 999999999
2 1
1 1000000000
2 1

Sample Output 5

0
1
1000000000
1000000000

Problem Statement

Takahashi is developing a meeting room management system for a company.

This company has one large meeting room, and N meetings have been reserved. The i-th meeting starts at time S_i and ends at time E_i. In other words, the i-th meeting occupies the meeting room during the time interval from S_i (inclusive) to E_i (exclusive).

Due to the capacity of the meeting room, a problem occurs if K or more meetings overlap at the same time. Takahashi wants to check whether the reservation schedule has any issues.

If there exists a moment when K or more meetings are being held simultaneously, output Yes; otherwise, output No.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq K \leq N + 1
• 0 \leq S_i < E_i \leq 10^9
• All inputs are integers

Sample Input 1

3 2
1 5
3 7
6 9

Sample Output 1

Yes

Sample Input 2

5 3
0 10
11 20
5 15
21 30
25 35

Sample Output 2

No

Sample Input 3

10 4
100 500
200 600
250 400
300 350
700 1000
800 900
850 950
10 50
60 90
500000000 1000000000

Sample Output 3

Yes

Problem Statement

Takahashi is participating in a fruit picking festival. The festival's orchard has N fruit trees, each bearing exactly one fruit. The fruit on the i-th tree (1 \leq i \leq N) has a deliciousness of V_i and grows at height D_i.

Takahashi is given a total of M harvesting chances. In the j-th (1 \leq j \leq M) harvesting chance, he is assigned a stepladder of height L_j, which allows him to reach any fruit at height L_j or below.

The harvesting chances occur one at a time in the order j = 1, 2, \ldots, M. During each harvesting chance, Takahashi performs one of the following:

• Choose and harvest one fruit that has not yet been harvested and satisfies D_i \leq L_j.
• Pass without harvesting anything.

The same fruit cannot be harvested more than once. That is, a fruit harvested during one harvesting chance cannot be chosen in any subsequent harvesting chance.

Find the maximum total deliciousness of fruits that Takahashi can harvest over the M harvesting chances.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq D_i \leq 10^9
• 1 \leq V_i \leq 10^9
• 1 \leq L_j \leq 10^9
• All input values are integers.

Sample Input 1

4 3
2 10
5 30
3 20
1 5
3 2 5

Sample Output 1

60

Sample Input 2

3 4
10 100
1 20
2 50
1 1 2 1

Sample Output 2

70

Sample Input 3

10 8
8 40
3 100
5 60
10 200
1 15
7 90
4 55
6 70
2 80
9 120
4 6 3 10 5 8 1 7

Sample Output 3

670

Sample Input 4

30 25
12 500
3 1000000000
25 450
7 300
18 760
2 50
30 900
15 610
9 400
22 850
5 120
11 530
28 990
14 600
1 10
20 800
6 250
24 870
17 700
10 480
13 560
27 950
4 200
19 780
8 350
21 820
16 650
29 980
23 860
26 930
5 10 15 20 25 30 1 6 12 18 24 30 3 9 14 22 27 2 7 13 19 26 28 4 11

Sample Output 4

1000014280

Sample Input 5

1 1
1000000000 1000000000
1

Sample Output 5

0

Problem Statement

Takahashi is shopping at a store.

The store has N products lined up, each numbered from 1 to N. The price of product i is A_i. Multiple products may have the same price, but products with different numbers are distinguished as different products.

Takahashi will select and purchase K products from these. He cannot select the same product more than once, and the order of selection does not matter (that is, he selects as a combination of K items from N). Let P be the product of the prices of the K selected items.

This store has a special point system where points are awarded for the combination of purchased products according to the following rules using a prime number M:

• If P is not a multiple of M: There exists exactly one integer Q satisfying P \cdot Q \equiv 1 \pmod{M} and 0 \leq Q < M (this is guaranteed since M is prime). This Q is called the multiplicative inverse of P modulo M, and Q points are awarded.
• If P is a multiple of M: Since the multiplicative inverse does not exist, the awarded points are 0.

For all \binom{N}{K} ways of choosing K products from N products, determine the points awarded for each selection, and output the remainder when the total sum is divided by M.

Constraints

• 1 \leq K \leq N \leq 5000
• 2 \leq M \leq 10^9
• M is a prime number
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers

Sample Input 1

4 2 7
1 2 3 4

Sample Output 1

0

Sample Input 2

5 3 5
5 1 2 10 3

Sample Output 2

1

Sample Input 3

12 5 101
3 202 7 15 101 48 7 99 100 250 13 1

Sample Output 3

12

Sample Input 4

30 15 998244353
1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 998244353 999999937 123456789 987654321 314159265

Sample Output 4

354173354

Sample Input 5

1 1 2
2

Sample Output 5

0