Problem Statement

Takahashi is analyzing the timetable of a certain bus stop.

Exactly N buses arrive at this bus stop during one day. The arrival time of each bus is recorded as an integer (in seconds) between 0 and 86400 inclusive, where 0 represents the start of the day (midnight, 12:00 AM).

The arrival times of the N buses are given as T_1, T_2, \ldots, T_N in chronological order, and no two or more buses arrive at the same time (that is, T_1 < T_2 < \cdots < T_N).

Takahashi wants to find all the intervals between consecutive buses in chronological order, and determine the shortest and longest intervals among them. Specifically, the interval between the i-th and (i+1)-th buses is defined as T_{i+1} - T_i (seconds) (1 \leq i \leq N-1).

Find the minimum and maximum values among these N-1 intervals.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq T_i \leq 86400
• T_1 < T_2 < \cdots < T_N
• All input values are integers.

Sample Input 1

5
100 200 500 700 800

Sample Output 1

100 300

Sample Input 2

3
0 43200 86400

Sample Output 2

43200 43200

Sample Input 3

10
60 120 300 1800 3600 7200 36000 72000 80000 86400

Sample Output 3

60 36000

Problem Statement

Takahashi is planning a trip. There are N candidate tourist spots, and he can choose to visit between 0 and K of them (inclusive). However, he cannot choose the same tourist spot more than once.

Each tourist spot i (i = 1, 2, \ldots, N) has a souvenir shop that sells C_i souvenirs. The j-th souvenir (j = 1, 2, \ldots, C_i) at tourist spot i has a satisfaction value V_{i,j}. Satisfaction values can be negative.

Each tourist spot i has a rating. The rating is the median of the satisfaction values of the C_i souvenirs sold at that tourist spot. Here, the median refers to the \frac{C_i + 1}{2}-th value when the C_i satisfaction values are sorted in ascending order. Since C_i is always odd, the median is uniquely determined and is an integer. Note that the rating can be negative.

Takahashi wants to maximize the sum of the ratings of the tourist spots he visits by choosing them wisely. If he visits no tourist spots, the sum of ratings is 0.

On behalf of Takahashi, find the maximum possible sum of ratings.

Constraints

• 1 \leq N \leq 100
• 1 \leq K \leq N
• 1 \leq C_i \leq 99
• C_i is odd
• -1000 \leq V_{i,j} \leq 1000
• All input values are integers

Sample Input 1

3 2
3
3 1 2
3
5 -1 10
3
-3 -5 -1

Sample Output 1

7

Sample Input 2

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

Sample Output 2

0

Sample Input 3

5 3
5
10 20 30 5 15
3
-2 3 1
7
100 -50 0 25 75 50 -10
3
-1 -2 -3
3
7 8 9

Sample Output 3

48

Sample Input 4

10 5
5
12 -3 7 20 -8
3
100 200 150
7
-5 -10 3 8 -1 0 6
1
-1000
9
50 40 30 20 10 0 -10 -20 -30
3
999 998 1000
5
-100 -200 -300 -400 -500
1
500
3
0 0 0
5
1 2 3 4 5

Sample Output 4

1666

Sample Input 5

1 1
1
-5

Sample Output 5

0

Problem Statement

Takahashi is investigating the relationship between buildings and roads in a certain city.

The city is represented as a grid with H rows and W columns. The cell at the i-th row from the top (1 \leq i \leq H) and the j-th column from the left (1 \leq j \leq W) is denoted as (i, j). Each cell has one of the following types:

• B : Building
• R : Road
• E : Empty lot

In the initial state, the type of cell (i, j) is given by the j-th character of the string S_i.

A building cell is said to be facing a road if at least one of its vertically or horizontally adjacent cells is a road cell. Diagonally adjacent cells are not considered as facing a road.

From now on, Q road construction operations will be performed in order. The effects of construction are cumulative (once a cell becomes a road, it remains a road throughout all subsequent operations).

In the k-th operation (1 \leq k \leq Q), all empty lot cells within the rectangular region from row U_k to row D_k and from column L_k to column R_k are converted to road cells. Cells that are already roads or buildings do not change. Cells outside the construction area also do not change.

It is guaranteed that no building cells are contained within the rectangular region of each construction operation.

After each construction operation, determine the total number of building cells that are facing a road. Even if a single building cell is adjacent to multiple road cells, it is counted as one.

Constraints

• 1 \leq H, W \leq 10^6
• 1 \leq Q \leq 10^5
• H W \leq 2 \times 10^6
• H + Q \leq 2 \times 10^5
• S_i (1 \leq i \leq H) is a string of length W, where each character is one of B, R, or E
• 1 \leq U_k \leq D_k \leq H (1 \leq k \leq Q)
• 1 \leq L_k \leq R_k \leq W (1 \leq k \leq Q)
• \displaystyle \sum_{k=1}^{Q} \left( 2(D_k-U_k+1) + 2(R_k-L_k+1) \right) \leq 5 \times 10^6
• No cell with B is contained within the rectangular region of each construction operation
• All inputs are integers and strings

Sample Input 1

4 5 3
EEEEE
EBERE
EEEEE
REBEE
1 1 1 3
3 4 4 5
2 3 3 3

Sample Output 1

1
2
2

Sample Input 2

3 3 4
BEB
EEE
BEB
2 2 2 2
1 3 2 2
2 2 1 3
1 1 2 2

Sample Output 2

0
4
4
4

Sample Input 3

8 10 7
EEREEEEEER
EEBEEEEEEE
EEEEERBEEE
EEEEEEEEEE
BEEEEEEEER
EEEEREEEEE
EEEEBEEEEE
REEEEEEEEE
1 1 1 5
4 4 1 10
2 3 4 6
5 6 2 4
6 8 6 8
1 3 8 10
7 8 1 3

Sample Output 3

3
4
4
4
4
4
4

Sample Input 4

12 15 10
EEEEREEEEEEEEEE
EEEEBEEEREEBEEE
EEEEEEEEEEEEEEE
EEBEEEEEEEEEEER
EREEEEEEEBEEEEE
EEEEEEEEEEEEERE
EEEEEEBEEEEEEBE
EEEEEEEEEEEEEEE
BEEEEEEBEEEEEER
EEEEREEEEEEEEEE
EEEBEEEEEEBEEEE
REEEEEEEEEEEEER
1 1 1 15
2 8 1 1
3 6 4 8
2 4 13 15
5 6 11 15
8 10 2 4
10 12 12 15
6 8 8 13
3 3 1 15
12 12 1 15

Sample Output 4

3
4
6
6
7
8
9
10
10
10

Sample Input 5

1 1 1
E
1 1 1 1

Sample Output 5

0

Problem Statement

There are N street lights lined up in a row along a certain street.

The initial brightness of the i-th street light is A_i. The brightness decreases by D_i per day, but does not go below 0. That is, the brightness of the i-th street light after t days is

C_i(t) = \max(0,\ A_i - D_i \times t)

A street light whose brightness is K or less at time t days later is called a "dark street light."

The number of dark subintervals after t days is defined as follows: it is the number of pairs of integers (l, r) satisfying 1 \leq l \leq r \leq N such that all street lights from the l-th to the r-th are dark street lights after t days.

Here, (l, r) does not need to be a maximal contiguous interval; all pairs satisfying the condition are counted. For example, if m consecutive street lights are all dark, the number of pairs (l, r) that can be chosen from them is \frac{m(m+1)}{2}, and all of them are counted.

Q queries are given. For the j-th query, find the number of dark subintervals after T_j days.

Constraints

• 1 \leq N, Q
• N + Q \leq 2 \times 10^5
• 0 \leq K \leq 10^9
• 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq D_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq T_j \leq 10^9 (1 \leq j \leq Q)
• All inputs are integers
• The answer to each query fits in a 64-bit signed integer

Sample Input 1

5 4 10
15 2
8 0
30 5
10 1
25 3
0
2
4
10

Sample Output 1

2
2
10
15

Sample Input 2

4 5 5
6 0
5 0
20 10
1 0
0
1
2
3
10

Sample Output 2

2
2
6
6
6

Sample Input 3

10 8 20
50 5
18 0
100 10
21 1
0 0
35 3
80 20
20 0
60 4
25 2
0
1
2
3
5
7
10
20

Sample Output 3

3
5
5
8
17
19
55
55

Sample Input 4

25 12 100
150 10
90 0
300 20
101 1
500 50
0 0
250 5
120 30
100 0
1000 100
80 2
450 25
600 0
110 3
700 70
95 1
130 15
100 5
1000000000 100000000
400 40
200 0
105 2
10000 500
99 0
160 8
0
1
2
3
5
7
10
15
20
50
100
1000000000

Sample Output 4

7
10
14
15
18
18
63
68
74
116
116
116

Sample Input 5

1 1 0
1000000000 1000000000
1000000000

Sample Output 5

1

Problem Statement

Takahashi manages a household budget book in which N transactions are recorded in order. The i-th transaction has a type D_i and an amount B_i.

• If the type is R, the amount is added to the balance (deposit).
• If the type is L, the amount is subtracted from the balance (withdrawal).

Takahashi processes Q operations in the order they are given. There are 2 types of operations:

• 1 p D b: Modify the p-th transaction to have type D and amount b.
• 2 K: For the current state of the budget book, starting with a balance of 0 and processing each transaction from the 1-st onward, answer the number of the first transaction after which the balance becomes at least K. If the balance never reaches K or more after any transaction, answer 0.

Here, the number of the i-th transaction is i. The balance may become negative during processing.

Type 2 operations are queries and do not change the contents of the budget book.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• Let M be the number of type 2 operations among all operations. Then 1 \leq M and N+Q+M \leq 2 \times 10^5.
• D_i \in \{\texttt{R}, \texttt{L}\}
• 1 \leq B_i \leq 10^9
• B_i is an integer
• For type 1 operations:
• 1 \leq p \leq N
• D \in \{\texttt{R}, \texttt{L}\}
• 1 \leq b \leq 10^9
• b is an integer
• For type 2 operations:
• 1 \leq K \leq 2 \times 10^{14}
• K is an integer

Sample Input 1

5 6
R 10
L 3
R 5
L 20
R 15
2 7
2 12
1 4 L 4
2 12
1 2 R 2
2 20

Sample Output 1

1
3
3
5

Sample Input 2

3 4
L 10
R 5
L 1
2 1
2 100
1 2 L 5
2 1

Sample Output 2

0
0
0

Sample Input 3

10 12
R 8
L 4
R 15
L 10
R 7
R 3
L 20
R 25
L 5
R 6
2 10
2 20
1 7 L 5
2 30
1 4 R 12
2 40
1 1 L 3
2 5
2 50
1 10 L 2
2 25
2 60

Sample Output 3

3
8
8
6
3
8
5
0

Sample Input 4

30 30
R 100
L 40
R 70
L 150
R 200
L 30
L 80
R 300
L 120
R 50
R 400
L 500
R 600
L 100
R 90
L 250
R 700
L 60
R 30
L 20
R 1000
L 800
R 450
L 300
R 200
L 100
R 50
L 400
R 900
L 700
2 100
2 500
1 4 R 150
2 500
1 12 L 100
2 1000
1 22 R 800
2 2000
1 28 R 400
2 2500
1 1 L 100
2 50
2 3000
1 17 L 700
2 1500
1 30 R 700
2 3500
1 7 R 80
2 1200
1 21 L 1000
2 1000
1 5 L 200
2 800
1 13 L 600
2 700
1 2 R 40
2 600
1 29 L 900
2 400
2 5000

Sample Output 4

1
11
8
11
21
21
4
22
22
29
13
13
13
30
11
11
0

Sample Input 5

1 1
R 1000000000
2 200000000000000

Sample Output 5

0