Problem Statement

Takahashi manages the point card system of a shopping mall. The mall has N members, and member i (1 \leq i \leq N) has an initial point balance of S_i.

From now on, M point adjustment operations will be performed one by one in order from the 1-st to the M-th. In the j-th operation (1 \leq j \leq M), the value V_j is added to the current point balance of member T_j, and the new point balance is set to the maximum of the result and 0. That is, if member T_j's point balance before the operation is P, then the point balance after the operation becomes \max(P + V_j,\ 0). Each operation is completed before the next operation begins. Note that the same member may be subject to multiple operations.

There is no upper limit on the point balance. On the other hand, by the rule above, the point balance after each operation is always 0 or greater.

Determine the point balance of each member after all point adjustment operations have been performed in order.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq T_j \leq N (1 \leq j \leq M)
• -10^9 \leq V_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers.
• It is guaranteed that all values to be output are at most 2^{63}-1 (they fit within a signed 64-bit integer).

Sample Input 1

3 4
100 200 300
1 50
2 -150
3 -400
1 -200

Sample Output 1

0 50 0

Sample Input 2

5 6
0 500 1000 750 300
3 -500
1 100
2 -600
4 250
5 -300
2 200

Sample Output 2

100 200 500 1000 0

Sample Input 3

10 12
1000000000 0 500000000 999999999 123456789 0 777777777 100000000 999999999 1
1 -1000000000
2 1000000000
3 -500000001
4 1
5 -123456790
6 0
7 -777777777
8 900000000
9 -1000000000
10 999999999
10 -500000000
3 1000000000

Sample Output 3

0 1000000000 1000000000 1000000000 0 0 0 1000000000 0 500000000

Problem Statement

Takahashi is maintaining a flower bed. The flower bed contains N flowers arranged in a row, and the variety of the i-th flower from the left is represented by an integer S_i. The same integer represents the same variety, and different integers represent different varieties.

Takahashi calls a section where K or more consecutive flowers of the same variety are lined up a "beautiful interval."

More precisely, a continuous sequence from the l-th flower to the r-th flower from the left is called a beautiful interval when the pair of integers (l, r) satisfies all of the following conditions:

• 1 \leq l \leq r \leq N
• S_l = S_{l+1} = \cdots = S_r
• r - l + 1 \geq K

Takahashi decided that for each flower, if there exists at least one beautiful interval containing that flower, he will keep it; otherwise, he will remove it.

That is, the i-th flower is kept if there exists a pair (l, r) satisfying the above conditions with 1 \leq l \leq i \leq r \leq N. Flowers for which no such (l, r) exists are removed.

After removing all the flowers to be taken out, determine the sequence of varieties of the remaining flowers, listed in their original order. It is possible that all flowers are removed and none remain.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq K \leq N
• 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

10 3
1 2 2 2 3 1 1 1 1 2

Sample Output 1

2 2 2 1 1 1 1

Sample Input 2

5 3
1 2 1 2 1

Sample Output 2

Sample Input 3

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

Sample Output 3

3 3 4 4 4 1 1 5 5 5 5

Sample Input 4

20 4
1 1 1 1 2 2 2 3 3 3 3 3 1 2 2 2 2 2 1 1

Sample Output 4

1 1 1 1 3 3 3 3 3 2 2 2 2 2

Sample Input 5

1 1
42

Sample Output 5

42

Problem Statement

Takahashi, as an adventurer, has infiltrated the treasure vault of ancient ruins. There are N treasures in the vault, and Takahashi is trying to pack them into his knapsack to bring them home.

Each treasure i (1 \leq i \leq N) has a weight of w_i kilograms and a value of v_i.

Takahashi's knapsack can hold treasures with a total weight of at most W kilograms. For each of the N treasures, Takahashi chooses whether or not to put it in the knapsack. There is at most one of each treasure, and it is not possible to split a treasure and put only a part of it in the knapsack.

Takahashi wants to maximize the total value of the chosen treasures, subject to the constraint that the total weight of the chosen treasures is at most W kilograms.

Find the maximum possible total value.

Constraints

• 1 \leq N \leq 100
• 1 \leq W \leq 10^5
• 1 \leq w_i \leq W
• 1 \leq v_i \leq 10^9
• All inputs are integers.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Sample Input 2

5 15
2 10
3 20
5 30
7 40
9 50

Sample Output 2

90

Sample Input 3

10 50
12 150
8 90
15 200
6 80
20 250
3 40
10 120
18 220
5 60
25 300

Sample Output 3

640

Problem Statement

Takahashi works at a delivery center and must deliver packages from a warehouse to N destinations.

The warehouse and all destinations are located on a single number line. The warehouse is at coordinate 0, and the i-th destination is at coordinate X_i (X_i can be positive or negative). All destination coordinates are distinct from each other and also distinct from the warehouse position (coordinate 0). Exactly D_i packages must be delivered to the i-th destination. The warehouse initially has all packages for all destinations, totaling \sum_{i=1}^{N} D_i packages.

The cart Takahashi uses has a capacity limit and can carry at most K packages at a time. Takahashi repeats the following procedure until the required number of packages has been delivered to all destinations:

1. Load packages: At the warehouse (coordinate 0), load any number of packages from 1 to K onto the cart. However, he cannot load more than the total remaining number of undelivered packages across all destinations.
2. Deliver: Depart from the warehouse and move freely along the number line, delivering packages from the cart to any destinations in any quantities. Multiple destinations can be visited in a single delivery trip, and destinations in both the positive and negative directions can be visited in the same trip. For example, a route where he first goes in the positive direction to deliver to some destinations, then turns back to deliver to destinations in the negative direction, is possible. The number of packages delivered to each destination must not exceed the remaining undelivered count for that destination. It is not necessary to deliver all packages loaded on the cart; undelivered packages are brought back to the warehouse and can be used in subsequent deliveries. Note that even if he passes through the warehouse (coordinate 0) during a delivery trip, he cannot load additional packages.
3. Return to warehouse: Return to the warehouse (coordinate 0).

Deliveries to each destination can be split across multiple trips. For example, if 5 packages need to be delivered to a destination, it is acceptable to deliver 3 in one trip and 2 in another.

The travel distance of a single delivery trip is the total distance Takahashi actually travels from departing the warehouse until returning to the warehouse. The distance of moving from coordinate a to coordinate b is |a - b|. For example, if he goes from the warehouse (coordinate 0) to coordinate 5, turns back to coordinate -3, and returns to the warehouse (coordinate 0), the travel distance is 5 + 8 + 3 = 16.

Takahashi wants to minimize the total travel distance across all delivery trips until all packages are delivered and he has returned to the warehouse (coordinate 0).

Find the minimum total travel distance.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^9
• -10^9 \leq X_i \leq 10^9
• X_i \neq 0
• All X_i are distinct
• 1 \leq D_i \leq 10^9
• \sum_{i=1}^{N} D_i \leq 10^9
• All inputs are integers

Sample Input 1

3 3
2 2
-4 1
5 2

Sample Output 1

22

Sample Input 2

2 2
-3 3
-1 1

Sample Output 2

12

Sample Input 3

8 5
-10 4
7 3
-2 6
15 2
4 5
-6 1
12 7
-14 3

Sample Output 3

128

Sample Input 4

20 7
-100 8
35 3
-12 15
80 6
5 9
-55 4
120 11
-3 2
60 7
-200 5
18 13
-75 10
150 1
-30 6
95 14
-140 3
42 8
-8 12
210 4
-180 9

Sample Output 4

3366

Sample Input 5

1 1000000000
-1000000000 1000000000

Sample Output 5

2000000000

Problem Statement

Takahashi is developing a contact list system for internal use at his company. Each employee has a unique username, but since usernames are long, he decided to implement a feature that assigns an abbreviation to each employee.

There are N employees, and the username of the i-th employee is a string S_i consisting of lowercase English letters. For each employee i, exactly one non-empty prefix of their username S_i is chosen and assigned as their abbreviation T_i. That is, T_i must be a string consisting of the first 1 to |S_i| characters of S_i. Using the entire username as the abbreviation is also permitted.

The abbreviation assignment (T_1, T_2, \ldots, T_N) must satisfy the following prefix-free condition:

• Prefix-free condition: For any two distinct employees i, j (i \neq j), T_i is not a prefix of T_j, and T_j is not a prefix of T_i.

Here, a string A is a prefix of a string B if |A| \leq |B| and the first |A| characters of B match A. In particular, when A = B, A is also a prefix of B.

Therefore, by the prefix-free condition, having T_i = T_j for distinct employees i, j (i \neq j) is also not permitted.

Takahashi wants to minimize the total length of abbreviations \sum_{i=1}^{N} |T_i| if a valid abbreviation assignment exists. If a valid assignment exists, output the minimum total length; otherwise, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• S_i is a string consisting of lowercase English letters.
• 1 \leq |S_i| \leq 5 \times 10^5
• If i \neq j, then S_i \neq S_j (all usernames are distinct).
• \sum_{i=1}^{N} |S_i| \leq 5 \times 10^5

Sample Input 1

3
alice
bob
carol

Sample Output 1

3

Sample Input 2

2
a
ab

Sample Output 2

-1

Sample Input 3

12
apple
apricot
banana
bandit
banner
candle
canary
cattle
dog
dove
duck
zebra

Sample Output 3

38

Sample Input 4

40
aaaaaa
aaaaab
aaaaac
aaaaad
aaaaae
aaaaba
aaaabb
aaaabc
aaaabd
aaaabe
aaabaa
aaabab
aaabac
aaabad
aaabae
aaabba
aaabbb
aaabbc
aaabbd
aaabbe
aabaaa
aabaab
aabaac
aabaad
aabaae
aababa
aababb
aababc
aababd
aababe
abaaaa
abaaab
abaaac
abaaad
abaaaae
ababaa
ababab
ababac
ababad
ababae

Sample Output 4

-1

Sample Input 5

1
a

Sample Output 5

1