Problem Statement

Takahashi works at a bento (lunch box) shop. The shop offers N types of side dishes, numbered from 1 to N. The price of side dish i is W_i yen.

Today, there are M orders. The j-th order has K_j types of side dishes selected, specifically side dishes A_{j, 1}, A_{j, 2}, \dots, A_{j, K_j}. The same side dish is never selected more than once within the same order.

For each order, calculate the total price of the selected side dishes.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^5
• 1 \leq W_i \leq 10^4 (1 \leq i \leq N)
• 1 \leq K_j \leq N (1 \leq j \leq M)
• 1 \leq A_{j, k} \leq N (1 \leq j \leq M,\ 1 \leq k \leq K_j)
• In the j-th order, A_{j, 1}, A_{j, 2}, \dots, A_{j, K_j} are all distinct
• \displaystyle \sum_{j=1}^{M} K_j \leq 10^6
• All input values are integers

Sample Input 1

4 3
300 500 120 450
2 1 3
3 2 4 1
1 2

Sample Output 1

420
1250
500

Sample Input 2

5 4
1000 250 400 800 150
5 1 2 3 4 5
2 5 2
3 3 1 4
1 4

Sample Output 2

2600
400
2200
800

Sample Input 3

9 6
130 260 390 520 150 280 410 540 170
4 1 3 5 7
3 9 2 4
5 8 6 4 2 1
2 5 9
6 3 4 5 6 7 8
1 2

Sample Output 3

1080
950
1730
320
2290
260

Sample Input 4

20 10
95 180 260 340 420 510 605 715 830 940 55 165 275 385 495 610 720 845 960 1000
5 1 5 10 15 20
8 2 4 6 8 12 14 16 18
10 1 2 3 4 5 6 7 8 9 10
7 11 12 13 14 15 16 17
3 19 20 1
12 20 18 16 14 12 10 8 6 4 2 1 3
1 11
9 5 7 9 11 13 15 17 19 20
4 3 6 9 12
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Sample Output 4

2950
3750
4895
2705
2055
6045
55
5360
1765
10405

Sample Input 5

1 1
9999
1 1

Sample Output 5

9999

Problem Statement

Takahashi is conducting a message forwarding experiment with a group of N members.

The members are numbered from 1 to N, and each member i (1 \leq i \leq N) has exactly one predetermined forwarding destination member number P_i (where P_i \neq i).

Takahashi gives a message to member 1. The message is always held by exactly one member, and initially member 1 holds it. A member who receives the message is recorded as received. Member 1 is considered to have received the message at the start, and is thus marked as received.

After that, forwarding is repeated according to the following rules:

1. Let i be the member currently holding the message.
2. Check whether member P_i, the forwarding destination of member i, has already received the message.

• If member P_i has not yet received the message, member i forwards the message to member P_i. As a result, member i no longer holds the message, and member P_i now holds the message. Member P_i is recorded as received. Then, return to step 1.
• If member P_i has already received the message, no forwarding takes place, and the experiment ends with member i still holding the message.

Determine the number of members who have been recorded as received by the time the experiment ends (including member 1).

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq N
• P_i \neq i (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

4
2 3 4 1

Sample Output 1

4

Sample Input 2

6
3 1 2 5 6 4

Sample Output 2

3

Sample Input 3

10
2 3 1 5 6 7 8 9 10 4

Sample Output 3

3

Problem Statement

Takahashi has been put in charge of managing a flower bed in the garden.

The flower bed consists of N sections arranged in a row, numbered section 1, section 2, …, section N from left to right. Initially, the soil in section i contains A_i liters of moisture.

Takahashi will perform M operations in order. In the j-th operation (1 \leq j \leq M), for every section in the contiguous range from section L_j to section R_j, he changes the moisture level by D_j liters. That is, he adds D_j to the moisture level of each such section (a positive D_j means watering, and a negative D_j means draining).

It is guaranteed that at any point in time, the moisture level of each section is between 0 and 10^{18}, inclusive.

After all operations are completed, determine the moisture level of each section.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
• -10^9 \leq D_j \leq 10^9 (1 \leq j \leq M)
• At any point in time, the moisture level of each section is between 0 and 10^{18}, inclusive
• All input values are integers

Sample Input 1

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

Sample Output 1

12 6 9 7 5

Sample Input 2

8 5
100 200 300 400 500 600 700 800
1 8 -50
3 6 100
1 4 -30
5 8 200
2 7 10

Sample Output 2

20 130 330 430 760 860 860 950

Sample Input 3

10 8
1000000000 500000000 0 300000000 700000000 100000000 999999999 250000000 800000000 450000000
1 10 1000000000
3 7 -500000000
1 5 200000000
6 10 300000000
2 4 -100000000
8 10 -200000000
1 1 500000000
5 9 100000000

Sample Output 3

2700000000 1600000000 600000000 900000000 1500000000 1000000000 1899999999 1450000000 2000000000 1550000000

Problem Statement

Takahashi is planning a hiking course in a mountainous area. This mountainous area has N locations, each numbered from 1 to N. The locations are connected by M bidirectional mountain trails. However, it is not guaranteed that all locations are reachable from each other via trails.

Each location i (1 \leq i \leq N) has an elevation H_i.

Takahashi wants to choose a route starting from location 1 (the trailhead) and reaching location N (the summit observation deck). Here, a route is a sequence of locations p_1, p_2, \ldots, p_L that satisfies all of the following conditions:

• p_1 = 1 and p_L = N.
• For all 1 \leq k \leq L-1, there exists a mountain trail connecting location p_k and location p_{k+1}.
• p_1, p_2, \ldots, p_L are all distinct (no location is visited more than once).

The number of locations L included in a route is called the number of waypoints of that route. The number of waypoints includes both the starting location 1 and the destination location N. From the above conditions, L \geq 2.

Additionally, the maximum elevation among all locations visited along the route, namely \max(H_{p_1}, H_{p_2}, \ldots, H_{p_L}), is called the maximum elevation of that route.

The higher the maximum elevation of a route, the greater the risk of altitude sickness. Takahashi wants to minimize the risk of altitude sickness as much as possible. On the other hand, choosing a route that passes through many locations will exhaust his stamina. Therefore, Takahashi has decided to choose from routes whose number of waypoints L is at most K.

Among all routes with a number of waypoints at most K, find the minimum achievable maximum elevation.

If no valid route exists (i.e., it is impossible to reach location N from location 1 with at most K waypoints), output -1.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 2 \times 10^5
• 2 \leq K \leq N
• 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
• There is at most one trail connecting any pair of locations (no multi-edges)
• There are no self-loops
• The graph is not necessarily connected
• All input values are integers

Sample Input 1

5 6 4
10 50 30 20 40
1 2
2 3
3 5
1 4
4 5
2 5

Sample Output 1

40

Sample Input 2

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

Sample Output 2

-1

Sample Input 3

8 10 5
5 100 3 7 200 4 8 6
1 2
1 3
2 5
3 4
4 6
6 7
7 8
5 8
2 8
3 7

Sample Output 3

8

Sample Input 4

10 15 4
10 500 20 15 300 25 12 8 400 30
1 2
1 3
1 7
2 5
3 4
4 6
6 10
7 8
8 10
5 10
2 10
3 10
4 10
7 10
9 10

Sample Output 4

30

Sample Input 5

2 1 2
1000000000 1
1 2

Sample Output 5

1000000000

Problem Statement

There are N people, and we consider assigning each of them to one of 2 teams. Either team may be empty.

This problem deals with declarations. Declarations are numbered 1, 2, \ldots in the order they are added. Initially, there are 0 declarations. Each declaration consists of a pair of two people (u, v) as the target, and a content c. The content c is one of 0 (should be on the same team), 1 (should be on different teams), or X (undetermined). The pair of people u and v is symmetric; (u, v) and (v, u) represent the same pair. Multiple declarations may exist for the same pair of people.

Perform Q operations in order. There are two types of operations:

• A u v c (Add operation)

Append a declaration targeting the pair of people u and v to the end. The content of the added declaration is c.

• R k (Propagate operation)

Read the current content of declaration k, and overwrite the content of declaration k+1 with the value obtained by adding 1 to it. The target pair of people for declaration k+1 does not change. Also, the content of declaration k does not change.

Here, addition is defined as follows: 0 + 1 = 1, 1 + 1 = 0, X + 1 = X (remains undetermined).

Note: The R operation may change the content of a declaration. In particular, if the content of declaration k is X, the content of declaration k+1 is overwritten to X (even if it was originally 0 or 1). The current content of a declaration depends on the history of all operations performed up to that point.

After each operation, determine the number of good determination methods based on all existing declarations and their current contents at that point, modulo 998244353. The terms are defined below.

Determination Method

A determination method is a way to independently choose and write either 0 or 1 into each declaration whose content is X among all current declarations, making all declaration contents either 0 or 1. The contents of declarations that are already 0 or 1 remain unchanged. Two determination methods are different if they differ in the value written to some declaration with content X. If there are 0 declarations with content X, there is exactly 1 determination method.

Good Determination Method

A determination method is called a good determination method if, after determining all declaration contents using that method, there exists at least one team division (a way to assign each person to one of the two teams) that satisfies all declarations simultaneously.

Here, a declaration (u, v, c) with determined content (c \in \{0, 1\}) is satisfied when:

• If c = 0: person u and person v belong to the same team
• If c = 1: person u and person v belong to different teams

Supplement (graph-theoretic rephrasing): Consider a multigraph where each person is a vertex and each declaration is an edge (no self-loops since u \neq v). After determination, each edge has a weight of 0 or 1. The necessary and sufficient condition for the existence of a team division that satisfies all declarations simultaneously is that the XOR of edge weights along every cycle in this graph is 0.

Constraints

• 2 \leq N \leq 3000
• 1 \leq Q \leq 3000
• In A u v c, 1 \leq u, v \leq N and u \neq v
• In A u v c, c is one of 0, 1, X
• In R k, letting M be the total number of declarations at the time of that operation, 1 \leq k \leq M - 1 (it is guaranteed that both declaration k and declaration k+1 exist)
• The total number of declarations across all operations (number of A operations) is at most Q
• R operations do not add or remove declarations
• N, Q, u, v, k are integers

Sample Input 1

3 5
A 1 2 0
A 2 3 X
A 1 3 1
R 2
R 1

Sample Output 1

1
2
1
2
1

Sample Input 2

3 6
A 1 2 0
A 2 3 0
A 1 3 1
A 1 3 X
R 3
R 1

Sample Output 2

1
1
0
0
0
0

Sample Input 3

7 15
A 1 2 X
A 2 3 0
A 3 4 1
A 4 5 X
A 5 1 0
R 1
A 2 5 1
R 5
A 6 7 X
A 1 7 1
R 7
A 3 6 0
R 8
R 3
A 2 4 X

Sample Output 3

2
2
2
4
2
4
2
2
4
4
8
4
8
4
4

Sample Input 4

12 30
A 1 2 0
A 2 3 X
A 3 4 1
A 4 5 0
A 5 6 X
A 6 1 1
R 2
A 7 8 0
A 8 9 X
A 9 10 1
A 10 11 0
A 11 12 X
A 12 7 1
R 8
R 11
A 1 7 X
A 3 9 0
R 12
A 5 11 1
R 14
A 2 8 X
A 4 10 0
R 16
A 6 12 1
R 17
R 1
R 3
A 1 12 X
R 18
A 2 11 0

Sample Output 4

1
2
2
2
4
2
4
4
8
8
8
16
8
16
32
64
32
32
16
16
16
0
16
8
16
8
16
16
16
8

Sample Input 5

2 1
A 1 2 X

Sample Output 5

2