Problem Statement

A group of N people went on a trip. The members are numbered from 1 to N. Expenses incurred during the trip were each paid upfront by one of the members on behalf of the others. After the trip, they decided to settle all expenses fairly among everyone.

A total of M payments were made during the trip. For the i-th payment (1 \leq i \leq M), person P_i paid C_i yen upfront. This payment was for K_i members who used it, and the users are B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}. The person P_i who paid upfront may or may not be included among the users. For each payment, the cost is to be shared equally among the K_i users. That is, the amount each user should bear is \frac{C_i}{K_i} yen.

Considering all payments, define the settlement amount D_j for person j (1 \leq j \leq N) as follows:

D_j = \sum_{\substack{1 \leq i \leq M \\ P_i = j}} C_i \;-\; \sum_{\substack{1 \leq i \leq M \\ j \in \{B_{i,1}, \ldots, B_{i,K_i}\}}} \frac{C_i}{K_i}

In other words, D_j is the value obtained by subtracting "the total amount person j should have borne" from "the total amount person j actually paid upfront." If person j did not pay upfront for any payment, the total amount paid upfront is 0 yen. Similarly, if person j is not included as a user in any payment, the total amount they should bear is 0 yen.

If D_j is positive, person j should receive D_j yen. If D_j is negative, person j should pay |D_j| yen. If D_j = 0, no settlement is needed.

Determine the value of D_j for all N people. Note that it is guaranteed that every \frac{C_i}{K_i} is an integer, so D_j is always an integer as well.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq P_i \leq N
• 1 \leq C_i \leq 10^9
• 1 \leq K_i \leq N
• 1 \leq B_{i,1} < B_{i,2} < \ldots < B_{i,K_i} \leq N
• P_i is not necessarily included among B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}
• \frac{C_i}{K_i} is an integer
• \sum_{i=1}^{M} K_i \leq 10^5
• All input values are integers

Sample Input 1

3 2
1 6000 3 1 2 3
2 4000 2 2 3

Sample Output 1

4000
0
-4000

Sample Input 2

5 4
1 10000 5 1 2 3 4 5
3 6000 3 1 2 3
2 8000 2 2 4
5 3000 3 3 4 5

Sample Output 2

6000
0
1000
-7000
0

Sample Input 3

6 5
1 12000 6 1 2 3 4 5 6
2 9000 3 1 2 3
4 8000 4 1 4 5 6
6 5000 2 2 6
3 7000 2 3 5

Sample Output 3

5000
1500
-1500
4000
-7500
-1500

Problem Statement

Takahashi is helping run a balloon popping game booth at a school festival. There are N balloons lined up in a row at the venue, and the i-th balloon has a durability of H_i.

Takahashi's team has M darts, and the j-th dart has an attack power of P_j.

Takahashi can throw darts at most K times in total. In each throw, he chooses 1 dart from the M darts and 1 balloon from the N balloons, and throws that dart at that balloon. This reduces the chosen balloon's durability by the chosen dart's attack power.

Each dart can be used any number of times. He may also target the same balloon multiple times, and is free to throw different darts at the same balloon.

When a balloon's durability becomes 0 or less, it pops. He may also throw darts at already popped balloons, but such a throw still counts as one of his throws, and it does not increase the number of popped balloons.

Determine the maximum number of balloons that can be popped when Takahashi throws darts optimally.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq K \leq 10^{18}
• 1 \leq H_i \leq 10^{18} (1 \leq i \leq N)
• 1 \leq P_j \leq 10^{18} (1 \leq j \leq M)
• All input values are integers.

Sample Input 1

5 2 5
3 1 4 1 5
2 3

Sample Output 1

4

Sample Input 2

3 1 2
10 20 30
5

Sample Output 2

1

Sample Input 3

7 3 15
10 5 8 12 3 7 20
4 6 2

Sample Output 3

7

Sample Input 4

10 5 50
100 200 300 400 500 600 700 800 900 1000
3 7 10 5 2

Sample Output 4

2

Sample Input 5

1 1 1
1
1

Sample Output 5

1

Problem Statement

Takahashi is standing in front of a staircase with N steps. Takahashi is currently on step 0 (the ground) and aims to reach step N (the top).

In one move, Takahashi can move from his current step to the step that is 1 step above, 2 steps above, or 3 steps above. That is, when he is currently on step i, he can directly move to step i+1, step i+2, or step i+3. However, he only lands on the destination step and does not land on any intermediate steps.

Some steps of the staircase are deteriorated and broken. There are M broken steps, which are steps B_1, B_2, \ldots, B_M (all B_i are distinct). It is not possible to land on a broken step. However, it is possible to jump over a broken step (passing it without landing). For example, even if step i+1 is broken, Takahashi can move from step i to step i+2 or step i+3. It is guaranteed that step 0 (the ground) and step N (the top) are not broken.

Find the number of ways Takahashi can climb from step 0 to step N. If there is no valid way to climb, output 0. Since the answer can be very large, output the remainder when divided by 10^9 + 7.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq M \leq N - 1
• 1 \leq B_i \leq N - 1 (1 \leq i \leq M)
• All B_i are distinct
• B_1, B_2, \ldots, B_M are not necessarily in ascending order
• All inputs are integers

Sample Input 1

5 1
3

Sample Output 1

5

Sample Input 2

4 3
1 2 3

Sample Output 2

0

Sample Input 3

20 3
5 10 15

Sample Output 3

6728

Sample Input 4

1000 5
100 200 300 400 500

Sample Output 4

935523008

Sample Input 5

1 0

Sample Output 5

1

Problem Statement

Takahashi runs an event planning company and has received N event requests. The requests are numbered from 1 to N, and request i (1 \leq i \leq N) specifies a venue start time L_i, end time R_i, and reward V_i. Times are represented as integers.

Takahashi has access to only one venue and cannot hold multiple events during the same time period. Executing request i occupies the venue during the time period represented by the half-open interval [L_i, R_i) (from time L_i inclusive to time R_i exclusive). Requests i and j (i \neq j) are said to be compatible if their occupied time periods do not overlap, that is, if R_i \leq L_j or R_j \leq L_i holds. In particular, if one's end time equals the other's start time (e.g., R_i = L_j), they are compatible.

Meanwhile, his rival Aoki will carry out sabotage to minimize Takahashi's profit. Aoki selects exactly K of the N requests to cancel (the K cancelled requests must all be distinct). Aoki chooses which K requests to cancel so as to minimize the total reward Takahashi can ultimately obtain, anticipating that Takahashi will act optimally after the cancellation.

From the remaining N - K requests that were not cancelled, Takahashi selects 0 or more requests to execute such that every pair of selected requests is compatible, maximizing the total reward. Each request can be executed at most once. If 0 requests are selected, the total reward is 0.

Determine the total reward Takahashi obtains when Aoki cancels optimally and then Takahashi selects optimally from the remaining requests.

Constraints

• 1 \leq N \leq 8
• 0 \leq K \leq N
• 0 \leq L_i < R_i \leq 100
• 1 \leq V_i \leq 1000
• All input values are integers

Sample Input 1

3 1
0 2 5
2 4 3
0 3 10

Sample Output 1

8

Sample Input 2

4 2
0 5 100
5 10 100
0 10 50
3 7 50

Sample Output 2

50

Sample Input 3

6 2
0 3 10
3 6 20
6 9 10
1 5 25
4 8 15
0 9 30

Sample Output 3

30

Sample Input 4

8 3
0 10 50
10 20 60
20 30 70
0 15 100
15 30 90
5 25 80
0 30 200
12 18 40

Sample Output 4

110

Sample Input 5

1 1
0 100 1000

Sample Output 5

0

Problem Statement

A town has N intersections connected by N - 1 roads. Any two intersections can be reached from each other by following roads along exactly one unique path (that is, the intersections and roads form a tree structure).

The distance between intersection a and intersection b is defined as the number of roads traversed to travel from a to b. In particular, the distance from intersection a to itself is 0.

Initially, there are no shops at any intersection. Over a period of Q days, on day i (1 \leq i \leq Q), a new shop opens at intersection C_i. No intersection will have a shop open more than once. Once a shop opens, it continues to operate indefinitely.

When Aoki is standing at some intersection in the town, he feels happy if there is exactly 1 shop within distance R or less, because he can have that shop all to himself.

For each day, determine the number of intersections where Aoki would feel happy at the end of that day. That is, find the number of intersections x such that the number of shops within distance R from intersection x is exactly 1. Note that if intersection x itself has a shop (distance 0), it is also counted among the shops.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq N
• N + Q \leq 2 \times 10^5
• 1 \leq R \leq 20
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• The given graph is a tree
• 1 \leq C_i \leq N
• All C_i are distinct
• All input values are integers

Sample Input 1

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

Sample Output 1

3
3
3

Sample Input 2

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

Sample Output 2

6
0
0
0

Sample Input 3

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

Sample Output 3

4
8
9
13
8
7
4
2

Sample Input 4

40 20 4
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
6 13
7 14
7 15
8 16
9 17
10 18
10 19
11 20
12 21
13 22
14 23
15 24
16 25
17 26
18 27
19 28
20 29
21 30
22 31
23 32
24 33
25 34
26 35
27 36
28 37
29 38
30 39
31 40
38
34
22
5
27
15
40
1
19
30
8
36
24
12
3
33
10
29
6
17

Sample Output 4

5
10
16
13
15
19
17
8
7
5
4
4
3
3
2
2
0
0
0
1

Sample Input 5

1 1 20
1

Sample Output 5

1