Problem Statement

You are given a permutation A = (A_1, A_2, \dots, A_N) of (1, 2, \dots, N).
For a pair of integers (L, R) such that 1 \leq L \leq R \leq N, let f(L, R) be the permutation obtained by reversing the L-th through R-th elements of A, that is, replacing A_L, A_{L+1}, \dots, A_{R-1}, A_R with A_R, A_{R-1}, \dots, A_{L+1}, A_{L} simultaneously.

There are \frac{N(N + 1)}{2} ways to choose (L, R) such that 1 \leq L \leq R \leq N.
If the permutations f(L, R) for all such pairs (L, R) are listed and sorted in lexicographical order, what is the K-th permutation from the front?

Constraints

• 1 \leq N \leq 7000
• 1 \leq K \leq \frac{N(N + 1)}{2}
• A is a permutation of (1, 2, \dots, N).

Sample Input 1

3 5
1 3 2

Sample Output 1

2 3 1

Here are the permutations f(L, R) for all pairs (L, R) such that 1 \leq L \leq R \leq N.

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

When these are sorted in lexicographical order, the fifth permutation is f(1, 3) = (2, 3, 1), which should be printed.

Sample Input 2

5 15
1 2 3 4 5

Sample Output 2

5 4 3 2 1

The answer is f(1, 5).

Sample Input 3

10 37
9 2 1 3 8 7 10 4 5 6

Sample Output 3

9 2 1 6 5 4 10 7 8 3

Problem Statement

You are given a positive integer N.

Find the number, modulo 998244353, of triples of positive integers (x,y,z) that satisfy the following condition.

• All of xy, yz, zx are less than or equal to N.

You have T test cases to solve.

Constraints

• 1 \le T \le 100
• 1 \le N \le 10^9

Sample Input 1

4
1
2
5
998244353

Sample Output 1

1
4
17
727512986

In the first test case, N=1. There is one triple (x,y,z) that satisfies the condition: (1,1,1).

In the second test case, N=2. There are four triples (x,y,z) that satisfy the condition: (1,1,1),(2,1,1),(1,2,1),(1,1,2).

Problem Statement

You are given a multiset of positive integers with N elements: A=\lbrace A_1,A_2,\dots,A_N \rbrace.

You may repeat the following operation any number of times (possibly zero).

• Choose a positive integer x that occurs at least twice in A. Delete two occurrences of x from A, and add one occurrence of x+1 to A.

Find the number, modulo 998244353, of multisets that A can be in the end.

Constraints

• 1 \le N \le 2 \times 10^5
• 1 \le A_i \le 2 \times 10^5

Sample Input 1

4
1 1 2 4

Sample Output 1

3

A can be one of the three multisets \lbrace 1,1,2,4 \rbrace,\lbrace 2,2,4 \rbrace,\lbrace 3,4 \rbrace in the end.

You can make A = \lbrace 3,4 \rbrace as follows.

• Choose x = 1. Delete two 1s from A and add one 2 to A, making A=\lbrace 2,2,4 \rbrace.
• Choose x = 2. Delete two 2s from A and add one 3 to A, making A=\lbrace 3,4 \rbrace.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

1

Sample Input 3

13
3 1 4 1 5 9 2 6 5 3 5 8 9

Sample Output 3

66

Problem Statement

Find the number, modulo 998244353, of sequences of N non-negative integers A=(A_1,A_2,\dots,A_N) totaling M that satisfy the following condition.

• It is possible to make all elements of A equal 0 by repeatedly choosing one of the following operations and performing it.
  • Choose an integer i such that 1 \le i \le N and decrease A_i by K.
  • Choose an integer i such that 1 \le i \le N-K+1 and decrease each of A_i,A_{i+1},\dots,A_{i+K-1} by 1.

Constraints

• 1 \le K \le N \le 2000
• 1 \le M \le 10^{18}

Sample Input 1

3 2 2

Sample Output 1

5

The following five sequences satisfy the requirements.

• (1,1,0)
• (0,1,1)
• (2,0,0)
• (0,2,0)
• (0,0,2)

For instance, if A=(0,1,1), you can do the following to make all elements of A equal 0.

• Perform the second operation. Choose i = 2 to decrease each of A_2 and A_3 by 1, making A=(0,0,0).

Sample Input 2

100 998244353 100

Sample Output 2

0

There may be no sequence that satisfies the requirements.

Sample Input 3

2000 545782618661124208 533

Sample Output 3

908877889

Problem Statement

You are given an undirected tree G with N vertices. The degree of every vertex in G is at most 3.
The vertices are numbered 1 to N. The edges are numbered 1 to N-1, and edge i connects vertex u_i and vertex v_i.
Each vertex has a fixed weight, and the weight of vertex i is W_i.

You will add zero or more edges to G. The cost of adding an edge between vertex i and vertex j is W_i + W_j.

Print one way to add edges to satisfy the following condition for the minimum possible total cost.

• G is 2-vertex-connected. In other words, for every vertex v in G, removing v and its incident edges from G would not disconnect G.

You have T test cases to solve.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 3 \leq N \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N
• The given graph is a tree.
• The degree of every vertex in the given graph is at most 3.
• 1 \leq W_i \leq 10^9
• W_i is an integer.
• The sum of N across the test cases is at most 2 \times 10^5.

Sample Input 1

2
3
2 3 5
1 2
2 3
7
1 10 100 1000 10000 100000 1000000
1 2
2 3
2 4
3 5
3 6
4 7

Sample Output 1

1
1 3
2
7 6
1 5

In the first test case, adding an edge connecting vertex 1 and vertex 3 makes G satisfy the condition in the problem statement.
The cost of this is W_1 + W_3 = 2 + 5 = 7. There is no way to add edges to satisfy the condition for a cost of less than 7, so this is a valid solution.

In the second test case, the solution above has a total cost of (W_7 + W_6) + (W_1 + W_5) = 1100000 + 10001 = 1110001, which is the minimum possible.

Problem Statement

There are an integer N and M pairs of integers: (a_1, b_1), (a_2, b_2), \dots, (a_M, b_M). Each pair (a_i, b_i) satisfies 1 \leq a_i \lt b_i \leq N.

Initally, you have all N! permutations of (1,2,\dots,N).
You will perform M operations. The i-th operation is as follows.

• Do the following for each of your N! permutations.
  • Compare the a_i-th and b_i-th elements. If the former is greater, swap the two elements.

For each 1 \leq i \leq M, let S_i be the number of permutations of yours that are already sorted in ascending order at the end of the i-th operation.
Print S_1, S_2, \dots, S_M.

Here, the input gives you pairs of integers (x_i, y_i) instead of (a_i, b_i).
The values of (a_i, b_i) can be obtained using x_i, y_i, and S_{i-1} as follows. (Let S_0 = 1 for convenience.)

• Let c_i = ((x_i + S_{i-1}) \bmod N) + 1.
• Let d_i = ((y_i + S_{i-1} \times 2) \bmod N) + 1. (Here, it is guaranteed that c_i \neq d_i.)
• Let a_i = \min(c_i, d_i).
• Let b_i = \max(c_i, d_i).

Constraints

• 2 \leq N \leq 15
• 1 \leq M \leq 5 \times 10^5
• 1 \leq a_i \lt b_i \leq N
• 0 \leq x_i, y_i \leq N - 1

Sample Input 1

2 1
1 1

Sample Output 1

2

You start with the permutations (1, 2) and (2, 1).
We have (a_1, b_1) = (1, 2). At the end of the first operation, you have two copies of (1, 2), so you should print 2.

Sample Input 2

3 4
0 1
2 1
1 1
0 1

Sample Output 2

2
4
4
6

(a_i, b_i) in order are (1, 2), (2, 3), (1, 3), (1, 2).

Sample Input 3

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

Sample Output 3

2
4
4
8
16

(a_i, b_i) in order are (1, 2), (3, 4), (1, 5), (2, 3), (4, 5).