Problem Statement

You are given an undirected graph with N vertices and M edges, where the vertices are numbered 1 through N and the edges are numbered 1 through M. Edge i connects vertices u_i and v_i.
To make the graph simple by removing edges, what is the minimum number of edges that must be removed?
Here, a graph is called simple if and only if it does not contain self-loops or multi-edges.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 5 \times 10^5
• 1 \leq u_i \leq N
• 1 \leq v_i \leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

2

By removing edges 3 and 5, the graph becomes simple. This is one of the ways to remove the minimum number of edges, so the answer is 2.

Sample Input 2

1 0

Sample Output 2

0

Sample Input 3

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

Sample Output 3

3

Problem Statement

You are given six integers: h_1, h_2, h_3, w_1, w_2, and w_3.
Consider writing a positive integer on each square of a 3 \times 3 grid so that all of the following conditions are satisfied:

• For i=1,2,3, the sum of numbers written in the i-th row from the top is h_i.
• For j=1,2,3, the sum of numbers written in the j-th column from the left is w_i.

For example, if (h_1, h_2, h_3) = (5, 13, 10) and (w_1, w_2, w_3) = (6, 13, 9), then all of the following three ways satisfy the conditions. (There are other ways to satisfy the conditions.)

How many ways are there to write numbers to satisfy the conditions?

Constraints

• 3 \leq h_1, h_2, h_3, w_1, w_2, w_3 \leq 30
• All values in input are integers.

Sample Input 1

3 4 6 3 3 7

Sample Output 1

1

The following is the only way to satisfy the conditions. Thus, 1 should be printed.

Sample Input 2

3 4 5 6 7 8

Sample Output 2

0

There may not be a way to satisfy the conditions.

Sample Input 3

5 13 10 6 13 9

Sample Output 3

120

Sample Input 4

20 25 30 22 29 24

Sample Output 4

30613

Problem Statement

There is one server and N PCs. The server and each PC each hold one string, and initially all strings are empty.

Q queries are given. Each query is in one of the following formats:

• 1 p: Replace the string of PC p with the string of the server.
• 2 p s: Append string s to the end of the string of PC p.
• 3 p: Replace the string of the server with the string of PC p.

Find the final string of the server after processing all queries in the given order.

Constraints

• N,Q are integers
• 1\leq N,Q \leq 2\times 10^5
• For every query, p is an integer and 1 \leq p\leq N.
• For every query of type 2, s is a string of length at least 1 consisting of lowercase English letters.
• The sum of the lengths of s over all queries of type 2 is at most 10^6.

Sample Input 1

2 6
2 1 at
3 1
2 2 on
1 2
2 2 coder
3 2

Sample Output 1

atcoder

• Initially, the strings of the server and PCs 1,2 are all empty.
• 1st query: Append at to the end of the string of PC 1. At this time, the strings of the server, PC 1,2 are empty, at, empty, respectively.
• 2nd query: Replace the string of the server with the string of PC 1. At this time, the strings of the server, PC 1,2 are at, at, empty, respectively.
• 3rd query: Append on to the end of the string of PC 2. At this time, the strings of the server, PC 1,2 are at, at, on, respectively.
• 4th query: Replace the string of PC 2 with the string of the server. At this time, the strings of the server, PC 1,2 are at, at, at, respectively.
• 5th query: Append coder to the end of the string of PC 2. At this time, the strings of the server, PC 1,2 are at, at, atcoder, respectively.
• 6th query: Replace the string of the server with the string of PC 2. At this time, the strings of the server, PC 1,2 are atcoder, at, atcoder, respectively.

Thus, the final string of the server is atcoder.

Sample Input 2

100000 3
1 100
2 300 abc
3 200

Sample Output 2

The final string of the server is empty.

Sample Input 3

10 10
2 7 ladxf
2 7 zz
2 7 kfm
3 7
1 5
2 5 irur
3 5
1 6
2 6 ptilun
3 6

Sample Output 3

ladxfzzkfmirurptilun

Problem Statement

You are given a tree with N vertices. The vertices are numbered 1,2,\dots,N, and the edges are numbered 1,2,\dots,N-1. Edge j bidirectionally connects vertices u_j and v_j and has weight w_j. Also, vertex i is given an integer x_i. If x_i > 0, then x_i positrons are placed at vertex i. If x_i < 0, then -x_i electrons are placed at vertex i. If x_i=0, then nothing is placed at vertex i. Here, it is guaranteed that \sum_{i=1}^N x_i = 0.

Moving one positron or electron along edge j costs energy w_j. Also, when a positron and an electron are at the same vertex, they annihilate each other in equal numbers.

Find the minimum energy required to annihilate all positrons and electrons.

Constraints

• 2 \leq N \leq 10^5
• |x_i| \leq 10^4
• \sum_{i=1}^N x_i = 0
• 1 \leq u_j < v_j \leq N
• 0 \leq w_j \leq 10^4
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

9

Initially, x=(x_1,x_2,x_3,x_4)=(-3,+2,+2,-1). By operating as follows, all positrons and electrons can be annihilated with energy 9:

• Move one electron at vertex 1 to vertex 2. This costs energy 2, and x=(-2,+1,+2,-1).
• Move one positron at vertex 2 to vertex 1. This costs energy 2, and x=(-1,0,+2,-1).
• Move one electron at vertex 4 to vertex 1. This costs energy 3, and x=(-2,0,+2,0).
• Move one electron at vertex 1 to vertex 3. This costs energy 1, and x=(-1,0,+1,0).
• Move one electron at vertex 1 to vertex 3. This costs energy 1, and x=(0,0,0,0).

It is impossible to annihilate all positrons and electrons with energy 8 or less, so the answer is 9.

Sample Input 2

2
0 0
1 2 1

Sample Output 2

0

The condition may already be satisfied from the beginning.

Sample Input 3

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

Sample Output 3

28

Problem Statement

You are given a positive integer N and sequences of N positive integers each: A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).

We have an N \times N grid. The square at the i-th row from the top and the j-th column from the left is called the square (i,j). For each pair of integers (i,j) such that 1 \le i,j \le N, the square (i,j) has the integer A_i + B_j written on it. Process Q queries of the following form.

• You are given a quadruple of integers h_1,h_2,w_1,w_2 such that 1 \le h_1 \le h_2 \le N,1 \le w_1 \le w_2 \le N. Find the greatest common divisor of the integers contained in the rectangle region whose top-left and bottom-right corners are (h_1,w_1) and (h_2,w_2), respectively.

Constraints

• 1 \le N,Q \le 2 \times 10^5
• 1 \le A_i,B_i \le 10^9
• 1 \le h_1 \le h_2 \le N
• 1 \le w_1 \le w_2 \le N
• All values in input are integers.

Sample Input 1

3 5
3 5 2
8 1 3
1 2 2 3
1 3 1 3
1 1 1 1
2 2 2 2
3 3 1 1

Sample Output 1

2
1
11
6
10

Let C_{i,j} denote the integer on the square (i,j).

For the 1-st query, we have C_{1,2}=4,C_{1,3}=6,C_{2,2}=6,C_{2,3}=8, so the answer is their greatest common divisor, which is 2.

Sample Input 2

1 1
9
100
1 1 1 1

Sample Output 2

109