Problem Statement

Takahashi is the manager of a farm. The farm has N plots of land, each numbered from 1 to N.

Each plot i (1 \leq i \leq N) has a designated "harvest value" S_i for the crop grown in that plot. The harvest value does not change through operations. Additionally, each plot i is given an initial soil "moisture level" C_i. The moisture level changes through operations.

At any given point in time, a plot whose moisture level is 0 or less is said to be in a "dry state".

Takahashi performs Q operations in order, depending on the weather and equipment conditions of the farm. Each operation is one of the following three types:

• Operation 1: 1 l r v — For each non-closed plot numbered from l to r, add v to its moisture level. v can be negative. This represents changes in moisture due to rainfall or drought. Closed plots are not affected by this operation.
• Operation 2: 2 x — Close plot x. A closed plot is treated as non-existent in all subsequent operations and queries. Specifically, it will not be subject to moisture addition in Operation 1, nor will it be included in the aggregation of Operation 3. Once a plot is closed, it is never reopened. It is guaranteed that Operation 2 is never performed more than once on the same plot.
• Operation 3: 3 l r — Among the plots numbered from l to r that are not closed and are currently in a dry state (moisture level 0 or less), compute and output the sum of their harvest values. If no such plots exist, output 0.

For all Operation 3 queries, output the answers in the order they appear.

Constraints

• 1 \leq N \leq 3000
• 1 \leq Q \leq 3000
• 1 \leq S_i \leq 10^4 (1 \leq i \leq N)
• -10^4 \leq C_i \leq 10^4 (1 \leq i \leq N)
• For Operation 1: 1 \leq l \leq r \leq N, -10^4 \leq v \leq 10^4
• For Operation 2: 1 \leq x \leq N
• For Operation 3: 1 \leq l \leq r \leq N
• The plot x specified in Operation 2 has not yet been closed at that point. Operation 2 is never performed more than once on the same plot.
• All input values are integers.
• Operation 3 is given at least once.

Sample Input 1

5 5
10 20 30 40 50
3 -1 0 5 -2
3 1 5
1 2 4 -5
3 1 5
2 3
3 1 5

Sample Output 1

100
140
110

Sample Input 2

8 8
5 15 25 35 10 20 30 40
1 -3 2 0 -1 4 -5 3
3 1 8
2 5
1 1 4 -2
3 1 6
1 6 8 -10
3 5 8
2 7
3 1 8

Sample Output 2

90
80
90
140

Sample Input 3

10 10
100 200 300 400 500 600 700 800 900 1000
5 -10 0 3 -7 8 1 -2 6 -4
3 1 10
1 1 5 -5
3 1 5
2 3
2 8
3 1 10
1 4 7 10
3 3 9
1 1 2 1
3 1 10

Sample Output 3

2800
1500
2200
500
1700

Problem Statement

Takahashi is conducting a robot motion experiment in a straight corridor of length L. This corridor corresponds to the interval [0, L] on a number line, and there are walls at both ends (coordinate 0 and coordinate L).

There are N robots in the corridor, and the i-th robot (1 \leq i \leq N) is placed at coordinate X_i at time 0. Each robot has a velocity V_i set at time 0. A robot with V_i > 0 moves at constant speed |V_i| in the direction of increasing coordinates (positive direction), a robot with V_i < 0 moves at constant speed |V_i| in the direction of decreasing coordinates (negative direction), and a robot with V_i = 0 does not move and stays in place. Here, the unit of velocity is the unit of coordinate divided by the unit of time.

When a robot reaches the end of the corridor (coordinate 0 or coordinate L), the sign of its velocity is immediately reversed, and it continues moving in the opposite direction at the same speed. This reflection is repeated any number of times, and the robot always remains within the interval [0, L].

This reflection rule also applies at time 0. Specifically, the behavior of robots whose initial position is on a wall is as follows:

• A robot at coordinate 0: If V_i < 0, its velocity is immediately reversed at time 0, and it begins moving in the positive direction at speed |V_i|. If V_i \geq 0, it does not reverse and moves with velocity V_i (if V_i = 0, it stays in place).
• A robot at coordinate L: If V_i > 0, its velocity is immediately reversed at time 0, and it begins moving in the negative direction at speed |V_i|. If V_i \leq 0, it does not reverse and moves with velocity V_i (if V_i = 0, it stays in place).

Each robot moves independently. Even if two or more robots reach the same coordinate, they pass through each other and do not affect each other's motion.

Find the coordinate of each of the N robots at time T.

It is guaranteed that in the given input, the coordinate of each robot at time T is always an integer.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L \leq 10^9
• 0 \leq T \leq 10^9
• 0 \leq X_i \leq L (1 \leq i \leq N)
• -10^9 \leq V_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers
• The coordinate of each robot at time T is always an integer

Sample Input 1

3 10 3
2 1
8 3
5 -2

Sample Output 1

5
3
1

Sample Input 2

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

Sample Output 2

3
2
3
1

Sample Input 3

5 100 7
10 15
50 -30
0 20
99 -1
100 -10

Sample Output 3

85
40
60
92
30

Sample Input 4

6 1000000000 1000000000
500000000 0
0 1
1 -1
0 2
500000000 3
999999999 1

Sample Output 4

500000000
1000000000
999999999
0
500000000
1

Sample Input 5

1 1 0
0 0

Sample Output 5

0

Problem Statement

Takahashi is the student council president of a certain school. During the preparation period for the cultural festival, he needs to convey an important announcement to the students.

There are N students in this school, and each student is assigned a number from 1 to N.

M pairs of friendship relations between students are given. Friendships are bidirectional, and there are no self-loops or multiple edges.

Takahashi initially chose K students and directly informed them. Let the numbers of the K students who were initially informed be S_1, S_2, \ldots, S_K.

Information spreads successively through friendship relations. That is, friends of students who know the information also learn it, and it further spreads to their friends, and so on. More precisely, all students who can be reached from any of the students S_1, S_2, \ldots, S_K by following zero or more friendship edges will eventually learn the information.

Find the number of students who ultimately know the information. Note that the K students who were initially informed are also counted as students who know the information.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq K \leq N
• 1 \leq S_i \leq N (1 \leq i \leq K)
• S_i \neq S_j (i \neq j)
• 1 \leq u_i < v_i \leq N (1 \leq i \leq M)
• (u_i, v_i) \neq (u_j, v_j) (i \neq j)
• All input values are integers

Sample Input 1

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

Sample Output 1

5

Sample Input 2

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

Sample Output 2

7

Sample Input 3

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

Sample Output 3

10

Problem Statement

Takahashi is in charge of hosting a company presentation competition. In this competition, N employees will give presentations, and each employee is assigned a number from 1 to N.

Each employee i (1 \leq i \leq N) has a positive integer A_i representing their "presentation skill".

In the competition, each of the N employees is assigned a unique presentation order from 1st to Nth. Let P_i denote the position in which employee i presents. Then (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N). Presentations are given in order: 1st, 2nd, \ldots, Nth.

The "contribution" of employee i is defined as A_i \times P_i. The "total score" of the competition is defined as the sum of contributions of all employees:

\displaystyle\sum_{i=1}^{N} A_i \times P_i

Takahashi wants to maximize the total score. However, Aoki has imposed M constraints. Each constraint k (1 \leq k \leq M) states that "employee U_k must present before employee V_k (i.e., P_{U_k} < P_{V_k})".

Among all presentation orders that satisfy all constraints, find the one that maximizes the total score, and output that maximum total score.

It is guaranteed that at least one presentation order satisfying all constraints exists.

Constraints

• 1 \leq N \leq 8
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i \leq 100 (1 \leq i \leq N)
• 1 \leq U_k, V_k \leq N (1 \leq k \leq M)
• U_k \neq V_k (1 \leq k \leq M)
• The same pair (U_k, V_k) is not given more than once.
• At least one presentation order satisfying all constraints exists (i.e., the directed graph with employees as vertices and constraints as directed edges is a DAG).
• All input values are integers.

Sample Input 1

3 1
1 2 3
1 2

Sample Output 1

14

Sample Input 2

3 1
3 1 2
1 3

Sample Output 2

13

Sample Input 3

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

Sample Output 3

84

Sample Input 4

8 4
10 20 30 40 50 60 70 80
1 2
3 4
5 6
7 8

Sample Output 4

2040

Sample Input 5

1 0
42

Sample Output 5

42

Problem Statement

Takahashi challenges a dungeon where N monsters are lined up in a row. The strength of the i-th (1 \leq i \leq N) monster is A_i. Both the monsters' strengths and Takahashi's health are represented as integers between 0 and C, inclusive.

Takahashi performs Q operations on this dungeon in order. There are two types of operations:

• 1 p x : Change the strength of the p-th monster to x. This change is reflected in all subsequent operations.
• 2 l r d : Determine the number of monsters that can be defeated when facing monsters from the l-th to the r-th in order, starting with an initial health of d. This operation does not change the monsters' strengths.

The number of monsters defeated in operation 2 l r d is determined by the following procedure:

Let the current health be h, initially h = d.

For i = l, l+1, \dots, r in order, do the following for the i-th monster (with current strength A_i):

• If h \geq A_i, defeat that monster and update h to h - A_i.
• If h < A_i, that monster cannot be defeated, and h remains unchanged.

In either case, proceed to the next monster.

After all monsters have been processed, the total number of defeated monsters is the answer for this operation.

For each operation 2, output the answer.

Constraints

• 1 \leq N \leq 50000
• 1 \leq C \leq 50
• 1 \leq Q \leq 20000
• 0 \leq A_i \leq C (1 \leq i \leq N)
• For operation 1 p x: 1 \leq p \leq N, 0 \leq x \leq C
• For operation 2 l r d: 1 \leq l \leq r \leq N, 0 \leq d \leq C
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
4
1
2

Sample Input 2

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

Sample Output 2

1
1
2
0

Sample Input 3

12 20 14
4 0 15 3 8 6 2 20 1 7 5 10
2 1 12 20
2 3 8 10
1 8 4
2 3 8 10
1 2 9
2 1 5 12
1 10 0
2 9 12 7
2 1 1 3
1 3 0
2 1 4 4
1 12 20
2 6 12 20
2 5 5 8

Sample Output 3

4
2
2
2
3
0
2
6
1

Sample Input 4

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

Sample Output 4

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

Sample Input 5

1 1 7
0
2 1 1 0
2 1 1 1
1 1 1
2 1 1 0
2 1 1 1
1 1 0
2 1 1 0

Sample Output 5

1
1
0
1
1