Problem Statement

A math test was recently held in Aoki's class. There are N students in the class, each assigned a student number from 1 to N. The test score of student i (1 \leq i \leq N) is S_i points.

Aoki has been asked by the teacher to organize the students' grades. Aoki needs to answer Q questions. For the i-th question, he determines whether the score of the student with student number a_i is strictly higher than the score of the student with student number b_i. Here, "strictly higher" means that equality is not included, i.e., S_{a_i} > S_{b_i} holds. Note that a_i = b_i is possible, meaning a comparison of the same student with themselves may occur.

For each question, output Yes if S_{a_i} > S_{b_i}, and No otherwise (i.e., if S_{a_i} \leq S_{b_i}).

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 0 \leq S_i \leq 100 (1 \leq i \leq N)
• 1 \leq a_i \leq N (1 \leq i \leq Q)
• 1 \leq b_i \leq N (1 \leq i \leq Q)
• It is possible that a_i = b_i
• All input values are integers

Sample Input 1

3 4
80 65 80
1 2
2 1
1 3
3 1

Sample Output 1

Yes
No
No
No

Sample Input 2

5 6
72 85 60 85 90
5 2
2 4
1 3
4 2
3 5
2 1

Sample Output 2

Yes
No
Yes
No
No
Yes

Sample Input 3

10 8
45 78 92 65 100 38 72 0 55 100
5 10
10 5
6 8
8 6
3 1
1 2
4 7
9 4

Sample Output 3

No
No
Yes
No
Yes
No
No
No

Problem Statement

A school has N students, each assigned a student ID number from 1 to N.

At some point, an interesting rumor started. At the initial time (before any group work takes place), only the K students with student ID numbers 1, 2, \ldots, K know this rumor, and no other students know it.

From now on, M group work sessions will take place at this school, in order from the 1-st to the M-th. Note that the same pair may be paired together again in different group work sessions.

In the i-th (1 \leq i \leq M) group work session, the student with student ID A_i and the student with student ID B_i form a pair and work together. If at least one of the two paired students knows the rumor at the start of that group work session, then both students will know the rumor after that group work session ends. If neither of them knows the rumor, nothing changes.

The propagation of the rumor caused by a group work session affects all subsequent group work sessions.

Determine the number of students who know the rumor after all group work sessions have been completed.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq K \leq N
• 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
• The same pair may be paired together again in different group work sessions
• All input values are integers

Sample Input 1

5 3 1
1 2
2 3
4 5

Sample Output 1

3

Sample Input 2

8 5 2
3 5
2 4
4 6
5 6
7 8

Sample Output 2

5

Sample Input 3

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

Sample Output 3

9

Problem Statement

Takahashi is managing a seating chart with H rows and W columns. The seat at row i and column j of the seating chart is called seat (i, j). Each seat is assigned a group name represented by a single lowercase letter, and the group name of seat (i, j) is denoted G_{i,j}.

Takahashi wants to find all "unique seats" in the seating chart. A seat (i, j) is a "unique seat" if and only if it satisfies both of the following conditions simultaneously:

• Uniqueness in the row: Among the W seats in row i, seat (i, j) is the only one with group name G_{i,j}. That is, the only k (1 \leq k \leq W) satisfying G_{i,k} = G_{i,j} is k = j.
• Uniqueness in the column: Among the H seats in column j, seat (i, j) is the only one with group name G_{i,j}. That is, the only k (1 \leq k \leq H) satisfying G_{k,j} = G_{i,j} is k = i.

Takahashi wants to read the group names of all unique seats in order of increasing row number, and within the same row in order of increasing column number, and concatenate them into a single string.

Given the seating chart information, determine the above string. If no unique seats exist, determine the empty string.

Constraints

• 1 \leq H \leq 2000
• 1 \leq W \leq 2000
• H, W are integers.
• G_{i,j} (1 \leq i \leq H, 1 \leq j \leq W) is a lowercase letter (a through z).

Sample Input 1

3 3
abc
bca
cab

Sample Output 1

abcbcacab

Sample Input 2

2 2
aa
aa

Sample Output 2

Sample Input 3

4 6
abcdef
aghijk
almnop
aqrstu

Sample Output 3

bcdefghijklmnopqrstu

Sample Input 4

8 10
abcdefghij
abcdefghij
klmnopqrst
klmnopqrst
uvwxabcdef
uvwxabcdef
ghijklmnop
ghijklmnop

Sample Output 4

Sample Input 5

1 1
z

Sample Output 5

z

Problem Statement

Takahashi is highlighting important parts of his textbook with a fluorescent marker while studying for exams.

Consider a particular line in the textbook. This line contains N characters arranged in a horizontal row, numbered from left to right as positions 1, 2, \ldots, N.

The fluorescent marker Takahashi uses marks W consecutive characters each time it is used. Takahashi used this fluorescent marker a total of K times. In the i-th marking (1 \leq i \leq K), he chose a starting position L_i and marked the W consecutive characters from position L_i to position L_i + W - 1. The marking range never extends beyond the line (that is, 1 \leq L_i \leq N - W + 1 holds).

The same starting position may be chosen in different markings. Also, even if starting positions differ, their marking ranges may overlap. The number of times a character at each position is marked is the total number of marking operations that include that position.

After all marking operations are completed, determine how many times the character at each position was marked in total.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq W \leq N
• 1 \leq K \leq 2 \times 10^5
• 1 \leq L_i \leq N - W + 1 (1 \leq i \leq K)
• All inputs are integers

Sample Input 1

10 3 2
2
5

Sample Output 1

0 1 1 1 1 1 1 0 0 0

Sample Input 2

8 4 3
1
3
2

Sample Output 2

1 2 3 3 2 1 0 0

Sample Input 3

15 5 6
1
3
7
11
2
7

Sample Output 3

1 2 3 3 3 2 3 2 2 2 3 1 1 1 1

Problem Statement

Takahashi needs to make exactly one rope of exactly W centimeters in length.

Takahashi has N types of strings. The i-th type of string has a length of L_i centimeters, and he has C_i of them in stock. Different types of strings may have the same length.

Takahashi will select one or more of these strings and connect them in a straight line without cutting them, keeping their original lengths, to make a rope. The length of the resulting rope equals the sum of the lengths of the selected strings (there is no length reduction due to knots). He may use multiple strings of the same type, but he can use at most C_i strings of the i-th type.

Takahashi wants to minimize the number of strings used while ensuring that the total length of the selected strings is exactly W centimeters.

If it is possible to make a rope of exactly W centimeters, find the minimum number of strings needed. If it is impossible to make a rope of exactly W centimeters regardless of how the strings are chosen, output -1.

Constraints

• 1 \leq N \leq 100
• 1 \leq W \leq 50000
• 1 \leq L_i \leq W
• 1 \leq C_i \leq 10000
• All inputs are integers

Sample Input 1

3 10
3 2
5 3
7 1

Sample Output 1

2

Sample Input 2

2 7
3 2
5 1

Sample Output 2

-1

Sample Input 3

5 80
7 5
13 4
23 3
31 2
50 2

Sample Output 3

3

Sample Input 4

10 5000
3 100
7 200
11 150
19 80
29 60
53 40
97 30
181 20
337 15
631 8

Sample Output 4

12

Sample Input 5

1 1
1 1

Sample Output 5

1