Problem Statement

Takahashi is serving as a judge for a cooking contest. N chefs are participating in this contest, and each chef is assigned a number from 1 to N.

The contest uses M types of ingredients, numbered from 1 to M. Chef i specializes in C_i types of ingredients, and the numbers of the ingredients they specialize in are T_{i,1}, T_{i,2}, \ldots, T_{i,C_i}. When C_i = 0, chef i has no ingredients they specialize in.

As a result of the contest's preliminary round, chef i earned a score of V_i. The N chefs are ranked according to the following rules, and the top K chefs (ranked 1st through Kth) advance to the finals.

• A chef with a higher score is ranked higher (i.e., has a smaller rank number).
• Among chefs with the same score, the chef with the smaller chef number is ranked higher.

Under these rules, the ranking of all chefs is uniquely determined, and the K chefs who advance to the finals are also uniquely determined.

In the finals, the K advancing chefs will cook dishes using only ingredients that all of them commonly specialize in. That is, an ingredient can be used in the finals only if all K chefs who advanced to the finals specialize in that ingredient.

For Takahashi, find the number of ingredients that all K chefs advancing to the finals commonly specialize in. If there are no such ingredients, output 0.

Constraints

• 1 \leq K \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 0 \leq C_i \leq M
• \sum_{i=1}^{N} C_i \leq 2 \times 10^5
• 1 \leq V_i \leq 10^9
• 1 \leq T_{i,j} \leq M
• For each chef i, T_{i,1}, T_{i,2}, \ldots, T_{i,C_i} are all distinct
• All input values are integers

Sample Input 1

3 5 2
100 3 1 2 3
80 4 1 2 4 5
90 2 1 2

Sample Output 1

2

Sample Input 2

5 6 3
50 2 1 3
100 3 1 2 3
100 4 1 2 3 4
75 3 2 3 5
60 0

Sample Output 2

2

Sample Input 3

10 8 4
500 5 1 2 3 4 5
450 4 1 2 3 6
480 6 1 2 3 4 5 6
300 3 1 2 7
520 4 1 2 3 8
200 2 1 2
490 5 1 2 3 5 7
350 4 2 3 4 5
400 3 1 3 4
100 1 1

Sample Output 3

3

Problem Statement

Takahashi works in sports analytics. In a certain tournament, N players participated and competed over T rounds. Let S_{j,i} denote the score of player i (1 \leq i \leq N) in round j (1 \leq j \leq T).

Takahashi wants to identify rounds where a certain player overwhelmingly outperformed the others. Specifically, he defined a player being "outstanding" in a round as follows:

> In round j, let M_{j,i} be the maximum score among all players other than player i. If S_{j,i} \geq 2 \times M_{j,i} holds, then player i is said to be "outstanding" in round j.

Since all scores are at least 1, if player i is outstanding in round j, then S_{j,i} is the maximum score in that round, and every other player's score is at most half of it. Therefore, there is at most one outstanding player in any single round.

Determine the number of rounds, out of the T rounds, in which an outstanding player exists.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq T \leq 10^5
• N \times T \leq 10^6
• 1 \leq S_{j,i} \leq 10^9
• All input values are integers

Sample Input 1

3 4
10 3 4
5 6 5
1 1 3
7 4 4

Sample Output 1

2

Sample Input 2

3 3
5 6 5
10 8 9
100 99 100

Sample Output 2

0

Sample Input 3

5 6
100 200 50 30 40
90 80 85 88 91
1 1 1 1 1000000000
50 100 51 49 48
3 3 3 3 7
10 10 10 10 20

Sample Output 3

4

Sample Input 4

10 8
5 3 2 1 1 1 1 1 1 1
100 100 50 40 30 20 10 5 3 1
1000 400 499 500 200 100 50 25 12 6
7 7 7 7 7 7 7 7 7 14
999999999 500000000 1 1 1 1 1 1 1 1
1000000000 500000000 499999999 1 1 1 1 1 1 1
12 6 6 6 6 6 6 6 6 6
50 26 25 24 23 22 21 20 19 18

Sample Output 4

4

Sample Input 5

2 1
2 1

Sample Output 5

1

Problem Statement

Takahashi is in a vast sea area dotted with N islands. The islands are numbered from 1 to N, and island i is located at coordinates (X_i, Y_i) on a two-dimensional plane.

Takahashi travels from island to island using a small boat. From his current island, he can move to another island in one step if the Euclidean distance between them is at most D. Here, the Euclidean distance between island i and island j is defined as \sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2}. Note that he is allowed to revisit islands he has already visited.

Takahashi starts at island S and wants to reach island T. Find the minimum number of moves required to travel from island S to island T. If it is impossible to reach island T, output -1.

Constraints

• 2 \leq N \leq 1500
• 1 \leq D \leq 10^9
• 1 \leq S \leq N
• 1 \leq T \leq N
• S \neq T
• -10^9 \leq X_i \leq 10^9
• -10^9 \leq Y_i \leq 10^9
• If i \neq j, then (X_i, Y_i) \neq (X_j, Y_j)
• All input values are integers

Sample Input 1

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

Sample Output 1

2

Sample Input 2

4 2 1 4
0 0
1 1
2 0
100 100

Sample Output 2

-1

Sample Input 3

8 5 1 8
0 0
3 4
-2 3
1 -4
7 7
4 0
0 5
10 10

Sample Output 3

3

Problem Statement

Takahashi is working as a librarian and is in charge of a book inspection spanning N days.

This library has M books. To ensure that no deterioration or damage to books is overlooked, a standard has been established that each book j (1 \leq j \leq M) must be inspected on at least R_j days out of the N days.

On the other hand, the maximum number of books that can be inspected on day i (1 \leq i \leq N) is L_i. Also, the same book cannot be inspected multiple times on the same day, but the same book can be inspected again on a different day.

Takahashi is free to decide which books to inspect on which days. Determine whether it is possible to create an inspection plan that satisfies the inspection requirements for all books.

Specifically, determine whether there exists an inspection plan that satisfies all of the following conditions:

• The number of books inspected on each day i is at most L_i.
• The same book is not inspected more than once on the same day.
• The total number of days each book j is inspected is at least R_j.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq L_i \leq M (1 \leq i \leq N)
• 1 \leq R_j \leq N (1 \leq j \leq M)
• All input values are integers

Sample Input 1

3 4
2 3 2
1 2 1 2

Sample Output 1

Yes

Sample Input 2

2 3
2 2
2 2 1

Sample Output 2

No

Sample Input 3

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

Sample Output 3

Yes

Problem Statement

Takahashi manages the power supply system of a certain region. This region has N factories and K power plants, which are connected by transmission lines forming a power transmission network.

The locations are numbered from 1 to N + K, where locations 1 through N correspond to factories, and locations N + 1 through N + K correspond to power plants. Specifically, factory i (1 \leq i \leq N) is located at location i, and power plant k (1 \leq k \leq K) is located at location N + k.

The transmission network consists of N + K locations connected by M transmission lines. Each transmission line j (1 \leq j \leq M) bidirectionally connects location U_j and location V_j, and can transmit up to C_j megawatts of power per day. Specifically, letting f_j megawatts denote the amount of power flowing through transmission line j in the direction from location U_j to location V_j, the constraint -C_j \leq f_j \leq C_j must be satisfied. Here, f_j > 0 means power is transmitted from location U_j to location V_j, and f_j < 0 means power is transmitted from location V_j to location U_j.

Each power plant k (1 \leq k \leq K), while operational, can supply any amount of power between 0 and W_k megawatts per day. Each factory i (1 \leq i \leq N) needs to receive at least B_i megawatts of power per day to operate. A factory may receive more than B_i megawatts of power; it operates without issues even if surplus power flows in.

At each location, flow conservation must hold for the power balance. The net inflow \mathrm{net}(v) at location v is defined as follows:

\mathrm{net}(v) = \sum_{\substack{j :\, V_j = v}} f_j - \sum_{\substack{j :\, U_j = v}} f_j

To clarify the meaning of this formula: for transmission line j, when f_j > 0, power flows from U_j to V_j, so f_j flows into location V_j and f_j flows out of location U_j. When f_j < 0, the reverse holds. \mathrm{net}(v) equals the total inflow to location v minus the total outflow from location v, summed over all transmission lines connected to location v.

The following conditions must be satisfied at each location:

• If location v is factory i: \mathrm{net}(v) \geq B_i. That is, a net inflow of at least B_i megawatts must flow into factory i through the transmission lines.
• If location v is an operational power plant k: -W_k \leq \mathrm{net}(v) \leq 0. That is, power plant k can supply between 0 and W_k megawatts of power. Since the supplied power leaves the location, the net inflow is non-positive.
• If location v is a non-operational power plant: \mathrm{net}(v) = 0. It cannot supply power, but as long as inflow equals outflow, it can still function as a relay point through which power passes via transmission lines.

Initially, all K power plants are operational, but it is not guaranteed that all factories can secure the necessary power even in the initial state.

However, due to aging, power plants are expected to fail and shut down sequentially. Specifically, Q events occur in order. At each event t (1 \leq t \leq Q), power plant S_t fails and becomes non-operational. Once a power plant fails, it remains non-operational permanently. Note that Q \leq K, and not all power plants necessarily fail.

For the state immediately after each event occurs, determine whether all factories can secure the necessary power and continue operating. That is, after each event, answer whether there exists a way to route power such that, using only the currently operational power plants, the flow conservation conditions are satisfied and at least B_i megawatts of power is delivered to each factory i.

Constraints

• 1 \leq N \leq 32
• 1 \leq K \leq 32
• 0 \leq M \leq 300
• 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq W_k \leq 10^9 (1 \leq k \leq K)
• 1 \leq U_j < V_j \leq N + K (1 \leq j \leq M)
• 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
• There is at most one transmission line between any pair of locations (no multi-edges exist)
• 1 \leq Q \leq K
• 1 \leq S_t \leq K (1 \leq t \leq Q)
• S_1, S_2, \ldots, S_Q are all distinct (no power plant fails more than once)
• All input values are integers

Sample Input 1

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

Sample Output 1

Yes
No

Sample Input 2

2 2 3
3 3
6 6
1 2 2
1 3 6
2 4 3
1
2

Sample Output 2

No

Sample Input 3

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

Sample Output 3

Yes
No
No

Sample Input 4

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

Sample Output 4

Yes
Yes
No
No

Sample Input 5

1 1 0
1
1
1
1

Sample Output 5

No