Problem Statement

Takahashi is in charge of purchasing supplies for his company. The company handles N types of supplies, numbered from 1 to N. The actual price of supply i is P_i yen.

One day, it was discovered that the old price list Takahashi had been using contained errors. In this old price list, the price of supply i is listed as Q_i yen.

Takahashi needs to report the difference between the actual purchase amount and the estimated amount based on the old price list for each department's purchase request.

Today, purchase requests were received from M departments. The j-th department wishes to purchase K_j types of supplies, one of each, and the supply numbers they wish to purchase are C_{j,1}, C_{j,2}, \ldots, C_{j,K_j}. The same supply number does not appear more than once in the same department's purchase request list.

For each department, find the value obtained by subtracting the estimated total amount based on the old price list from the actual total amount, that is:

\sum_{k=1}^{K_j} (P_{C_{j,k}} - Q_{C_{j,k}})

This value may be negative.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq Q_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq K_j \leq N (1 \leq j \leq M)
• 1 \leq C_{j,k} \leq N (1 \leq j \leq M, 1 \leq k \leq K_j)
• C_{j,1}, C_{j,2}, \ldots, C_{j,K_j} are pairwise distinct (1 \leq j \leq M)
• \sum_{j=1}^{M} K_j \leq 2 \times 10^5
• All inputs are integers

Sample Input 1

3 2
100 200 300
90 250 280
2 1 3
3 1 2 3

Sample Output 1

30
-20

Sample Input 2

4 3
50 30 100 200
100 80 50 300
1 1
2 3 4
4 1 2 3 4

Sample Output 2

-50
-50
-150

Sample Input 3

8 5
500 1200 800 350 960 1500 2200 430
480 1300 750 400 1000 1450 2100 500
3 1 4 7
2 2 6
5 1 2 3 4 5
1 8
4 5 6 7 8

Sample Output 3

70
-50
-120
-70
40

Sample Input 4

10 8
1000000000 999999999 500000000 123456789 777777777 100 200 300 999999 1
900000000 1000000000 600000000 123456790 777777776 200 100 400 999998 2
3 1 2 3
4 4 5 6 7
2 8 9
1 10
5 1 3 5 7 10
10 1 2 3 4 5 6 7 8 9 10
2 1 10
3 6 7 8

Sample Output 4

-1
0
-99
-1
100
-101
99999999
-100

Sample Input 5

1 1
1000000000
1
1 1

Sample Output 5

999999999

Problem Statement

Takahashi works as a gardener and is responsible for managing N sections of lawn arranged in a horizontal row. Each section is numbered from 1 to N from left to right.

Initially, the moisture level of every section is 0. The target moisture level of the j-th section (1 \leq j \leq N) is T_j.

Takahashi waters the lawn using a sprinkler. In one operation, he chooses a starting position, an integer i (1 \leq i \leq N-K+1), and increases the moisture level of each of the K consecutive sections from section i to section i+K-1 by 1.

Takahashi can repeat this operation any number of times (including 0 times). The starting position can be freely chosen for each operation, and the same starting position can be chosen multiple times.

Determine whether it is possible to make the moisture level of every section exactly equal to its target moisture level.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 0 \leq T_j \leq 10^9 (1 \leq j \leq N)
• All input values are integers.

Sample Input 1

5 3
2 3 3 2 1

Sample Output 1

No

Sample Input 2

6 2
1 2 2 1 0 1

Sample Output 2

No

Sample Input 3

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

Sample Output 3

No

Problem Statement

Takahashi is conducting an evacuation simulation inside a building.

The building has N rooms and M corridors. The rooms are numbered from 1 to N, and each corridor bidirectionally connects two distinct rooms. There is at most one corridor connecting any pair of rooms.

There is no limit on the number of people that can pass through corridors or be in rooms. Multiple evacuees can use the same corridor in the same turn, and any number of evacuees can be in the same room without issue. Each evacuee's actions do not affect the others.

There are K evacuees in the building. Evacuee i (1 \leq i \leq K) is initially in room S_i. Different evacuees may be in the same room.

Additionally, fires have broken out in Q rooms of the building. The rooms on fire are P_1, P_2, \ldots, P_Q, all of which are distinct. Fires continue to burn throughout the simulation but do not spread to other rooms.

Room T is the emergency exit, and it is not on fire. All evacuees have complete knowledge of the entire graph structure, fire locations, and positions of other evacuees, and they all act optimally so that everyone can reach room T. Each evacuee can independently choose their action (moving to a different room or staying) within the same turn.

Simulation Progression

The simulation proceeds in turns. Once an evacuee has been eliminated or has completed evacuation, they do not participate in subsequent turns.

Initial Processing (Before Turn 1)

At the start of the simulation, the following processing occurs:

• Evacuees whose initial position is room T immediately complete evacuation.
• Evacuees whose initial position is a room on fire are immediately eliminated and fail to evacuate.

Due to the constraints, room T is never on fire, so no evacuee can satisfy both conditions.

Processing Each Turn

After that, the following processing occurs in each turn in this order:

1. Movement Phase: All evacuees who have neither been eliminated nor completed evacuation act simultaneously. Each evacuee chooses either to move to one adjacent room directly connected to their current room by a corridor, or to stay in their current room. In a single movement phase, an evacuee can move at most one corridor (to one adjacent room).
2. Evacuation Completion Check: Evacuees who are in room T after moving complete evacuation.
3. Elimination Check: Evacuees who are in a room on fire after moving are eliminated. Due to the constraints, room T is never on fire, so an evacuee who completed evacuation in step 2 will not be eliminated in this step.

Note: Moving to a room on fire is not prohibited, but doing so results in elimination during the elimination check. Therefore, since an evacuee can move at most one adjacent room per movement phase, it is impossible to "pass through" a room on fire to reach the other side.

Objective

Determine whether all evacuees can reach room T without being eliminated. If everyone can reach it, find the minimum number of turns required for all evacuees to complete evacuation.

If all evacuees have already completed evacuation at the start of the simulation (i.e., everyone's initial position is room T), the required number of turns is 0.

If even one evacuee cannot avoid elimination, then evacuation of everyone is impossible. In particular, if any evacuee's initial position is a room on fire, they are eliminated at the start, so evacuation is necessarily impossible in such cases.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq K \leq 2 \times 10^5
• 0 \leq Q \leq N
• 1 \leq T \leq N
• 1 \leq U_i, V_i \leq N \ (1 \leq i \leq M)
• U_i \neq V_i \ (1 \leq i \leq M)
• There is at most one corridor connecting any pair of rooms
• 1 \leq S_i \leq N \ (1 \leq i \leq K)
• S_i may contain duplicates
• 1 \leq P_j \leq N \ (1 \leq j \leq Q)
• All P_j are distinct
• P_j \neq T for all j
• The graph is not necessarily connected
• An evacuee's initial position may be a room on fire
• All input values are integers

Sample Input 1

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

Sample Output 1

3

Sample Input 2

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

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

3

Sample Input 4

20 19 10 4 20
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 20
4 16
7 17
10 18
13 19
1 3 5 7 9 11 13 15 20 1
16 17 18 19

Sample Output 4

15

Sample Input 5

1 0 1 0 1
1

Sample Output 5

0

Problem Statement

Takahashi is playing a puzzle game where N blocks are arranged in a row.

The i-th block from the left has an integer A_i written on it. This value can be positive or negative.

Takahashi can perform the following operation any number of times (zero or more times).

Operation: Choose K consecutive blocks and remove all of them. The removed blocks disappear, and the remaining blocks are shifted to the left to form a single row again.

Takahashi wants to maximize the sum of the integers written on the blocks that remain in the end.

If no blocks remain, the sum is defined to be 0.

Find the maximum possible sum of the integers written on the remaining blocks when the operations are performed optimally.

Constraints

• 1 \leq K \leq N \leq 10^6
• -10^9 \leq A_i \leq 10^9
• All inputs are integers

Sample Input 1

5 2
3 -5 4 -2 1

Sample Output 1

4

Sample Input 2

6 3
-1 2 -3 4 -5 6

Sample Output 2

7

Sample Input 3

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

Sample Output 3

21

Sample Input 4

30 5
12 -5 -20 7 3 -8 15 -2 6 -11 4 9 -30 18 -1 5 -6 14 -9 2 -3 10 -12 8 1 -7 16 -4 -15 11

Sample Output 4

74

Sample Input 5

1 1
-1000000000

Sample Output 5

0

Problem Statement

Takahashi is a quality control manager at a food manufacturer. For the development of a new product, he plans to use N types of raw materials, but some of these raw materials may contain substances that cause allergies.

The N types of raw materials are numbered from 1 to N. Each raw material is either an "allergen" or "safe."

Takahashi asked M monitors to cooperate and conducted allergy tests.

Specifically, each monitor j (1 \leq j \leq M) is assigned a set of raw materials S_j \subseteq \{1, 2, \ldots, N\}. Let k_j denote the number of elements in S_j, and let the elements of S_j be represented as s_{j,1}, s_{j,2}, \ldots, s_{j,k_j}. The same raw material may be assigned to multiple monitors. There may also be raw materials that are not assigned to any monitor.

Monitor j consumes all raw materials in S_j simultaneously. If at least one allergen is included among the consumed raw materials, monitor j shows an allergic reaction. If all consumed raw materials are safe, no allergic reaction occurs for monitor j. Note that whether a raw material is an allergen is an inherent property of the raw material itself, and the result does not change regardless of which monitor consumes it.

As a result of the tests, it was determined for each monitor whether they "had an allergic reaction" or "had no reaction." This result is represented by R_1, R_2, \ldots, R_M. R_j = 1 means monitor j had an allergic reaction, and R_j = 0 means monitor j had no reaction.

From these results, Takahashi wants to know how many possible patterns of allergen combinations exist.

That is, among the 2^N combinations where each of the N types of raw materials is designated as either an allergen or safe, find the number of combinations that satisfy all of the following conditions:

• For every monitor j with R_j = 1, at least one allergen is contained in S_j.
• For every monitor j with R_j = 0, no allergens are contained in S_j.

Since the answer can be very large, output the remainder when divided by 998244353. If no valid combination exists, output 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 20
• 1 \leq k_j \leq N (1 \leq j \leq M), where k_j is the number of raw materials consumed by monitor j.
• 1 \leq s_{j,i} \leq N (1 \leq j \leq M, 1 \leq i \leq k_j), where s_{j,i} is the number of a raw material consumed by monitor j.
• For each j, s_{j,1}, s_{j,2}, \ldots, s_{j,k_j} are all distinct.
• \sum_{j=1}^{M} k_j \leq 2 \times 10^5
• R_j \in \{0, 1\} (1 \leq j \leq M)
• All input values are integers.

Sample Input 1

3 2
2 1 2
2 2 3
1 0

Sample Output 1

1

Sample Input 2

2 2
1 1
1 1
0 1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

2

Sample Input 4

30 12
5 1 2 3 4 5
6 4 5 6 7 8 9
4 10 11 12 13
7 2 8 14 15 16 17 18
3 19 20 21
5 1 10 19 22 23
6 6 12 18 24 25 26
4 3 14 22 27
5 7 15 20 28 29
6 9 13 17 21 25 30
3 11 16 24
4 5 23 26 30
1 0 1 1 1 1 1 1 1 0 0 1

Sample Output 4

19587

Sample Input 5

1 1
1 1
0

Sample Output 5

1