Problem Statement

There are N permutations of (1,2,\dots,L). The i-th permutation is P_i, and the j-th element of P_i is P_{i,j} (1 \le j \le L).

Initially, you have A = (1,2,\dots,L), and your initial amount of money is 0 yen. From now on, for i = 1,2,\dots,N in this order, you will perform the following operation:

1. First, perform zero or one swap of two adjacent elements in A.
   • Specifically, “a swap of two adjacent elements in A” means choosing j with 1 \le j \le L-1, and swapping A_j and A_{j+1}.
2. Then, if A is equal to P_i, you gain C_i yen.

Find the maximum possible amount of money you can have at the end.

Constraints

• 1 \leq N \leq 3 \times 10^4
• 1 \leq L \leq 9
• 0 \leq C_i \leq 10^4
• Each P_i is a permutation of (1,2,\dots,L).
• All input values are integers.

Sample Input 1

4 3
200 2 1 3
400 3 1 2
300 2 3 1
100 3 2 1

Sample Output 1

600

By doing the operations as follows, you can end up with 600 yen.

• For i=1: swap A_1 and A_2, so A=(2,1,3). We have A=P_1, so you gain 200 yen.
• For i=2: swap A_2 and A_3, so A=(2,3,1). We have A \neq P_2.
• For i=3: do not swap, so A=(2,3,1). We have A=P_3, so you gain 300 yen.
• For i=4: swap A_1 and A_2, so A=(3,2,1). We have A=P_4, so you gain 100 yen.

Sample Input 2

2 1
0 1
10000 1

Sample Output 2

10000

Sample Input 3

1 9
2025 2 4 6 8 7 5 1 9 3

Sample Output 3

0

Sample Input 4

10 5
2615 5 1 3 4 2
4275 1 3 2 5 4
4331 3 1 5 2 4
1457 3 5 1 2 4
2222 1 3 2 4 5
5051 2 4 5 3 1
1082 2 3 1 5 4
1579 4 1 5 2 3
2855 5 1 3 2 4
5848 2 4 3 1 5

Sample Output 4

12345

Problem Statement

You are given non-negative integers q,L,R\;(q \in \{ 0,1\}, \; L \leq R). Consider a set S that satisfies all of the following conditions.

• S consists of distinct integers between L and R, inclusive.
• If a \in S, \; b \in S, \; a \neq b, then a and b differ in at least two digits in binary representation. More formally, there exist at least two non-negative integers i such that \left\lfloor\frac{a}{2^i}\right\rfloor and \left\lfloor\frac{b}{2^i}\right\rfloor have different parities.
• Among those satisfying the above two conditions, the number of elements is maximum.

If q=0, find the number of elements in such a set S.
If q=1, construct one such set S.

For each input file, solve T test cases.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 0 \leq q \leq 1
• 0 \leq L \leq R \leq 10^{18}
• The sum of q(R-L) over all test cases is at most 5\times 10^6.
• All input values are integers.

Sample Input 1

3
1 0 3
0 1 2
1 213 213

Sample Output 1

1001
2
1

In the first test case, S=\{0,3\} satisfies the conditions. S=\{1,2\} also satisfies the conditions, so it is correct as well.
In the second test case, the only S that satisfies the conditions is \{1,2\}, whose number of elements is 2.

Problem Statement

You are given two trees T and U, each with N vertices numbered from 1 to N. The i-th edge of T connects vertices u_i and v_i. The i-th edge of U connects vertices b_i and c_i.
You are also given a length-N integer sequence A=(A_1,A_2,\dots,A_N).

For k = 1, 2, \dots, N, solve the following subproblem.

Does there exist a tuple of integers (x_1, x_2, x_3, x_4) that satisfies the following conditions? If so, find the minimum value of \sum_{i=1}^4 A_{x_i} for a tuple satisfying the conditions.

• x_1, x_2, x_3, x_4 are all distinct.
• x_1, x_2, x_3, x_4 are all different from k.
• For all integers (i,j) satisfying 1 \leq i \lt j \leq 4, the x_i x_j path in T contains vertex k, and the x_i x_j path in U also contains vertex k.

You are given t test cases; solve the problem for each of them.

Constraints

• 1 \leq t \leq 10^5
• 5 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq u_i \lt v_i \leq N
• 1 \leq b_i \lt c_i \leq N
• T and U are trees.
• The sum of N over all test cases is at most 10^5.
• All input values are integers.

Sample Input 1

2
5
20 26 1 25 213
1 5
3 5
2 5
4 5
4 5
1 5
2 5
3 5
20
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288
1 2
2 3
1 4
1 5
2 6
3 7
3 8
3 9
2 10
1 11
8 12
6 13
5 14
11 15
13 16
1 17
7 18
9 19
15 20
1 2
2 3
2 4
4 5
2 6
1 7
6 8
3 9
3 10
7 11
7 12
1 13
3 14
3 15
8 16
1 17
3 18
2 19
1 20

Sample Output 1

-1 -1 -1 -1 72
70664 616 131968 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

For the first test case, when k=1,2,3,4, there does not exist (x_1, x_2, x_3, x_4) satisfying the conditions. When k=5, (x_1,x_2,x_3,x_4) = (1,2,3,4) satisfies the conditions.

Problem Statement

You are given positive integers N and K satisfying 1\leq K\leq N.

For a permutation P = (P_{1}, P_{2}, \dots , P_{N}) of (1, 2, \dots , N), define f(P) as follows:

• The minimum possible value of the number of inversions of a length-N integer sequence A = (A_{1}, A_{2}, \dots, A_{N}) satisfying the following condition:
  • |A_{i}| = P_{i} for every integer 1\leq i\leq N.

For a = 1, 2, \dots, N, answer the following question:

There are (N - 1)! permutations P = (P_{1}, P_{2}, \dots , P_{N}) of (1, 2, \dots , N) satisfying P_{K} = a. Find the sum, modulo 998244353, of f(P) over all of them.

Constraints

• 1\leq K\leq N\leq 2\times 10^{5}
• All input values are integers.

Sample Input 1

4 2

Sample Output 1

3
3
6
8

Sample Input 2

1 1

Sample Output 2

0

Sample Input 3

16 7

Sample Output 3

262718137
262718137
826158422
869037161
443336358
897729892
154945392
124681723
861272045
3176021
900143166
451899023
365015181
740245202
732524873
391198612