Problem Statement

You are given a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

You can perform the following operation zero or more times:

• Choose an integer i (1 \leq i \leq N-1) and swap the values of P_i and P_{i+1}. Here, both of the following conditions must be satisfied:
  • P_i>P_{i+1} holds immediately before the operation.
  • The operation does not change the length of the longest increasing subsequence of P.

Find the lexicographically smallest permutation among all permutations that can be obtained as P after operations.

Solve T test cases for each input.

Constraints

• 1 \leq T \leq 250000
• 1 \leq N \leq 250000
• P is a permutation of (1,2,\ldots,N).
• The sum of N over all test cases in each input does not exceed 250000.
• All input values are integers.

Sample Input 1

4
3
2 3 1
3
3 2 1
7
5 7 6 4 2 3 1
15
6 4 5 14 15 1 3 9 12 8 10 2 7 13 11

Sample Output 1

2 1 3
3 2 1
5 2 1 7 6 4 3
4 1 6 5 3 2 9 8 7 14 12 10 15 13 11

Let us explain the first test case. For P=(2,3,1), the operation cannot be performed with i=1, but can be performed with i=2. After the operation, P=(2,1,3), and no further operations can be performed from here. Among the permutations reachable starting from P=(2,3,1), the lexicographically smallest one is (2,1,3).

Problem Statement

Maroon's summer vacation lasts N days from Day 1 through Day N. During the vacation, M movies numbered from 1 through M are scheduled to be screened, and movie i can be watched from Day L_i through Day R_i.

For a subset s of all movies, define f(s) as follows:

• f(s) is the maximum number of movies in s that can be watched throughout the vacation when he can watch at most one movie per day. Here, watching the same movie multiple times counts as one movie.

There are 2^M possible sets for s. Find the sum, modulo 998244353, of f(s) over all of them.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq N \times (N+1) /2
• 1 \leq L_i \leq R_i \leq N
• (L_i,R_i) \neq (L_j,R_j) (i \neq j)
• All input values are integers.

Sample Input 1

2 3
1 1
2 2
1 2

Sample Output 1

11

f(s)=|s| holds for most s. The only exception is s=\{1,2,3\}, where f(s)=2. The sum of f(s) over all s is 11.

Sample Input 2

3 3
1 1
2 2
3 3

Sample Output 2

12

Sample Input 3

4 10
3 3
2 4
2 3
4 4
3 4
1 3
1 1
2 2
1 2
1 4

Sample Output 3

3796

Sample Input 4

7 20
1 3
4 5
3 3
3 5
1 4
4 7
2 3
1 7
6 7
4 6
2 4
6 6
3 6
2 5
7 7
3 4
2 2
5 5
2 6
1 2

Sample Output 4

7113137

Problem Statement

There are balls with integers from 1 to N written on them. Specifically, there are A_i balls with integer i (1 \leq i \leq N) written on them.

Define S=A_1+A_2+\cdots+A_N. Here, it is guaranteed that S is a positive even number. Divide the S balls into S/2 pairs. The integers written on the two balls in a pair must be different. It can be proved that such pairing is possible under the constraints of this problem.

For each pair, perform the following operation:

• Let the integers written on the two balls be x and y (x < y). Replace the numbers written on these balls with x+0.5 and y-0.5, respectively.

After completing the operation for all pairs, let d be the maximum number of balls with the same number written on them. Find the minimum possible value of d.

Solve T test cases for each input.

Constraints

• 1 \leq T \leq 125000
• 2 \leq N \leq 250000
• 0 \leq A_i \leq 10^9
• S=A_1+A_2+\cdots+A_N is a positive even number.
• A_i \leq S/2
• The sum of N over all test cases in each input does not exceed 250000.
• All input values are integers.

Sample Input 1

4
4
1 2 2 1
4
2 2 5 1
7
101 2 203 304 5 106 107
20
239276621 320064891 910500852 164832983 245532750 198319686 715892722 967824729 769431650 80707349 459924867 257261830 777045523 583882654 950300098 438099970 322288793 532405019 256358887 45539860

Sample Output 1

2
6
203
613287276

Consider the first test case. Let (x,y) denote a pair of balls with integers x,y written on them.

For example, if we pair as (1,3),(2,3),(2,4), the numbers written on the balls after the operation are 1.5,2.5,2.5,2.5,2.5,3.5. The maximum number of balls with the same number written on them is d=4.

On the other hand, if we pair as (1,2),(2,3),(3,4), the numbers written on the balls after the operation are 1.5,1.5,2.5,2.5,3.5,3.5. The maximum number of balls with the same number written on them is d=2.

d cannot be made smaller than 2, so the answer is 2.

Problem Statement

You are given an integer N. We call a rooted tree T satisfying the following conditions a BFS-ordered tree.

• T is a rooted tree with N vertices numbered from 1 to N.
• The root is vertex 1.
• Let vertex p_i be the parent of each vertex i (2 \leq i \leq N). Then, p_2 \leq p_3 \leq \cdots \leq p_N holds.

For each d=1,2,\ldots,(N-1), find the number, modulo 998244353, of BFS-ordered trees T satisfying the following condition.

• The distance between vertices (N-1) and N in T is exactly d. More precisely, when considering T as an undirected tree and the path connecting vertices (N-1) and N, the number of edges in that path is exactly d.

Constraints

• 2 \leq N \leq 10^6
• All input values are integers.

Sample Input 1

2

Sample Output 1

1

Sample Input 2

3

Sample Output 2

1
1

Sample Input 3

4

Sample Output 3

2
2
1

Sample Input 4

5

Sample Output 4

5
5
3
1

Sample Input 5

20

Sample Output 5

477638700
477638700
178405156
178405139
109639972
108787985
86366256
69212603
43976909
22930595
9698374
3355343
947052
215710
38814
5324
524
33
1

Problem Statement

You are given integers N, C, and K. Find the number, modulo 998244353, of length-N integer sequences x=(x_1,x_2,\ldots,x_N) satisfying the following conditions.

• 1 \leq x_i \leq N (1 \leq i \leq N).
• Consider an undirected graph with N vertices numbered from 1 to N. This graph has N edges, and the i-th edge connects vertices i and x_i. Then, the number of connected components of the graph is exactly C.
• The number of i satisfying i<x_i is exactly K.

Constraints

• 1 \leq N \leq 250000
• 1 \leq C \leq N
• 0 \leq K \leq N-1
• All input values are integers.

Sample Input 1

3 1 2

Sample Output 1

6

The following six sequences x satisfy the conditions:

• x=(2,3,1)
• x=(2,3,2)
• x=(2,3,3)
• x=(3,3,1)
• x=(3,3,2)
• x=(3,3,3)

Sample Input 2

3 2 2

Sample Output 2

0

Sample Input 3

6 3 0

Sample Output 3

225

Sample Input 4

20 4 7

Sample Output 4

476087626

Sample Input 5

250000 2025 125000

Sample Output 5

410390562