Problem Statement

Takahashi is working at the reception desk of a certain event venue. For this event, two types of tickets are sold: regular tickets and student discount tickets.

One day, part of the event program was canceled, so it was decided to refund the ticket prices to the visitors. The refund rules are as follows:

• For visitors holding a regular ticket (denoted as normal in the input), the full amount of their purchase price P_i yen is refunded, i.e., P_i yen.
• For visitors holding a student discount ticket (denoted as half in the input), half of their purchase price (rounded down) is refunded, i.e., \lfloor P_i / 2 \rfloor yen.

There are N visitors lined up for refunds at Takahashi's counter. For each visitor i (1 \leq i \leq N), a string T_i representing the ticket type and the purchase price P_i (in yen) are given.

Find the total amount (in yen) that Takahashi needs to refund to all visitors.

Constraints

• 1 \leq N \leq 2 \times 10^5
• T_i is either normal or half.
• 1 \leq P_i \leq 10^5
• N and all P_i are integers.

Sample Input 1

3
normal 1000
half 500
half 300

Sample Output 1

1400

Sample Input 2

5
normal 2000
half 1999
normal 500
half 750
normal 1200

Sample Output 2

5074

Sample Input 3

10
normal 100000
half 99999
normal 50000
half 1
normal 12345
half 67890
normal 1
half 100000
normal 99999
half 55555

Sample Output 3

424066

Problem Statement

Takahashi's bookshelf has N books lined up in a row. The i-th book from the left has a number written on it represented by the integer A_i.

Aoki saw M books lined up in a row in a bookstore's show window. The j-th book from the left has a number written on it represented by the integer B_j.

Note that book numbers may have duplicates.

Determine whether there exists a contiguous subsequence in Takahashi's bookshelf that exactly matches the arrangement in the show window.

Specifically, determine whether there exists an integer i (1 \le i \le N - M + 1) such that A_i, A_{i+1}, \dots, A_{i+M-1} match B_1, B_2, \dots, B_M respectively. If such an i exists, output the smallest such i. If it does not exist, output -1.

Constraints

• 1 \le M \le N \le 5 \times 10^5
• 1 \le A_i \le 10^9 (1 \le i \le N)
• 1 \le B_j \le 10^9 (1 \le j \le M)
• All input values are integers

Sample Input 1

6 3
4 1 2 3 5 6
2 3 5

Sample Output 1

3

Sample Input 2

4 2
1 3 1 3
3 3

Sample Output 2

-1

Sample Input 3

18 5
5 1 2 1 2 3 4 1 2 3 4 5 1 2 3 4 6 7
1 2 3 4 5

Sample Output 3

8

Sample Input 4

46 10
100 200 300 400 500 100 200 300 999 888 777 666 555 444 333 222 111 123 234 345 42 84 126 168 210 252 294 336 378 420 42 84 126 168 210 999999937 1 2 3 4 5 6 7 8 9 10
42 84 126 168 210 252 294 336 378 420

Sample Output 4

21

Sample Input 5

1 1
1000000000
1000000000

Sample Output 5

1

Problem Statement

Takahashi is a member of the school gardening committee. In the schoolyard, there are N planters arranged in a straight line from east to west, numbered Planter 1, Planter 2, \ldots, Planter N from west to east. Before watering begins, the amount of water in each planter is 0 liters.

Starting today, Takahashi is assigned watering duty for Q days. On day i (1 \leq i \leq Q), he waters each planter from Planter L_i to Planter R_i (inclusive) with C_i liters of water.

After all Q days of watering are completed, find the total amount of water given to each of Planter 1, Planter 2, \ldots, Planter N.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq N
• 1 \leq C_i \leq 10^4
• All input values are integers

Sample Input 1

5 3
1 3 2
2 4 3
4 5 1

Sample Output 1

2 5 5 4 1

Sample Input 2

10 5
1 10 1
3 7 2
5 5 10
1 1 5
8 10 3

Sample Output 2

6 1 3 3 13 3 3 4 4 4

Sample Input 3

20 8
1 20 100
5 15 50
1 5 30
16 20 30
10 10 500
3 8 25
12 18 40
7 14 15

Sample Output 3

130 130 155 155 205 175 190 190 165 665 165 205 205 205 190 170 170 170 130 130

Problem Statement

Takahashi is observing a culture sample consisting of N cells.

Each cell has an activity value represented by a positive integer. Initially, the activity value of the i-th cell is A_i.

As long as there exists a cell with an activity value of 2 or more in the culture sample, Takahashi repeatedly performs the following sequence of steps as one operation:

1. Choose one cell from the culture sample whose activity value is 2 or more. Let x be the activity value of the chosen cell.
2. Choose a prime number p that divides x.
3. Remove that cell from the culture sample, and add p new cells each with activity value x / p to the culture sample. (Since p is a divisor of x, x / p is a positive integer.)

Each operation increases the total number of cells by p - 1. If the activity value of the newly added cells is 2 or more, they become eligible to be chosen in subsequent operations. Cells with an activity value of 1 cannot be chosen for operations.

In each operation, Takahashi is free to choose which cell to select and which prime number p to use. Depending on these choices, the number of operations required until all cells have an activity value of 1 may vary.

Find the minimum and maximum number of operations required to make the activity values of all cells equal to 1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^6
• All input values are integers.

Sample Input 1

3
2 3 4

Sample Output 1

5 5

Sample Input 2

4
1 6 8 9

Sample Output 2

14 15

Sample Input 3

10
12 15 16 18 20 25 27 30 49 64

Sample Output 3

141 171

Sample Input 4

24
2 4 6 8 9 10 12 15 16 18 20 21 24 25 27 30 32 36 40 45 49 64 81 1000000

Sample Output 4

250346 988666

Sample Input 5

1
1

Sample Output 5

0 0

Problem Statement

Takahashi has an integer sequence A_1, A_2, \ldots, A_N of length N.

Takahashi wants to select one contiguous interval of W elements from this sequence and maximize its evaluation score.

Specifically, he chooses an integer l (1 \leq l \leq N - W + 1) and defines the evaluation score of the interval A_l, A_{l+1}, \ldots, A_{l+W-1} by the following formula:

\text{Evaluation Score} = \left(\sum_{i=l}^{l+W-1} A_i\right) + K \times \min(A_l, A_{l+1}, \ldots, A_{l+W-1})

That is, the evaluation score is the sum of the elements in the interval plus the product of the minimum value in the interval and the integer K.

Note that K and each A_i can be positive, zero, or negative.

Find the maximum evaluation score over all possible values of l (1 \leq l \leq N - W + 1).

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq W \leq N
• -10^6 \leq K \leq 10^6
• -10^9 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5 3 2
1 3 2 5 4

Sample Output 1

15

Sample Input 2

4 2 -3
5 1 4 3

Sample Output 2

3

Sample Input 3

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

Sample Output 3

7

Sample Input 4

20 5 -2
10 -7 3 8 -1 6 2 -4 9 5 -3 7 1 -8 4 11 -6 2 0 3

Sample Output 4

31

Sample Input 5

1 1 1000000
-1000000000

Sample Output 5

-1000001000000000