Problem Statement

Takahashi is in charge of the award ceremony as a staff member of a programming contest.

There are N participants in this contest, and the final score of the i-th participant is P_i points.

Takahashi decided to award all participants whose final score is K points or more. During the ceremony, Takahashi claps for each awarded participant a number of times equal to that participant's final score. For example, he claps 80 times for a participant whose final score is 80 points.

Find the total number of times Takahashi claps. If there are no participants to be awarded, the total is 0.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq K \leq 100
• 1 \leq P_i \leq 100 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5 60
45 72 88 55 60

Sample Output 1

220

Sample Input 2

10 50
30 85 42 91 50 67 25 100 48 73

Sample Output 2

466

Sample Input 3

15 70
65 78 92 45 70 83 69 100 55 71 88 40 95 62 77

Sample Output 3

754

Problem Statement

Takahashi works as a manager of an orchard. In this orchard, there are N fruit trees lined up in a row, numbered Tree 1, Tree 2, \ldots, Tree N from left to right. Tree i (1 \leq i \leq N) bears exactly one fruit with a sweetness level of T_i.

Takahashi wants to harvest only the fruits that meet the shipping standard. A fruit meets the shipping standard if and only if its sweetness level is at least L and at most R.

Takahashi plans to select a contiguous interval of consecutively numbered trees and harvest all the fruits within that interval. Specifically, he chooses integers l, r (1 \leq l \leq r \leq N) and considers the interval consisting of Tree l, Tree l+1, \ldots, Tree r. If all fruits on the trees within this interval meet the shipping standard, the interval is called harvestable.

Find the maximum number of trees r - l + 1 contained in a harvestable interval. If no harvestable interval exists, output 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L \leq R \leq 10^9
• 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5 10 20
15 12 18 25 14

Sample Output 1

3

Sample Input 2

10 5 15
8 10 12 7 9 20 6 11 13 14

Sample Output 2

5

Sample Input 3

15 100 500
150 200 300 250 180 50 400 350 300 200 150 100 450 600 200

Sample Output 3

7

Problem Statement

Takahashi and Aoki are in the same class and competing based on their final exam results.

The final exam consists of N subjects, each with its own maximum score. The maximum score for the i-th subject is P_i points. The score for each subject is an integer between 0 and P_i, inclusive.

As a result of the exam, Takahashi scored A_i points and Aoki scored B_i points on the i-th subject.

Here, we define the score difference as the value obtained by subtracting Aoki's total score across all subjects from Takahashi's total score across all subjects. Takahashi wants to maximize this score difference.

Thanks to the teacher's arrangement, Takahashi can choose exactly 1 subject from the N subjects and retake that subject's exam. Takahashi's score on the retaken subject will be changed to any integer between 0 and that subject's maximum score, inclusive. The new score may be the same as the original score. Aoki's scores do not change.

When Takahashi optimally chooses the subject and sets his new score, find the maximum possible score difference after the retake. Note that this value may be negative.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq 10^9
• 0 \leq A_i \leq P_i
• 0 \leq B_i \leq P_i
• All inputs are integers.

Sample Input 1

3
100 100 100
60 80 50
70 70 70

Sample Output 1

30

Sample Input 2

5
200 150 300 100 250
200 100 250 80 50
150 120 200 90 100

Sample Output 2

220

Sample Input 3

8
1000000000 500 1000 200 300 400 600 800
0 500 1000 200 300 400 600 800
1000000000 0 0 0 0 0 0 0

Sample Output 3

3800

Problem Statement

Takahashi is trying to take all N courses at his university.

The courses are numbered from 1 to N, and each course is taken exactly once. Some courses have prerequisite courses, and in order to take such a course, all of its prerequisite courses must have been completed beforehand. A single course may have multiple prerequisites. Courses with no prerequisites can be taken from the beginning.

There are M prerequisite relationships given, each in the form: "In order to take course B_j, course A_j must have been completed first."

Takahashi takes courses one at a time. At each step, among the courses he has not yet taken whose prerequisites have all been completed (these are called available courses), he selects the one with the smallest number and takes it.

Output the order in which Takahashi takes all the courses.

It is guaranteed that there are no contradictions in the prerequisite relationships (i.e., no cycles exist), and that it is always possible to take all courses. Furthermore, the above rule uniquely determines the order of enrollment.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_j \leq N (1 \leq j \leq M)
• 1 \leq B_j \leq N (1 \leq j \leq M)
• A_j \neq B_j (1 \leq j \leq M)
• If i \neq j, then (A_i, B_i) \neq (A_j, B_j) (the same prerequisite relationship is not given more than once)
• There are no cycles in the prerequisite relationships
• All input values are integers

Sample Input 1

4 3
1 2
3 4
2 4

Sample Output 1

1 2 3 4

Sample Input 2

5 3
2 1
3 1
5 4

Sample Output 2

2 3 1 5 4

Sample Input 3

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

Sample Output 3

1 2 3 4 5 6 7 8 9 10

Sample Input 4

15 12
15 14
14 13
13 12
12 11
1 5
2 5
5 6
3 7
8 9
9 10
4 10
6 11

Sample Output 4

1 2 3 4 5 6 7 8 9 10 15 14 13 12 11

Sample Input 5

1 0

Sample Output 5

1

Problem Statement

Takahashi is researching algorithms related to sequences. Today, he is working on a subsequence matching problem in sequences.

You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N and a pattern sequence P = (P_1, P_2, \ldots, P_K) of length K. Each element of the sequence A and the pattern sequence P is a positive integer.

Takahashi wants to find the number of ways to choose K distinct positions from the sequence A such that the subsequence formed by those positions, preserving the original order, matches the pattern sequence P.

More precisely, find the number of index tuples (i_1, i_2, \ldots, i_K) satisfying 1 \leq i_1 < i_2 < \cdots < i_K \leq N such that A_{i_j} = P_j holds for all j (1 \leq j \leq K).

Note that if the chosen index tuples differ in even one position, they are counted as distinct selections, even if the values of all selected elements are the same.

Since the answer can be very large, find it modulo 10^9 + 7.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq K \leq 100
• K \leq N
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq P_j \leq 10^9 (1 \leq j \leq K)
• All inputs are integers

Sample Input 1

5 2
1 2 1 2 1
1 2

Sample Output 1

3

Sample Input 2

8 3
3 1 4 1 5 9 2 6
1 5 6

Sample Output 2

2

Sample Input 3

15 4
2 3 2 3 2 3 2 3 2 3 2 3 2 3 2
2 3 2 3

Sample Output 3

126