Problem Statement

Takahashi is a martial artist. There are N moves that a martial artist can learn, called Move 1, 2, \ldots, N. For each 1 \leq i \leq N, it takes T_i minutes of practice to learn Move i. Additionally, at the beginning of that practice, all of the Moves A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} must be already learned. Here, it is guaranteed that A_{i,j} < i for each 1 \leq j \leq K_i.

Takahashi has not learned any move at time 0. He cannot practice for more than one move simultaneously, nor can he stop a practice he has already started. Find the minimum number of minutes needed for Takahashi to learn Move N.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq T_i \leq 10^9
• 0 \leq K_i < i
• 1 \leq A_{i,j} < i
• \sum_{i=1}^N K_i \leq 2\times 10^5
• A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} are all distinct.
• All values in input are integers.

Sample Input 1

3
3 0
5 1 1
7 1 1

Sample Output 1

10

Here is one possible plan for Takahashi.

• At time 0, start practicing for Move 1 to learn Move 1 at time 3.
• Then, at time 3, start practicing for Move 3 to learn Move 3 at time 10.

Here, Takahashi spends 3+7=10 minutes to learn Move 3, which is the fastest possible. Note that he does not need to learn Move 2 to learn Move 3.

Sample Input 2

5
1000000000 0
1000000000 0
1000000000 0
1000000000 0
1000000000 4 1 2 3 4

Sample Output 2

5000000000

Note that the answer may not fit into a 32-bit integer.

Problem Statement

Person 0, Person 1, \ldots, and Person (N-1) are sitting around a turntable in their counterclockwise order, evenly spaced. Dish p_i is in front of Person i on the table.
You may perform the following operation 0 or more times:

• Rotate the turntable by one N-th of a counterclockwise turn. As a result, the dish that was in front of Person i right before the rotation is now in front of Person (i+1) \bmod N.

When you are finished, Person i is happy if Dish i is in front of Person (i-1) \bmod N, Person i, or Person (i+1) \bmod N.
Find the maximum possible number of happy people.

Constraints

• 3 \leq N \leq 2 \times 10^5
• 0 \leq p_i \leq N-1
• p_i \neq p_j if i \neq j.
• All values in input are integers.

Sample Input 1

4
1 2 0 3

Sample Output 1

4

The figure below shows the table after one operation.

Here, there are four happy people:

• Person 0 is happy because Dish 0 is in front of Person 3\ (=(0-1) \bmod 4);
• Person 1 is happy because Dish 1 is in front of Person 1\ (=1);
• Person 2 is happy because Dish 2 is in front of Person 2\ (=2);
• Person 3 is happy because Dish 3 is in front of Person 0\ (=(3+1) \bmod 4).

There cannot be five or more happy people, so the answer is 4.

Sample Input 2

3
0 1 2

Sample Output 2

3

Sample Input 3

10
3 9 6 1 7 2 8 0 5 4

Sample Output 3

5

Problem Statement

You are given N circles on the xy-coordinate plane. For each i = 1, 2, \ldots, N, the i-th circle is centered at (x_i, y_i) and has a radius of r_i.

Determine whether it is possible to get from (s_x, s_y) to (t_x, t_y) by only passing through points that lie on the circumference of at least one of the N circles.

Constraints

• 1 \leq N \leq 3000
• -10^9 \leq x_i, y_i \leq 10^9
• 1 \leq r_i \leq 10^9
• (s_x, s_y) lies on the circumference of at least one of the N circles.
• (t_x, t_y) lies on the circumference of at least one of the N circles.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes

Here is one way to get from (0, -2) to (3, 3).

• From (0, -2), pass through the circumference of the 1-st circle counterclockwise to reach (1, -\sqrt{3}).
• From (1, -\sqrt{3}), pass through the circumference of the 2-nd circle clockwise to reach (2, 2).
• From (2, 2), pass through the circumference of the 3-rd circle counterclockwise to reach (3, 3).

Thus, Yes should be printed.

Sample Input 2

3
0 1 0 3
0 0 1
0 0 2
0 0 3

Sample Output 2

No

It is impossible to get from (0, 1) to (0, 3) by only passing through points on the circumference of at least one of the circles, so No should be printed.

Problem Statement

You are given N points (x_1, y_1), (x_2, y_2), \dots, (x_N, y_N) on a two-dimensional plane, and a non-negative integer D.

Find the number of integer pairs (x, y) such that \displaystyle \sum_{i=1}^N (|x-x_i|+|y-y_i|) \leq D.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq D \leq 10^6
• -10^6 \leq x_i, y_i \leq 10^6
• (x_i, y_i) \neq (x_j, y_j) for i \neq j.
• All input values are integers.

Sample Input 1

2 3
0 0
1 0

Sample Output 1

8

The following figure visualizes the input and the answer for Sample 1. The blue points represent the input. The blue and red points, eight in total, satisfy the condition in the statement.

Sample Input 2

2 0
0 0
2 0

Sample Output 2

0

Sample Input 3

6 100
9 -6
10 -1
2 10
-1 7
-7 5
-1 -4

Sample Output 3

419

Problem Statement

Given is a tree with N vertices. The vertices are numbered 1, 2, \ldots, N, and for each 1\leq i\leq N-1, the i-th edge connects Vertex U_i and Vertex V_i. Let D be the diameter of the tree. Find the number, modulo 998244353, of ways to choose two or more of the vertices and paint them red so that all distances between two red vertices are D.

Here, the distance between two vertices is the minimum number of edges that must be traversed to travel from one vertex to the other, and the diameter of the tree is the maximum distance between two vertices.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq U_i,V_i \leq N
• U_i \neq V_i
• All values in input are integers.
• The given graph is a tree.

Sample Input 1

5
1 2
1 3
1 4
4 5

Sample Output 1

2

The given tree has five vertices and a diameter of 3.
There are just two pairs of vertices whose distance is 3: (2,5) and (3,5), so there are two ways to paint the tree to satisfy the condition: \lbrace 2,5\rbrace and \lbrace 3,5\rbrace .
Note that painting 2,3,5 does not satisfy the condition since the distance between Vertex 2 and Vertex 3 is 2.

Sample Input 2

4
1 2
1 3
1 4

Sample Output 2

4

The diameter is 2, and the four ways to paint the tree to satisfy the condition are: \lbrace 2,3\rbrace , \lbrace 2,4\rbrace , \lbrace 3,4\rbrace , \lbrace 2,3,4\rbrace .