Problem Statement

Takahashi is the administrator of a certain system. To log in to this system, one must correctly enter a password consisting of lowercase English letters of length N.

However, due to a server failure, part of the data storing the password has been corrupted. Fortunately, M characters of the password were successfully recovered. Specifically, for the i-th (1 \leq i \leq M) piece of recovered data, it is known that the P_i-th character of the password is the character C_i. The characters at all other positions are unknown.

As a temporary fix, Takahashi modified the password verification system as follows:

• For each position j (1 \leq j \leq N) of the input string of length N: if the data at position j has been recovered (that is, P_i = j for some i), check whether the j-th character of the input string matches C_i.
• If the data at position j has not been recovered, any character is accepted at that position.
• If the characters match at all recovered positions, the password is judged to be correct.

Aoki is attempting to log in to this system and has prepared Q candidate strings T_1, T_2, \ldots, T_Q. For each candidate string, determine whether it would be judged as a correct password.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq M \leq N
• 1 \leq Q \leq 10^3
• 1 \leq P_i \leq N
• All P_i are distinct
• C_i is a lowercase English letter
• Each T_j is a string of length N consisting of lowercase English letters

Sample Input 1

5 2 3
1 a
4 d
abcde
xbcde
abcdz

Sample Output 1

Yes
No
Yes

Sample Input 2

3 0 2
abc
xyz

Sample Output 2

Yes
Yes

Sample Input 3

10 4 5
2 b
5 e
7 g
10 z
abcdefghiz
xbxdexgxxz
abcdeagxyz
xbxdexhxxz
abcdefghij

Sample Output 3

Yes
Yes
Yes
No
No

Problem Statement

Takahashi is in charge of academic affairs at a school and manages the students' test results. There are N students in this school, and each student is identified by a student number from 1 to N.

Recently, multiple quizzes were administered, and a total of M answer sheets were submitted. Each answer sheet records the student number of the student who submitted it and the score of that answer sheet (an integer between 0 and 100, inclusive). It is possible that the same student submitted multiple answer sheets, and there may also be students who did not submit any answer sheets (students who were absent from all quizzes).

To identify students with poor performance, Takahashi decided to determine "students requiring supplementary lessons" based on the following criteria:

For students who submitted at least one answer sheet, if the arithmetic mean of the scores of all answer sheets submitted by that student is strictly less than a predetermined threshold score T, that student is considered a "student requiring supplementary lessons." Students who did not submit any answer sheets are excluded from the evaluation and are not counted as students requiring supplementary lessons.

On behalf of Takahashi, find the number of students requiring supplementary lessons.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq T \leq 100
• 1 \leq c_i \leq N (1 \leq i \leq M)
• 0 \leq s_i \leq 100 (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

5 7 60
1 50
1 40
2 80
2 70
3 55
4 60
4 65

Sample Output 1

2

Sample Input 2

8 10 50
1 50
1 50
2 49
2 51
3 0
3 0
4 100
5 30
5 20
6 49

Sample Output 2

3

Sample Input 3

10 15 70
1 90
1 80
1 70
2 60
2 50
3 100
4 65
4 70
4 68
6 40
6 30
7 70
8 69
8 71
9 0

Sample Output 3

4

Problem Statement

Takahashi is organizing the bookshelf in his house. The bookshelf contains N books arranged in a row, numbered 1, 2, \ldots, N from left to right. Book i has a satisfaction value of A_i and a weight of B_i.

Takahashi wants to select one or more consecutive books from the bookshelf and move them to a new shelf. Specifically, he chooses integers l, r (1 \leq l \leq r \leq N) and takes out all books l, l+1, \ldots, r.

However, there is a limit to the weight Takahashi can carry at once, so the total weight of the books in the selected interval must be at most K. That is, the following condition must be satisfied:

B_l + B_{l+1} + \cdots + B_r \leq K

Among all choices of l, r that satisfy this condition, find the maximum value of the total satisfaction A_l + A_{l+1} + \cdots + A_r.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{15}
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers
• There exists at least one interval (l, r) (1 \leq l \leq r \leq N) such that the total weight is at most K

Sample Input 1

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

Sample Output 1

15

Sample Input 2

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

Sample Output 2

25

Sample Input 3

10 1000000000000000
100 200 300 400 500 600 700 800 900 1000
1 1 1 1 1 1 1 1 1 1

Sample Output 3

5500

Problem Statement

Takahashi works as a delivery person. Today, he must head to the delivery destination as quickly as possible to deliver a package.

The delivery area contains N locations, numbered from 1 to N. Takahashi starts from the distribution center at location 1 and aims to reach the delivery destination at location N.

There are M one-way roads between the locations. The i-th road (1 \leq i \leq M) is a one-way road from location U_i to location V_i, and it takes C_i time to travel along this road. There may be multiple roads for the same pair of locations (U_i, V_i).

Takahashi may pass through the same location more than once. Find the shortest time required to travel from the distribution center (location 1) to the delivery destination (location N).

It is guaranteed that location N is reachable from location 1.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq U_i \leq N
• 1 \leq V_i \leq N
• U_i \neq V_i
• 1 \leq C_i \leq 10^9
• The same pair (U_i, V_i) may be given multiple times
• Location N is reachable from location 1
• All input values are integers

Sample Input 1

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

Sample Output 1

6

Sample Input 2

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

Sample Output 2

26

Sample Input 3

10 15
1 2 1000000000
1 3 500000000
2 4 300000000
3 4 200000000
3 5 400000000
4 6 100000000
5 6 150000000
5 7 250000000
6 7 50000000
6 8 200000000
7 8 100000000
7 9 300000000
8 9 150000000
8 10 400000000
9 10 100000000

Sample Output 3

1200000000

Problem Statement

Takahashi is a librarian at a certain library. This library has N shelves, each numbered from 1 to N.

The library holds M books in its collection. Multiple books may be placed on the same shelf. For each book i (1 \leq i \leq M), the shelf number S_i where the book is placed and its page count D_i are recorded.

Aoki is a library user. Aoki performs Q searches. For each search j (1 \leq j \leq Q), he specifies a shelf number range [L_j, R_j] and a minimum page count T_j, and wants to find "the number of books placed on shelves with numbers between L_j and R_j (inclusive) that have a page count of at least T_j."

However, the library's search system has a bug: the number of books displayed as the search result is the actual count minus a non-negative integer K. If the result would be negative, 0 is displayed instead.

For each search, determine the value displayed by the system.

That is, letting C_j be the number of books placed on shelves with numbers between L_j and R_j (inclusive) and with a page count of at least T_j, output \max(C_j - K, 0).

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq Q \leq 10^5
• 0 \leq K \leq M
• 1 \leq S_i \leq N (1 \leq i \leq M)
• 1 \leq D_i \leq 10^9 (1 \leq i \leq M)
• 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
• 1 \leq T_j \leq 10^9 (1 \leq j \leq Q)
• All input values are integers.

Sample Input 1

3 4 3 1
1 100
1 50
2 200
3 150
1 2 100
2 3 150
1 3 10

Sample Output 1

1
1
3

Sample Input 2

4 3 4 0
4 120
2 80
4 200
1 1 50
1 3 100
3 4 150
2 2 1

Sample Output 2

0
0
1
1

Sample Input 3

8 12 8 2
1 300
2 120
2 500
3 450
3 200
4 600
5 50
5 700
6 400
7 800
8 10
8 900
1 8 400
2 5 200
5 8 600
1 3 1000
4 4 1
6 8 350
3 7 750
8 8 5

Sample Output 3

5
3
1
0
0
1
0
0

Sample Input 4

20 30 15 3
1 100
1 500
2 250
2 800
3 150
3 900
4 400
4 50
5 1000
5 300
6 600
6 610
7 200
7 700
8 720
9 330
9 340
10 100
10 10000
11 450
12 460
12 470
13 480
14 490
15 5000
16 510
17 520
18 530
19 540
20 550
1 20 500
1 5 200
6 10 600
10 10 1000
11 15 460
16 20 525
3 7 700
8 12 50
13 17 480
2 2 1
4 9 1000
15 15 4999
1 20 10001
9 14 335
5 16 510

Sample Output 4

12
4
2
0
2
0
0
5
2
0
0
0
0
4
5

Sample Input 5

1 1 5 1
1 1000000000
1 1 1
1 1 999999999
1 1 1000000000
1 1 1000000000
1 1 1000000000

Sample Output 5

0
0
0
0
0