Problem Statement

Takahashi manages the production line of a factory. The factory has N workstations arranged in a row, numbered 1, 2, \ldots, N from left to right. Initially, workstation i has A_i parts placed on it.

Each workstation has a switch. When the switch of workstation i (1 \leq i \leq N - 1) is pressed, all parts on workstation i are moved by a belt conveyor to the adjacent workstation i + 1. The moved parts are added to the parts already on workstation i + 1, and the number of parts on workstation i becomes 0. On the other hand, when the switch of workstation N is pressed, all parts on workstation N are ejected outside the production line, and the number of parts on workstation N becomes 0. Ejected parts are completely removed from the production line and have no relation to any subsequent operations.

If the switch of a workstation with 0 parts is pressed, nothing happens (the number of parts on that workstation remains 0).

Takahashi will perform a total of Q switch operations. In the j-th operation (1 \leq j \leq Q), he presses the switch of workstation B_j. The operations are performed one at a time in the order j = 1, 2, \ldots, Q, and each operation is executed in the state reflecting the results of all previous operations. Note that the switch of the same workstation may be pressed multiple times.

After all operations are completed, determine the number of parts remaining on each workstation.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq Q \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq B_j \leq N (1 \leq j \leq Q)
• All input values are integers
• It is guaranteed that at any point during and after the operations, the number of parts on each workstation does not exceed 2 \times 10^{14}

Sample Input 1

5 3
3 1 4 1 5
1
3
5

Sample Output 1

0 4 0 5 0

Sample Input 2

4 4
5 3 2 1
1
1
2
3

Sample Output 2

0 0 0 11

Sample Input 3

8 6
10 20 30 40 50 60 70 80
2
4
6
7
8
8

Sample Output 3

10 0 50 0 90 0 0 0

Sample Input 4

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

Sample Output 4

0 0 0 0 0 0 0 0 0 0

Sample Input 5

1 1
1000000000
1

Sample Output 5

0

Problem Statement

Takahashi is planning a trip.

Takahashi has N smartphones. Each smartphone is numbered from 1 to N, and smartphone i currently has a battery level of A_i %. Battery levels are managed as integer values and never go below 0 %.

A smartphone with a battery level of L % or less is powered off and cannot be used. Therefore, smartphone i with A_i \leq L at the current time is already powered off from the start. Once a smartphone is powered off, it can never become usable again.

Takahashi has one mobile battery. Let the current time be time 0. At time 0, Takahashi can choose at most K smartphones (possibly 0) from among the currently powered-on smartphones and connect them to the mobile battery. Smartphones connected to the mobile battery remain connected until all processing at time Y is complete, and their battery levels do not decrease at all during this period. It is not possible to disconnect them midway or switch the connection to a different smartphone. Also, a powered-off smartphone cannot be connected to the mobile battery.

After the mobile battery connections are made, at each of time 1, time 2, \ldots, time Y, the following operations are performed in this order:

1. Battery consumption: For each powered-on smartphone that is not connected to the mobile battery, its battery level decreases by 1 %.
2. Power-off check: For smartphones not connected to the mobile battery, any smartphone whose battery level has become L % or less is powered off.

When Takahashi optimally chooses which smartphones to connect to the mobile battery, find the maximum number of smartphones that are powered on (usable) immediately after all processing at time Y is complete. Smartphones connected to the mobile battery are also counted if they are powered on.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq L \leq 99
• 0 \leq K \leq N
• 1 \leq Y \leq 100
• 1 \leq A_i \leq 100
• All inputs are integers

Sample Input 1

5 10 2 5
50 12 8 30 14

Sample Output 1

4

Sample Input 2

8 20 3 10
100 35 25 50 18 30 22 80

Sample Output 2

7

Sample Input 3

10 0 1 50
100 48 51 30 75 50 60 10 49 55

Sample Output 3

6

Problem Statement

Takahashi is about to purchase N items. The items are numbered from 1 to N, and the price of item i is W_i yen.

Takahashi has Q discount coupons. The j-th coupon has the effect of discounting the price of every item whose number is between L_j and R_j inclusive (i.e., items L_j, L_j+1, \ldots, R_j) by D_j yen each.

When multiple coupons apply to the same item, the discount amounts are all accumulated. That is, if the total discount amount from all coupons applied to item i is S_i, then the price of item i after applying all coupons becomes \max(W_i - S_i,\ 0) yen.

After applying all coupons, find the number of items whose price becomes 0 yen (i.e., items satisfying W_i \leq S_i).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq W_i \leq 10^9
• 1 \leq L_j \leq R_j \leq N
• 1 \leq D_j \leq 10^9
• All input values are integers.

Sample Input 1

5 3
100 200 150 300 50
1 3 100
2 4 150
5 5 50

Sample Output 1

4

Sample Input 2

7 4
500 300 200 400 100 600 250
1 4 200
3 5 150
2 6 100
4 7 300

Sample Output 2

5

Sample Input 3

10 6
1000000000 500 200 800 1200 300 450 100 900 600
1 5 600
3 7 250
1 3 400
6 10 400
2 8 200
5 9 500

Sample Output 3

8

Problem Statement

Takahashi has one long rope.

This rope is divided into N sections, and each section is numbered from 1 to N from left to right. The length of section i (1 \leq i \leq N) is A_i, and the total length of the rope is A_1 + A_2 + \cdots + A_N.

Takahashi wants to divide this rope into exactly K pieces. The rope can only be cut at the boundary between section i and section i+1 (1 \leq i \leq N-1). To divide the rope into exactly K pieces, he selects exactly K - 1 of the N - 1 available boundaries and cuts at those positions. Sections cannot be removed, and every section must belong to exactly one of the resulting pieces.

As a result, each piece after the division consists of one or more consecutively numbered sections. The length of each piece is the sum of the lengths of the sections it contains.

Takahashi wants to minimize the length of the longest piece among the K pieces after the division.

Find the minimum possible length of the longest piece among the K pieces when the cuts are made optimally.

Constraints

• 1 \leq K \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• All inputs are integers.

Sample Input 1

5 3
1 2 3 4 5

Sample Output 1

6

Sample Input 2

8 4
3 1 4 1 5 9 2 6

Sample Output 2

9

Sample Input 3

10 3
100 200 300 400 500 600 700 800 900 1000

Sample Output 3

2100

Problem Statement

Takahashi is a travel planner. A certain sightseeing area has N tourist spots, numbered from 1 to N. There are M bidirectional roads connecting these spots.

Each tourist spot i has a satisfaction value c_i. Takahashi wants to propose a sightseeing route that starts at spot S and arrives at spot T.

Here, a sightseeing route is a simple path from S to T, that is, a sequence of spots S = v_0, v_1, \ldots, v_k = T (k \geq 1) satisfying all of the following conditions:

• All spots in the sequence are distinct (no spot is visited more than once).
• For each pair of consecutive spots v_{i-1} and v_i (1 \leq i \leq k), a road exists between them.

The score of a sightseeing route is defined as the sum of satisfaction values of all spots visited along the route (including the starting spot S and the ending spot T): \displaystyle\sum_{i=0}^{k} c_{v_i}.

Compute the average score over all sightseeing routes from S to T (i.e., the sum of scores of all routes divided by the total number of routes).

It is guaranteed that at least one sightseeing route from S to T exists.

Constraints

• 2 \leq N \leq 18
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq S \leq N
• 1 \leq T \leq N
• S \neq T
• 1 \leq c_i \leq 1000 (1 \leq i \leq N)
• 1 \leq u_j < v_j \leq N (1 \leq j \leq M)
• There is at most one road between any pair of spots (no multi-edges)
• There are no self-loops
• At least one simple path from S to T exists
• All input values are integers

Sample Input 1

3 2 1 3
10
20
30
1 2
2 3

Sample Output 1

60.000000000000000

Sample Input 2

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

Sample Output 2

19.000000000000000

Sample Input 3

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

Sample Output 3

31.714285714285715

Sample Input 4

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

Sample Output 4

87.619047619047620

Sample Input 5

2 1 1 2
1
1000
1 2

Sample Output 5

1001.000000000000000