Problem Statement

Takahashi works as an instructor at a cram school. His job is to analyze the results of tests administered across multiple classes.

The cram school has N classes, each numbered from 1 to N. Class i (1 \leq i \leq N) has M_i students enrolled, and the test score of the j-th student (1 \leq j \leq M_i) is S_{i,j} points.

Takahashi wants to determine, for each class, "the number of students whose score is at least the threshold score K." For each class i, find the number of students C_i whose test score is K points or higher.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq K \leq 100
• 1 \leq M_i \leq 100
• The total number of students across all classes is at most 10^6, i.e., \sum_{i=1}^{N} M_i \leq 10^6
• 0 \leq S_{i,j} \leq 100
• All input values are integers

Sample Input 1

3 60
5 45 72 60 88 55
3 100 59 60
4 30 40 50 20

Sample Output 1

3
2
0

Sample Input 2

5 75
6 80 65 90 75 70 85
4 74 75 76 100
3 50 60 70
8 75 75 75 75 74 74 74 74
2 0 100

Sample Output 2

4
3
0
4
1

Sample Input 3

10 50
10 45 55 60 40 70 80 35 50 65 48
8 100 99 98 97 96 95 94 93
5 0 25 50 75 100
12 10 20 30 40 50 60 70 80 90 100 49 51
3 50 50 50
7 49 49 49 49 49 49 49
6 51 52 53 54 55 56
4 0 0 0 0
9 100 100 100 100 100 100 100 100 100
15 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95

Sample Output 3

6
8
3
7
3
0
6
0
9
10

Problem Statement

Takahashi walks every day along a promenade consisting of N blocks arranged in a row. The blocks are numbered 1, 2, \ldots, N from left to right, and the beauty of the i-th block is represented by an integer A_i (the beauty can be negative).

Takahashi has a favorite place, which is the D-th block. He wants to choose an interval of exactly K consecutive blocks from the promenade that must include the D-th block, such that the total beauty is maximized.

Specifically, he decides an integer l representing the starting position of the interval, and selects K consecutive blocks from the l-th to the (l+K-1)-th. The value of l must satisfy all of the following conditions:

• 1 \leq l (the interval does not extend beyond the left end of the promenade)
• l + K - 1 \leq N (the interval does not extend beyond the right end of the promenade)
• l \leq D \leq l + K - 1 (the interval includes the favorite D-th block)

Among all valid choices of l, find the maximum value of the total beauty A_l + A_{l+1} + \cdots + A_{l+K-1}.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq K \leq N
• 1 \leq D \leq N
• -10^9 \leq A_i \leq 10^9
• It is guaranteed that at least one valid l exists.
• All input values are integers.

Sample Input 1

7 3 4
2 -1 5 3 -2 4 1

Sample Output 1

7

Sample Input 2

5 2 3
-3 -5 -1 -4 -2

Sample Output 2

-5

Sample Input 3

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

Sample Output 3

19

Sample Input 4

20 7 12
3 -1 4 1 5 -9 2 6 -5 3 5 8 -3 7 2 -4 6 1 -2 3

Sample Output 4

21

Sample Input 5

1 1 1
-1000000000

Sample Output 5

-1000000000

Problem Statement

Takahashi manages an irrigation water channel network consisting of N junction points. The junction points are numbered from 1 to N, and junction point 1 is the uppermost water source. The parent of junction point i (2 \leq i \leq N) is junction point P_i, and the entire structure forms a rooted tree with junction point 1 as the root. Water flows from parent to child.

Each junction point i currently holds V_i liters of water.

Takahashi wants to make the water volume at all junction points exactly 0 by performing the "drain" operation zero or more times. There is no upper limit on the number of operations, and the junction point chosen for each operation can be freely decided. The same junction point may be chosen multiple times.

One "drain" operation is performed as follows:

• Choose one junction point (let the chosen junction point be u).
• Simultaneously decrease the water volume by 1 at all junction points on the path from u to the root (junction point 1) in the tree (including u itself and junction point 1).

For example, if u = 1, only the water volume at junction point 1 decreases by 1.

However, after each operation is performed, the water volume at all junction points must be 0 or greater. That is, an operation that would result in the water volume at any junction point becoming negative cannot be performed.

Determine whether it is possible to make the water volume at all junction points exactly 0. If possible, output Yes; if impossible, output No.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq P_i \leq i - 1 (2 \leq i \leq N)
• 0 \leq V_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
1 1 2 2
7 4 2 1 2

Sample Output 1

Yes

Sample Input 2

3
1 1
1 1 1

Sample Output 2

No

Sample Input 3

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

Sample Output 3

Yes

Sample Input 4

25
1 1 1 2 2 3 3 4 4 5 5 6 7 7 8 9 10 10 12 12 14 16 16 20
35 10 15 6 7 2 9 4 1 5 1 4 2 6 3 4 0 4 1 3 2 5 1 2 3

Sample Output 4

No

Sample Input 5

1

1000000000

Sample Output 5

Yes

Problem Statement

Takahashi is planning a hike in a mountainous area. There are N locations in this mountainous area, and the elevation of location i (1 \leq i \leq N) is H_i.

There are M trails between locations, and the j-th (1 \leq j \leq M) trail bidirectionally connects location U_j and location V_j. The fatigue cost of traversing the j-th trail once is the absolute difference in elevation between its two endpoints, |H_{U_j} - H_{V_j}|.

Takahashi will travel from location 1 (the starting point) to location N (the destination) using only trails. During the trip, he is allowed to visit the same location multiple times and traverse the same trail multiple times. If the same trail is traversed multiple times, its fatigue cost is added each time it is traversed.

However, he can only use trails whose fatigue cost is at most K. Trails with fatigue cost greater than K cannot be used.

Find the minimum total fatigue cost when traveling from location 1 to location N using only passable trails.

If it is impossible to reach location N from location 1 using only passable trails, output -1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq K \leq 10^9
• 0 \leq H_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
• There is at most one trail connecting any pair of locations (no multiple edges)
• All input values are integers

Sample Input 1

5 6 5
10 14 8 12 16
1 2
1 3
2 4
3 4
2 5
4 5

Sample Output 1

6

Sample Input 2

4 4 3
0 10 20 30
1 2
2 3
3 4
1 4

Sample Output 2

-1

Sample Input 3

7 10 10
0 8 5 15 12 20 25
1 2
1 3
2 4
3 4
3 5
4 6
5 6
5 7
6 7
2 5

Sample Output 3

25

Problem Statement

Takahashi is working in a bioinformatics laboratory, analyzing gene expression levels. In this research, the expression level at each position of each sample is represented by one of three characters: H (high), M (medium), or L (low), and recorded as a string of these characters.

The laboratory has N samples, and their expression level sequences are recorded as strings S_1, S_2, \ldots, S_N. Takahashi also has a reference pattern P that is believed to be related to a specific function.

Aoki has decided to help Takahashi's research by creating an analysis program that counts how many times a modified pattern—obtained by reversing a part of the reference pattern—appears in each sample.

Specifically, Q queries are given. For the j-th query (1 \leq j \leq Q), a tuple of integers (i_j, l_j, r_j) is given, representing a sample number i_j, the left endpoint l_j, and the right endpoint r_j of an interval. The answer is determined by the following procedure.

Generation of the modified pattern: Reverse the substring of the reference pattern P from the l_j-th character to the r_j-th character (1-indexed, both endpoints inclusive), while keeping the remaining parts unchanged, to generate the modified pattern P'_j. The length of P'_j equals the length |P| of P.

For example, if P = HMLLM and l_j = 2, r_j = 4, then the substring from the 2nd to 4th characters MLL is reversed to LLM, resulting in P'_j = HLLMM.

Counting occurrences: Count the number of contiguous substrings of length |P| in sample S_{i_j} that match P'_j. More precisely, find the number of starting positions a (1 \leq a \leq |S_{i_j}| - |P| + 1) such that the substring of S_{i_j} from the a-th character to the (a + |P| - 1)-th character matches P'_j. If |S_{i_j}| < |P|, no valid starting position exists, so the occurrence count is 0. Even if occurrences overlap, they are counted separately as long as their starting positions differ.

Note that the modification operation is independent for each query; each time, the operation is applied to the original reference pattern P.

For each query, determine the above occurrence count.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq |P| \leq 5 \times 10^5
• 1 \leq |S_i| \leq 5 \times 10^5 (1 \leq i \leq N)
• \sum_{i=1}^{N} |S_i| \leq 5 \times 10^5
• P and each S_i consist only of H, M, L
• 1 \leq i_j \leq N (1 \leq j \leq Q)
• 1 \leq l_j \leq r_j \leq |P| (1 \leq j \leq Q)
• All inputs are given as integers or strings

Sample Input 1

2 4
HMLLM
HLLMMHMLLMHMLLM
LLMHMHLLMM
1 2 4
1 1 5
2 1 3
2 5 5

Sample Output 1

1
1
0
0

Sample Input 2

3 5
HML
HMLHML
LMHLMH
HHHH
1 1 1
1 1 3
2 1 3
3 2 2
2 2 3

Sample Output 2

2
0
2
0
1

Sample Input 3

5 12
HMLLHMMHLH
HMLLHMMHLHHMLLHMMHLH
HLMMLHMHLHMLLHMMHLLH
LLLLHHHHMMMMHMLLHMMHLH
MLHMLHMLHMLHMLHMLHMLH
HHMLLHMMHLHLLHMMHLLMHH
1 1 10
1 3 7
2 2 9
2 5 5
3 1 4
3 7 10
4 1 3
4 4 8
5 2 6
5 1 10
1 6 10
2 1 1

Sample Output 3

0
0
0
0
0
0
0
0
0
0
0
0

Sample Input 4

8 20
HMLLMHHLMLMHHLLMMHLMHLML
HMLLMHHLMLMHHLLMMHLMHLMLHMLLMHHLMLMHHLLMMHLMHLML
LLHHMMLMLHHMLLMHMLHMLMLLHMMHHLLMMHLMHLMLHMLLMHH
MMMMHHHHLLLLHMLLMHHLMLMHHLLMMHLMHLMLLLLLHHHHMMMM
HMLHMLHMLHMLHMLHMLHMLHMLHMLHMLHMLHML
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
MLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLML
HMLLMHHLMLMHHLLMMHLMHLMLLMLHMHMLMMHLLHHMMLMLHH
1 1 24
1 6 18
1 12 12
2 1 5
2 10 24
3 4 20
3 15 24
4 1 3
4 2 23
5 1 24
5 7 7
6 1 1
6 20 24
7 3 22
7 8 16
8 1 24
8 5 14
8 11 21
2 6 6
3 1 24

Sample Output 4

0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Sample Input 5

1 1
H
M
1 1 1

Sample Output 5

0