Problem Statement

We have a multiset of integers S, which is initially empty.

Given Q queries, process them in order. Each query is of one of the following types.

• 1 x: Insert an x into S.

• 2 x c: Remove an x from S m times, where m = \mathrm{min}(c,( the number of x's contained in S)).

• 3 : Print ( maximum value of S)-( minimum value of S). It is guaranteed that S is not empty when this query is given.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 0 \leq x \leq 10^9
• 1 \leq c \leq Q
• When a query of type 3 is given, S is not empty.
• All values in input are integers.

Sample Input 1

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

Sample Output 1

1
5
4

The multiset S transitions as follows.

• 1-st query: insert 3 into S. S is now \lbrace 3 \rbrace.
• 2-nd query: insert 2 into S. S is now \lbrace 2, 3 \rbrace.
• 3-rd query: the maximum value of S = \lbrace 2, 3\rbrace is 3 and its minimum value is 2, so print 3-2=1.
• 4-th query: insert 2 into S. S is now \lbrace 2,2,3 \rbrace.
• 5-th query: insert 7 into S. S is now \lbrace 2, 2,3, 7\rbrace.
• 6-th query: the maximum value of S = \lbrace 2,2,3, 7\rbrace is 7 and its minimum value is 2, so print 7-2=5.
• 7-th query: since there are two 2's in S and \mathrm{min(2,3)} = 2, remove 2 from S twice. S is now \lbrace 3, 7\rbrace.
• 8-th query: the maximum value of S = \lbrace 3, 7\rbrace is 7 and its minimum value is 3, so print 7-3=4.

Sample Input 2

4
1 10000
1 1000
2 100 3
1 10

Sample Output 2

If the given queries do not contain that of type 3, nothing should be printed.

Problem Statement

You are given a simple undirected graph with N vertices and M edges, where the vertices are labeled 1 to N. The i-th edge connects vertices u_i and v_i.
What is the minimum number of edges that need to be deleted from this graph so that the graph becomes a forest?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min \left( \frac{N(N-1)}{2}, 2 \times 10^5\right)
• 1 \leq u_i < v_i \leq N
• The given graph is simple.
• All input values are integers.

Sample Input 1

4 4
1 2
1 3
2 4
3 4

Sample Output 1

1

For example, if you delete the first edge, the graph becomes a forest.

Sample Input 2

5 0

Sample Output 2

0

Sample Input 3

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

Sample Output 3

2

Problem Statement

You are given a string S of length N consisting of 0 and 1. It is guaranteed that S contains at least one 1.

You may perform the following operation any number of times (possibly zero):

• Choose an integer i (1 \leq i \leq N-1) and swap the i-th and (i+1)-th characters of S.

Find the minimum number of operations needed so that all 1s are contiguous.

Here, all 1s are said to be contiguous if and only if there exist integers l and r (1 \leq l \leq r \leq N) such that the i-th character of S is 1 if and only if l \leq i \leq r, and 0 otherwise.

Constraints

• 2 \leq N \leq 5 \times 10^5
• N is an integer.
• S is a length N string of 0 and 1.
• S contains at least one 1.

Sample Input 1

7
0101001

Sample Output 1

3

For example, the following three operations make all 1s contiguous:

• Choose i=2 and swap the 2nd and 3rd characters. Then, S= 0011001.
• Choose i=6 and swap the 6th and 7th characters. Then, S= 0011010.
• Choose i=5 and swap the 5th and 6th characters. Then, S= 0011100.

It is impossible to do this in two or fewer swaps, so the answer is 3.

Sample Input 2

3
100

Sample Output 2

0

All 1s are already contiguous, so no swaps are needed.

Sample Input 3

10
0101001001

Sample Output 3

7

Problem Statement

You are given two strings: S, which consists of uppercase English letters and has length N, and T, which also consists of uppercase English letters and has length M\ (\leq N).

There is a string X of length N consisting only of the character #. Determine whether it is possible to make X match S by performing the following operation any number of times:

• Choose M consecutive characters in X and replace them with T.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq M \leq \min(N, 5)
• S is a string consisting of uppercase English letters with length N.
• T is a string consisting of uppercase English letters with length M.

Sample Input 1

7 3
ABCBABC
ABC

Sample Output 1

Yes

Below, let X[l:r] denote the part from the l-th through the r-th character of X.

You can make X match S by operating as follows.

1. Replace X[3:5] with T. X becomes ##ABC##.
2. Replace X[1:3] with T. X becomes ABCBC##.
3. Replace X[5:7] with T. X becomes ABCBABC.

Sample Input 2

7 3
ABBCABC
ABC

Sample Output 2

No

No matter how you operate, it is impossible to make X match S.

Sample Input 3

12 2
XYXXYXXYYYXY
XY

Sample Output 3

Yes

Problem Statement

You are given a simple undirected graph consisting of N vertices and M edges. For i = 1, 2, \ldots, M, the i-th edge connects vertices u_i and v_i. Also, for i = 1, 2, \ldots, N, vertex i is assigned a positive integer W_i, and there are A_i pieces placed on it.

As long as there are pieces on the graph, repeat the following operation:

• First, choose and remove one piece from the graph, and let x be the vertex on which the piece was placed.
• Choose a (possibly empty) set S of vertices adjacent to x such that \sum_{y \in S} W_y \lt W_x, and place one piece on each vertex in S.

Print the maximum number of times the operation can be performed.

It can be proved that, regardless of how the operation is performed, there will be no pieces on the graph after a finite number of iterations.

Constraints

• All input values are integers.
• 2 \leq N \leq 5000
• 1 \leq M \leq \min \lbrace N(N-1)/2, 5000 \rbrace
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace
• 1 \leq W_i \leq 5000
• 0 \leq A_i \leq 10^9

Sample Input 1

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

Sample Output 1

5

In the following explanation, let A = (A_1, A_2, \ldots, A_N) represent the numbers of pieces on the vertices. Initially, A = (1, 0, 0, 0, 0, 1).

Consider performing the operation as follows:

• Remove one piece from vertex 1 and place one piece each on vertices 2 and 3. Now, A = (0, 1, 1, 0, 0, 1).
• Remove one piece from vertex 2. Now, A = (0, 0, 1, 0, 0, 1).
• Remove one piece from vertex 6. Now, A = (0, 0, 1, 0, 0, 0).
• Remove one piece from vertex 3 and place one piece on vertex 2. Now, A = (0, 1, 0, 0, 0, 0).
• Remove one piece from vertex 2. Now, A = (0, 0, 0, 0, 0, 0).

In this procedure, the operation is performed five times, which is the maximum possible number of times.

Sample Input 2

2 1
1 2
1 2
0 0

Sample Output 2

0

In this sample input, there are no pieces on the graph from the beginning.

Sample Input 3

10 20
4 8
1 10
1 7
5 9
9 10
8 10
7 5
1 4
7 3
8 7
2 8
5 8
4 2
5 1
7 2
8 3
3 4
8 9
7 10
2 3
25 5 1 1 16 5 98 3 21 1
35 39 32 11 35 37 14 29 36 1

Sample Output 3

1380