Problem Statement

You are given an integer N. For length-N^2 integer sequences a and b consisting of integers between 1 and N (inclusive), we define their distance d(a,b) as follows:

• d(a,b)= "the number of indices i (1 \leq i \leq N^2) such that a_i \neq b_i."

Now, you will create N length-N^2 integer sequences consisting of integers between 1 and N, and denote them as x_1,x_2,\cdots,x_N (their order also matters). Find the number, modulo 998244353, of instances of (x_1,x_2,\cdots,x_N) satisfying the following condition.

• For any length-N^2 integer sequence y consisting of integers between 1 and N, there exists some 1 \leq i \leq N such that d(x_i,y) \geq N^2-N.

Constraints

• 1 \leq N \leq 50
• All input values are integers.

Sample Input 1

2

Sample Output 1

80

For example, (x_1,x_2)=((1,1,2,2),(1,2,1,2)) does not satisfy the condition, because if y=(1,1,1,2), then d(x_1,y)=1,d(x_2,y)=1.

On the other hand, (x_1,x_2)=((1,1,1,1),(2,2,2,2)) satisfies the condition.

There are 80 instances of (x_1,x_2) that satisfy the condition.

Sample Input 2

3

Sample Output 2

597965565

Sample Input 3

10

Sample Output 3

241191911

Problem Statement

You are given an integer sequence X=(X_1,X_2,\cdots,X_N) of length N consisting of 0 and 1.

You can perform the following operation zero or more times:

• Classify each element of X into group A or group B. Then, for each group, reverse the order of the elements it contains. More formally, if the elements contained in a group are X_{i_1},X_{i_2},\cdots,X_{i_s} (i_1<i_2<\cdots<i_s), then for all 1 \leq j \leq s, simultaneously replace the value of X_{i_j} with X_{i_{s+1-j}}.

Your goal is to make X non-decreasing. Find the minimum number of operations needed to achieve the goal and the way to perform the operations. It can be proved that a solution always exists under the constraints of this problem.

Solve T cases for one input.

Constraints

• 1 \leq T \leq 250000
• 1 \leq N \leq 250000
• 0 \leq X_i \leq 1
• The sum of N over the T cases is at most 250000.
• All input values are integers.

Sample Input 1

2
4
0 1 0 1
5
0 0 1 1 1

Sample Output 1

2
AABA
BBBB
0

For the first test case, the goal can be achieved in two operations as follows, which is the minimum number of operations:

• First operation: Use s_1=AABA. Since (X_1,X_2,X_4) are in group A, reverse their order, resulting in (X_1,X_2,X_4)=(1,1,0). Similarly, since (X_3) is in group B, reverse their order, resulting in (X_3)=(0). Thus, overall we get X=(1,1,0,0).

• Second operation: Use s_2=BBBB. Since () are in group A, reverse their order, resulting in ()=(). Similarly, since (X_1,X_2,X_3,X_4) are in group B, reverse their order, resulting in (X_1,X_2,X_3,X_4)=(0,0,1,1). Thus, overall we get X=(0,0,1,1).

For the second test case, the goal can be achieved by performing the operation zero times.

Problem Statement

There are N slimes numbered from 1 to N. The color of each slime is represented by an integer between 0 and 2K (inclusive), and the color of slime i is C_i.

Currently, M pairs of slimes are in a (bidirectional) friendship. Specifically, slimes A_i and B_i are friends (1 \leq i \leq M). Here, it is guaranteed that for any two slimes, one can reach the other by following friendship relations.

You can perform the following operation:

• First, choose a pair of slimes (u,v) that satisfies both of the following conditions:
  • Slimes u and v are in a friendship.
  • (C_u - C_v) \bmod (2K+1) \geq K+1 (here, the result of x \bmod y is always in the range [0,y-1]).
• Then, let slime u eat slime v. Slime v disappears from the field. Also, all slimes except u that were in a friendship with slime v become friends with slime u (if they were already friends with slime u, nothing happens).

Determine whether it is possible to leave only slime 1 on the field by repeating the operation appropriately.

Solve T cases for one input.

Constraints

• 1 \leq T \leq 125000
• 2 \leq N \leq 250000
• N-1 \leq M \leq 250000
• 1 \leq K \leq N
• 0 \leq C_i \leq 2K
• 1 \leq A_i < B_i \leq N
• (A_i,B_i) \neq (A_j,B_j) (i \neq j)
• For any two slimes, one can reach the other by following friendship relations.
• The sum of N over the T cases is at most 250000.
• The sum of M over the T cases is at most 250000.
• All input values are integers.

Sample Input 1

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

Sample Output 1

No
Yes
No
No

In the first test case, no operation can be performed.

In the second test case, it is possible to leave only slime 1 on the field by the following procedure:

• Choose (u,v)=(3,2) and let slime 3 eat slime 2. Slime 2 disappears, and slimes 1 and 3 become friends.
• Choose (u,v)=(1,3) and let slime 1 eat slime 3. Slime 3 disappears.

Problem Statement

Let L=10^8.

You are given an integer N and a non-negative integer sequence A=(A_1,A_2,\cdots,A_M) of length M (0 \leq A_i < L). For each k=1,2,\cdots,N, solve the following problem:

There are k red balls numbered from 1 to k and k blue balls numbered from 1 to k. Now, you will write a real number on each ball in the following way. Here, all random choices are independent.

• For each 1 \leq i \leq k, the number written on red ball i is L \times (i-1)+A_{j_i}. Here, j_i is an integer chosen uniformly at random from the range between 1 and M (inclusive).

• For each 1 \leq i \leq k, the number written on blue ball i is a real number chosen uniformly at random from the range [0,k \times L).

Find the probability, modulo 998244353, that the following condition is satisfied after writing numbers on all balls.

• For any real number x (0 \leq x \leq k \times L), "the number of red balls with a number written that is at most x" \geq "the number of blue balls with a number written that is at most x".

Constraints

• 1 \leq N \leq 250000
• 1 \leq M \leq 250000
• 0 \leq A_i < L=10^8
• All input values are integers.

Sample Input 1

2 1
50000000

Sample Output 1

499122177
686292993

• k=1: The probability of satisfying the condition is 1/2.
• k=2: The probability of satisfying the condition is 5/16.

Sample Input 2

3 5
78682095 25048034 71067122 94666780 1927105

Sample Output 2

741897823
406774904
435399949

Sample Input 3

10 7
40490214 25131781 2271243 52064315 34467030 27419560 56103210

Sample Output 3

457696464
497746652
679391958
742383895
245278311
709723420
729551291
1911348
414224424
650563524

Problem Statement

You are given N pairs of integers (A_1,B_1),(A_2,B_2),\cdots,(A_N,B_N).

For a subset s of \{1,2,\cdots,N\}, we define its score as follows:

• (\sum_{i \in s} A_i)^2 + (\sum_{i \in s} B_i)^2 - 3 \sum_{i \in s} (A_i^2+B_i^2)

Find the maximum possible value of the score.

Solve T cases for one input.

Constraints

• 1 \leq T \leq 250000
• 1 \leq N \leq 250000
• \sum_{1 \leq i \leq N} |A_i| \leq 10^9
• \sum_{1 \leq i \leq N} |B_i| \leq 10^9
• The sum of N over the T cases is at most 250000.
• All input values are integers.

Sample Input 1

4
4
1 0
0 1
-1 0
0 -1
4
1 0
1 0
1 0
1 0
6
1 -9
-7 -2
0 -10
10 1
2 -8
1 -8
10
19271058 -140039457
-3441379 -134156148
227767903 -70474702
-837477 -74699717
153584327 80404336
115741008 -22141349
-190028077 -21940357
76149725 17176032
159846847 -296045185
-53332199 142922717

Sample Output 1

0
4
296
178262497119089558

In the first case, if s=\{\}, the score is 0, which is the maximum.

In the second case, if s=\{1,2,3,4\}, the score is 4, which is the maximum.