Problem Statement

There are N houses numbered 1 through N on a two-dimensional plane. House i is at (x_i, y_i).

We use Chebyshev distance to calculate the distance between two houses. That is, the distance between Houses i and j is \max(|x_i - x_j|, |y_i-y_j|).

There are \frac{N(N-1)}{2} pairs formed by two different houses. For each of these pairs, we will calculate the distance between the houses, and then we will sort these distances in descending order to get a sequence of length \frac{N(N-1)}{2}. Find the second value from the beginning of this sequence.

Constraints

• All values in input are integers.
• 3 \leq N \leq 2 \times 10^{5}
• -10^{9} \leq x_i, y_i \leq 10^{9}

Sample Input 1

3
0 0
1 2
4 0

Sample Output 1

3

• The distance between Houses 1 and 2 is 2;
• The distance between Houses 1 and 3 is 4;
• The distance between Houses 2 and 3 is 3.
• By sorting these in descending order, we get (4,3,2), where the second value from the beginning is 3.

Sample Input 2

4
0 0
0 0
1 0
0 1

Sample Output 2

1

• There may be multiple houses at the same coordinates.

Sample Input 3

20
407 361
167 433
756 388
-551 -47
306 -471
36 928
338 -355
911 852
288 70
-961 -769
-668 -386
-690 -378
182 -609
-677 401
-458 -112
184 -131
-243 888
-163 471
-11 997
119 544

Sample Output 3

1766

Problem Statement

Snuke has 2N dogs, numbered 1 through 2N.

The cuteness of Dog i is a_i. The color of Dog i is c_i, which is R, G, or B; R stands for red, G stands for green, and B stands for blue.

Snuke has N kennels, and wants to put two dogs in each kennel. Note that this means each dog will be in exactly one kennel.

When he puts two dogs in the same kennel, it will cause some dissatisfaction in that kennel. The level of dissatisfaction is represented as an integer. When Dogs i and j are in the same kennel, the dissatisfaction will be 0 if c_i = c_j and |a_i - a_j| otherwise.

Find the minimum possible total dissatisfaction when putting two dogs in each of the N kennels.

Constraints

• 1 \leq N \leq 10^{5}
• 1 \leq a_i \leq 10^{15}
• a_i is an integer.
• c_i is R, G, or B.

Sample Input 1

1
1 R
2 G

Sample Output 1

1

• Dog 1 has the cuteness of 1, and Dog 2 has the cuteness of 2.
• Since c_1 \neq c_2, the dissatisfaction will be 1.

Sample Input 2

1
1 B
2 B

Sample Output 2

0

• Dog 1 has the cuteness of 1, and Dog 2 has the cuteness of 2.
• Since c_1 = c_2, the dissatisfaction will be 0.

Sample Input 3

10
585 B
293 B
788 B
222 B
772 G
841 B
115 R
603 G
450 B
325 R
851 B
205 G
134 G
651 R
565 R
548 B
391 G
19 G
808 B
475 B

Sample Output 3

0

Problem Statement

Given is a sequence p which is a permutation of (1,2, \ldots, N). Initially, the n-th term of p is p_{n}.

Your objective is to sort p in ascending order in at most N^2 operations. In one operation, you make the following change on p:

• In the 1-st, 3-rd, and subsequent odd-numbered operations, you choose an odd number n between 1 and N-1 (inclusive) to swap p_n and p_{n+1}.
• In the 2-nd, 4-th, and subsequent even-numbered operations, you choose an even number n between 2 and N-1 (inclusive) to swap p_n and p_{n+1}.

We can prove that the objective is always achievable under the Constraints of this problem. Find one sequence of operations that achieves the objective.

You will be given T test cases and asked to solve each of them.

Constraints

• All values in input are integers.
• 1 \leq T \leq 250
• 2 \leq N \leq 500
• 1 \leq p_i \leq N
• p is a permutation of (1,2,\ldots,N).
• In one input file, the sum of N does not exceed 500.

Sample Input 1

2
5
2 1 3 5 4
2
1 2

Sample Output 1

2
1 4
0

• Here is the description for the 1-st test case.
  • Choosing 1 in the 1-st operation makes p = (1,2,3,5,4).
  • Choosing 4 in the 2-nd operation makes p = (1,2,3,4,5).
  • Note that although (1,4) is a valid sequence of operations, (4, 1) is not.
• Also note that it is allowed to perform no operation, and it is not required to minimize the number of operations.

Problem Statement

Snuke has a blackboard and N candies. The tastiness of the i-th candy is a_i.

He will repeat the operation below until he has no more candy.

• Choose one or two of his candies and eat them (of course, they disappear). Then, write on the blackboard the total tastiness of the candies he has just chosen.

Snuke wants to minimize X-Y, where X and Y are the largest and smallest values written on the blackboard, respectively. Find the minimum possible value of X-Y.

Constraints

• All values in input are integers.
• 1 \leq N \leq 5000
• -10^{9} \leq a_i \leq 10^9

Sample Input 1

3
1 2 4

Sample Output 1

1

• One optimal sequence of operations is to eat the candies with the tastinesses of 1 and 2 in the first operation, and then eat the candies with the tastiness of 4 in the second operation.

Sample Input 2

2
-100 -50

Sample Output 2

0

• It is optimal to eat both candies with the tastiness of -100 and -50 in the first operation.

Sample Input 3

20
-18 31 -16 12 -44 -5 24 17 -37 -31 46 -24 -2 11 32 16 0 -39 35 38

Sample Output 3

13

Problem Statement

Given is a directed tree with N vertices numbered 1 through N.

Vertex 1 is the root of the tree. For each integer i such that 2 \leq i \leq N, there is a directed edge from Vertex p_i to i.

Let a be the permutation of (1, \ldots, N), and a_i be the i-th element of a.

Among the N! sequences that can be a, find the number of sequences that satisfy the following condition, modulo 998244353.

• Condition: For every integer i such that 1 \leq i \leq N, Vertex i is unreachable from Vertex a_i by traversing one or more edges.

Constraints

• All values in input are integers.
• 1 \leq N \leq 2000
• 1 \leq p_i < i

Sample Input 1

4
1 1 3

Sample Output 1

4

Sample Input 2

30
1 1 3 1 5 1 1 1 8 9 7 3 11 11 15 14 4 10 11 12 1 10 13 11 7 23 8 12 18

Sample Output 2

746746186

• Remember to print the count modulo 998244353.

Problem Statement

Given is a tree with N vertices numbered 1 through N.

The i-th edge connects Vertices a_i and b_i.

Snuke will label each vertex with 0 or 1 and each edge with AND or OR. Among the 2^{2N-1} ways to label the vertices and edges, find the number of ways that satisfy the following condition, modulo 998244353.

Condition: There exists a sequence of N-1 operations ending up with one vertex labeled 1, where each operation consists of the steps below.

• Choose one edge and contract it. Here, let x and y be the labels of the erased vertices and \mathrm{op} be the label of the erased edge.
• If \mathrm{op} is AND, label the new vertex with \mathrm{AND}(x,y); if \mathrm{op} is OR, label the new vertex with \mathrm{OR}(x,y).

Notes

• The operation \mathrm{AND} is defined as follows: \mathrm{AND}(0,0)=(0,1)=(1,0)=0,\mathrm{AND}(1,1)=1.
• The operation \mathrm{OR} is defined as follows: \mathrm{OR}(1,1)=(0,1)=(1,0)=1,\mathrm{OR}(0,0)=0.
• When contracting the edge connecting Vertex s and Vertex t, we merge the two vertices while removing that edge. After the contraction, there is an edge connecting the new vertex and vertex u if and only if there was an edge connecting s and u or connecting t and u before the contraction.

Constraints

• All values in input are integers.
• 2 \leq N \leq 10^{5}
• 1 \leq a_i, b_i \leq N
• The given graph is a tree.

Sample Input 1

2
1 2

Sample Output 1

4

Sample Input 2

20
7 3
20 18
16 12
7 2
10 5
18 16
16 3
4 11
7 15
8 1
6 1
12 13
15 5
19 17
7 1
9 8
7 17
16 14
11 7

Sample Output 2

283374562

• Remember to print the count modulo 998244353.