Problem Statement

You are given a positive integer N.

Find one permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) that minimizes \displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j.

Here, \displaystyle \bigoplus_{1\le j\le i} P_j is defined as the bitwise \mathrm{XOR} of P_1,P_2,\ldots,P_i.

You are given T test cases; solve each of them.

Constraints

• 1\le T\le 10^3
• 1\le N
• The sum of N over all test cases is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

3
3
1
7

Sample Output 1

1 3 2
1
4 5 3 2 6 7 1

Consider the first test case.

If P=(1,3,2), then \displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j=1 + (1 \oplus 3) + (1 \oplus 3 \oplus 2) = 1+2+0=3.

The value of \displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j cannot be made less than 3, so outputting P=(1,3,2) is correct.

Outputting P=(2,3,1) is also correct.

Problem Statement

You are given integers N,K and an integer sequence A=(A_1,A_2,\ldots,A_K) of length K. It is guaranteed that each element of A is between 1 and N, inclusive, and all elements are distinct.

For a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N), define f(P) as follows.

• The maximum number of times the following operation can be performed on P.
  • Choose 2\le i\le N satisfying P_i < \max(P_1,P_2,\ldots,P_{i-1}), and move P_i to the front. That is, replace P with (P_i,P_1,P_2,\ldots,P_{i-1},P_{i+1},\ldots,P_N).

There are (N-K)! permutations P of (1,2,\ldots,N) satisfying P_i=A_i for i=1,2,\ldots,K. Find the sum, modulo 998244353, of f(P) over all such permutations.

You are given T test cases; solve each of them.

Constraints

• 1\le T\le 10^5
• 1\le K\le N
• The sum of N over all test cases is at most 5\times 10^5.
• 1\le A_i\le N
• All elements of A are distinct.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
6
1382640

Consider the first test case.

The permutations P of (1,2,\ldots,N) satisfying P_i=A_i for i=1,2,\ldots,K are P=(1,2,3) and P=(1,3,2), giving two permutations.

When P=(1,2,3), no operation can be performed, so f(P)=0.

When P=(1,3,2), the operation can be performed twice as follows.

• Choose i=3. Now P=(2,1,3).
• Choose i=2. Now P=(1,2,3).

The operation cannot be performed three or more times, so f(P)=2 in this case.

Thus, the answer is 0+2=2.

Problem Statement

AtCoder Store has N items. The i-th item costs A_i yen.

N people visit the store one by one. Each person has C yen and performs the following procedure.

• Choose an integer x uniformly at random between 1 and C, inclusive, as the budget for shopping.
• If there is an item remaining in the store that costs at most x yen, purchase one of the most expensive ones among them. Otherwise, leave the store without purchasing anything.

As the owner of the store, you want to know how many items will be sold. For k=0,1,2,\ldots,N, find the probability, modulo 998244353, that exactly k items are sold in the end.

You are given T test cases; solve each of them.

Constraints

• 1\le T
• 1\le N
• The sum of N over all test cases is at most 100.
• 1\le A_i \le C < 998244353
• All input values are integers.

Sample Input 1

4
2 3
1 3
3 17
9 9 8
5 2025
1 1 1 1 1
6 1000
544 105 450 715 479 992

Sample Output 1

0 776412275 221832079
465698363 588015298 487439081 455335965
0 0 0 0 0 1
366062443 766314649 169448288 553531286 643499511 890090646 604030590

Consider the first test case.

For example, the procedure for each person proceeds as follows.

• Person 1: Chooses x=2. The most expensive item that costs at most 2 yen is the first item, so they purchase the first item.
• Person 2: Chooses x=1. There are no items costing at most 1 yen, so they leave without purchasing anything.

In this case, exactly one item is sold in the end.

The probabilities that exactly 0,1,2 items are sold are \displaystyle 0, \frac49,\frac59, respectively.

Problem Statement

You are given positive integers N,M and a sequence of positive integers A=(A_1,A_2,\ldots,A_N) of length N.

For a positive integer k, define f(k) as the answer to the following problem.

Takahashi has k yen. AtCoder Store has N items, and the i-th item costs A_i yen.

He performs the following action for i=1,2,\ldots,N in order.

• If the amount of money he currently has is at least A_i yen, he purchases the i-th item.

Find the total price of the items he purchased.

Find \displaystyle \bigoplus_{1\le k\le M} (k\times f(k)). Here, \displaystyle \bigoplus_{1\le k\le M} (k\times f(k)) is defined as the bitwise \mathrm{XOR} of 1\times f(1), 2\times f(2), \ldots, M\times f(M).

You are given T test cases; solve each of them.

Constraints

• 1\le T \le 10
• 1\le N,M
• The sum of N over all test cases is at most 5\times 10^5.
• The sum of M over all test cases is at most 5\times 10^7.
• 1\le A_i \le M
• All input values are integers.

Sample Input 1

3
3 6
2 3 1
5 10
3 1 4 1 5
7 12
4 2 3 4 2 3 3

Sample Output 1

61
115
190

Consider the first test case.

For example, when Takahashi's initial amount of money is 3 yen, he acts as follows.

• For i=1: he has 3 yen, which is at least 2 yen, so he purchases the first item.
• For i=2: he has 1 yen, which is less than 3 yen, so he does not purchase the second item.
• For i=3: he has 1 yen, which is at least 1 yen, so he purchases the third item.

From this, we get f(3)=2+1=3.

The values of f(1),f(2),f(3),f(4),f(5),f(6) are 1,2,3,3,5,6, respectively. Thus, the answer is the bitwise \mathrm{XOR} of 1,4,9,12,25,36, which is 61.

Problem Statement

You are given a tree with N vertices numbered 1 to N. Here, N is at least 2. The i-th edge (1\le i\le N-1) connects vertices u_i and v_i.

Perform the following operation on this tree exactly K times. The k-th operation (1\le k\le K) is as follows.

• Choose one of the N-2+k edges of the tree at that point uniformly at random. Let u and v be the vertices connected by the chosen edge. Prepare a new vertex N+k, add edges connecting vertices u and N+k and connecting vertices v and N+k, then delete the chosen edge.

Note that for k=1,2,\ldots,K, the tree will have N+k vertices after the k-th operation.

Find the expected value, modulo 998244353, of \displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) after K operations. Here, \text{dist}(i,j) denotes the distance between vertices i and j in the tree.

You are given T test cases; solve each of them.

Constraints

• 1\le T
• 2\le N
• The sum of N over all test cases is at most 3\times 10^5.
• 1\le K
• The sum of K over all test cases is at most 10^6.
• 1\le u_i < v_i \le N
• The given graph is a tree.
• All input values are integers.

Sample Input 1

3
4 2
1 2
1 3
1 4
4 5
1 2
2 3
3 4
6 13
1 2
1 3
2 4
2 5
3 6

Sample Output 1

499122208
120
713032723

Consider the first test case.

For example, the two operations proceed as follows.

• Operation 1: The edge connecting vertices 1 and 2 is chosen. After adding edges connecting vertices 1 and 5 and connecting vertices 2 and 5, the edge connecting vertices 1 and 2 is deleted.
• Operation 2: The edge connecting vertices 2 and 5 is chosen. After adding edges connecting vertices 2 and 6 and connecting vertices 5 and 6, the edge connecting vertices 2 and 5 is deleted.

In this case, the value of \displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) is 32.

The value of \displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) is 31 with probability \displaystyle \frac12 and 32 with probability \displaystyle \frac12.