Problem Statement

Takahashi is a fruit farmer and obtained N fruits from today's harvest. He measured the sugar content of each fruit i and found it to be S_i.

As a shipping criterion, only fruits with sugar content of K or higher can be shipped. Fruits with sugar content less than K are considered substandard and cannot be shipped.

Takahashi wants to know the average sugar content of the fruits that can be shipped (fruits with sugar content of K or higher). However, if there are no fruits that can be shipped, the average cannot be calculated.

If there is at least one fruit that can be shipped, output the average sugar content of those fruits. If there are no fruits that can be shipped, output -1.

Constraints

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

Sample Input 1

5 8
3 10 7 12 9

Sample Output 1

10.333333333333334

Sample Input 2

4 15
3 7 10 14

Sample Output 2

-1

Sample Input 3

10 50
45 60 55 30 70 48 52 49 80 51

Sample Output 3

61.333333333333336

Sample Input 4

20 500
120 600 450 800 300 550 499 501 750 200 630 480 520 999 100 500 350 680 490 510

Sample Output 4

640.0

Sample Input 5

1 1000000000
1000000000

Sample Output 5

1000000000.0

Problem Statement

There is an electronic display board with N cells arranged in a horizontal row. Each cell displays a single uppercase English letter. Let S_i denote the character displayed in the i-th cell from the left. The initial state is represented by a string S = S_1 S_2 \dots S_N of length N.

Takahashi performs Q updates on this display board in order. In the k-th update, he changes the character in the i_k-th cell from the left to the uppercase English letter c_k (the character may be changed to the same character as the current one).

For an integer i satisfying 1 \le i < N, if the characters displayed in the i-th cell and the (i+1)-th cell from the left are the same, this pair is called a matching pair. The number of matching pairs is the number of such i that satisfy this condition.

For each update, determine the number of matching pairs immediately after the update.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq Q \leq 10^5
• S is a string of length N consisting of uppercase English letters
• 1 \leq i_k \leq N (1 \leq k \leq Q)
• c_k is an uppercase English letter (1 \leq k \leq Q)
• N, Q, i_k are integers

Sample Input 1

5 4
ABBCC
2 A
3 A
5 D
4 D

Sample Output 1

2
3
2
3

Sample Input 2

6 5
ABCDEF
1 A
2 A
6 E
5 E
3 A

Sample Output 2

0
1
2
2
3

Sample Input 3

12 8
AABCCDDEFGGH
3 A
4 A
5 A
8 D
9 D
10 D
11 D
12 D

Sample Output 3

5
5
6
7
8
8
9
10

Sample Input 4

20 12
ABBAACCDDDEEFFGGHHII
1 B
4 B
5 B
10 E
8 C
9 C
20 H
19 H
12 F
11 F
15 H
16 H

Sample Output 4

11
11
12
12
12
13
12
14
14
14
13
15

Sample Input 5

2 1
AA
1 B

Sample Output 5

0

Problem Statement

Takahashi is a dispatch manager at a shipping company. In the warehouse, N packages are lined up in a row, numbered from 1 to N, and the weight of the i-th package is A_i.

These packages are to be divided among exactly M trucks for delivery. The division is performed by partitioning the packages into exactly M groups of consecutively numbered packages, preserving the order of package numbers. Specifically, we choose an integer sequence L_0, L_1, \ldots, L_M satisfying 0 = L_0 < L_1 < L_2 < \cdots < L_M = N, and the k-th truck (1 \leq k \leq M) is loaded with packages L_{k-1}+1, L_{k-1}+2, \ldots, L_k. Note that since L_0 < L_1 < \cdots < L_M uses strict inequalities, each truck contains at least one package.

For each truck, the total weight of its loaded packages is called its "load". Since the truck with the largest load among the M trucks bears a disproportionate burden, Takahashi wants to divide the packages so that the maximum load is as small as possible.

Let S be the minimum possible value of the maximum load over all possible ways to divide the packages. Given an integer K, determine whether S > K.

• If the maximum load exceeds K no matter how the packages are divided (i.e., S > K), output Yes.
• If there exists a way to divide the packages such that the maximum load is at most K (i.e., S \leq K), output No.

Constraints

• 1 \leq M \leq N \leq 10^6
• 1 \leq A_i \leq 10^9
• 1 \leq K \leq 10^{15}
• All input values are integers.

Sample Input 1

5 2 10
3 5 2 4 6

Sample Output 1

No

Sample Input 2

5 2 9
3 5 2 4 6

Sample Output 2

Yes

Sample Input 3

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

Sample Output 3

No

Sample Input 4

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

Sample Output 4

No

Sample Input 5

3 3 5
5 6 5

Sample Output 5

Yes

Problem Statement

Takahashi is a network design engineer at a telecommunications company. There are N bases, and there are M candidate communication cables to connect them. Each candidate i bidirectionally connects base u_i and base v_i with an installation cost of c_i.

Takahashi must construct a network where all bases can communicate with each other (either directly or via relays). However, the overall evaluation of the network is not measured simply by the total cost, but by a "load index" defined as follows.

Let S be the set of cables to be installed. The load index is defined as:

\text{Load Index} = \left( \sum_{i \in S} c_i \right) + K \times \max_{i \in S} c_i

Here, K is a non-negative integer coefficient determined by company policy. The load index means that, in addition to the total installation cost, a penalty is added by multiplying the cost of the most expensive cable by K. This reflects the maintenance and operational risks of including extremely expensive cables.

Takahashi wants to find a set of cables S that makes all bases connected while minimizing the load index. Find the minimum possible load index.

Note that it is guaranteed that there always exists a set of cables that makes all bases connected.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N - 1 \leq M \leq 2 \times 10^5
• 0 \leq K \leq 10^6
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• 1 \leq c_i \leq 10^6
• All input values are integers.
• There exists at least one set of cables that makes all bases connected.

Sample Input 1

4 5 2
1 2 3
2 3 4
3 4 5
1 4 10
1 3 6

Sample Output 1

22

Sample Input 2

3 3 0
1 2 7
2 3 2
1 3 5

Sample Output 2

7

Sample Input 3

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

Sample Output 3

55

Sample Input 4

12 20 100
1 2 15
2 3 18
3 4 14
4 5 16
5 6 20
6 7 13
7 8 17
8 9 19
9 10 12
10 11 21
11 12 11
1 6 50
2 7 45
3 8 40
4 9 35
5 10 30
6 11 25
7 12 22
1 12 100
3 10 28

Sample Output 4

2276

Sample Input 5

2 1 1000000
1 2 1000000

Sample Output 5

1000001000000

Problem Statement

Takahashi is conducting research in bioinformatics. One day, he needs to join two DNA fragments together.

The DNA fragments used in the research are represented as strings where the base sequences are encoded using the two values 0 and 1. Fragment S is a string of length L, and fragment T is a string of length M (L \leq M). Takahashi wants to join fragment S to either the left side or the right side of fragment T. During joining, the ends of the two fragments can be placed so that they overlap, but the sequences in the overlapping portion must match exactly. Simple concatenation without overlap is not allowed; an overlap of at least 1 character is required.

More precisely:

Left joining (the resulting order is S, T): Choose a positive integer k (1 \le k \le L). When the last k characters of S match the first k characters of T, a left join with overlap width k is possible. The resulting string is formed by S in its entirety followed by the remaining part of T after removing its first k characters (equivalently, the first L - k characters of S followed by T in its entirety), and has total length L + M - k.

Right joining (the resulting order is T, S): Choose a positive integer k (1 \le k \le L). When the last k characters of T match the first k characters of S, a right join with overlap width k is possible. The resulting string is formed by T in its entirety followed by the remaining part of S after removing its first k characters (equivalently, T in its entirety followed by the last L - k characters of S), and has total length L + M - k.

In both cases, k = L (where the entirety of S overlaps with an end of T) is also permitted. Note that since L \leq M, for any k \le L, T always has at least k characters available.

The larger the overlap width, the shorter the total length after joining, making analysis more efficient. Takahashi wants to choose either left joining or right joining to maximize the overlap width.

Find the larger of the maximum achievable overlap width for left joining and the maximum achievable overlap width for right joining. If joining with an overlap width of 1 or more is impossible for both joining methods (i.e., there is no overlap where the sequences match for either left joining or right joining), output 0.

Constraints

• 1 \leq L \leq 5 \times 10^5
• 1 \leq M \leq 5 \times 10^5
• L \leq M
• S is a string of length L consisting only of 0 and 1.
• T is a string of length M consisting only of 0 and 1.

Sample Input 1

3 5
101
01101

Sample Output 1

3

Sample Input 2

1 4
0
1111

Sample Output 2

0

Sample Input 3

12 20
110010101011
01010110011101011010

Sample Output 3

7

Sample Input 4

50 80
01001101010100110101010011010101001101010100110101
01001101010100110101010011010111111000001111100000111110000011111000001111100000

Sample Output 4

30

Sample Input 5

1 1
1
1

Sample Output 5

1