Problem Statement

There is an N \times N grid. The cell at the i-th row from the top and j-th column from the left is called (i,j).

For each way of writing 0 or 1 in each cell, define f(X) as follows:

• The number of ways to move from a cell with X written on it to another cell with X written on it by repeating the operation "move to the right adjacent cell or move to the down adjacent cell" one or more times.

Construct one way of writing that satisfies f(0) = f(1). It is guaranteed that a solution exists under the constraints of this problem.

Constraints

• 1 \le N \le 500

Sample Input 1

2

Sample Output 1

01
01

There is one way, shown below, to perform operations satisfying the condition for f(0), so f(0) = 1.

• Start from (1,1) and move to (2,1).

There is one way, shown below, to perform operations satisfying the condition for f(1), so f(1) = 1.

• Start from (1,2) and move to (2,2).

Since f(0) = f(1), the condition is satisfied.

Sample Input 2

6

Sample Output 2

100111
101000
100010
011101
010000
110001

Problem Statement

There is a traffic signal. This signal is always red, but when PCT-kun pays P yen and presses a button, it becomes green for X seconds. However, he must follow the following rules:

• The button can only be pressed at timings that can be expressed as time t for an integer t. (Negative integers can also be chosen as t.)
• If the button is pressed at time t, it cannot be pressed until time t+Y. (It can be pressed at time t+Y.)

There are N people crossing this signal. The i-th person tries to cross this signal at time A_i + 0.5, and if the signal is green at time A_i + 0.5, they pay C_i yen to PCT-kun.

Find the maximum possible value of money received by PCT-kun minus the cost of pressing the button.

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

Constraints

• 1 \le T \le 2 \times 10^5
• 1 \le N \le 2 \times 10^5
• 1 \le P \le 10^9
• 1 \le X \le Y \le 10^9
• 1 \le A_i \le 10^{18}
• 1 \le C_i \le 10^9
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

5
3 4 5 12
3 5 11
6 2 9
4 2 1 1
1 2 3 4
100 100 100 1
7 37 21 41
80 136 88 102 161 91 115
61 1 11 86 17 59 91
10 2763 2591 3369
2735 7773 36286 43737 9840 21707 19921 45759 44170 45287
3287 8050 3485 6845 3784 4565 3345 9297 2010 5550
15 408094769 859747485 886452311
1760053960 6327322912 490407029 1899495636 1174752626 84645660 6211206638 270040559 6098433044 4316510828 6601842919 5644655565 243073507 3150320792 4408022586
872391155 333542193 911310678 545186339 707811244 197915352 984885281 162966691 939525712 161385193 129092590 700676660 546046296 128723014 931663769

Sample Output 1

7
294
164
36403
6362927487

For the first test case, here is an example of PCT-kun's actions:

• Pay 4 yen and press the button at time -1. This makes the signal green from time -1 to time 4.
• Person 1 comes at time 3.5. Since the signal is green, they pay 6 yen to him.
• Person 2 comes at time 5.5. Since the signal is red, nothing happens.
• Pay 4 yen and press the button at time 11. This makes the signal green from time 11 to time 16.
• Person 3 comes at time 11.5. Since the signal is green, they pay 9 yen to him.

In this case, the money received by him minus the cost of pressing the button is 7 yen, and it can be proved that 7 yen is the maximum value.

For the second test case, here is an example of his actions:

• Pay 2 yen and press the button at time 1. This makes the signal green from time 1 to time 2.
• Person 1 comes at time 1.5. Since the signal is green, they pay 100 yen to him.
• Pay 2 yen and press the button at time 2. This makes the signal green from time 2 to time 3.
• Person 2 comes at time 2.5. Since the signal is green, they pay 100 yen to him.
• Pay 2 yen and press the button at time 3. This makes the signal green from time 3 to time 4.
• Person 3 comes at time 3.5. Since the signal is green, they pay 100 yen to him.

In this case, the money received by him minus the cost of pressing the button is 294 yen, and it can be proved that 294 yen is the maximum value.

Note that he can press the button at negative times.

Problem Statement

You are given two length-N sequences of non-negative integers: A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).

For a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N), define the cost of P as \sum_{i=1}^{N} \left \lfloor \frac{A_{P_i}}{2^{B_i}} \right \rfloor.

Find the number, modulo 998244353, of permutations P that achieve the minimum cost.

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

Constraints

• 1 \le T \le 2 \times 10^5
• 1 \le N \le 2 \times 10^5
• 1 \le A_i \le 10^9
• 0 \le B_i \le 30
• The sum of N over all test cases is at most 2 \times 10^5.

Sample Input 1

7
2
5 9
0 1
3
3 4 10
0 1 2
4
1 2 3 4
0 0 1 1
5
1000000000 1000000000 1000000000 1000000000 1000000000
0 0 0 0 0
11
19 68 97 62 99 52 57 19 43 80 96
5 3 3 2 3 4 3 2 3 4 3
14
86 49 83 31 5 43 7 46 98 36 60 4 69 59
3 1 4 4 4 0 1 3 0 4 3 5 1 2
10
907139744 237517128 852012347 350549430 62876062 196019710 263351472 184393437 281593038 753973502
23 12 1 26 29 24 0 7 10 4

Sample Output 1

1
2
4
120
8640
15552
1

For the first test case, the cost for each P is as follows:

• For P=(1,2), \left \lfloor \frac{A_{1}}{2^{B_1}} \right \rfloor + \left \lfloor \frac{A_{2}}{2^{B_2}} \right \rfloor = \left \lfloor \frac{5}{1} \right \rfloor + \left \lfloor \frac{9}{2} \right \rfloor = 9
• For P=(2,1), \left \lfloor \frac{A_{2}}{2^{B_1}} \right \rfloor + \left \lfloor \frac{A_{1}}{2^{B_2}} \right \rfloor = \left \lfloor \frac{9}{1} \right \rfloor + \left \lfloor \frac{5}{2} \right \rfloor = 11

Thus, the minimum cost is 9, and there is one permutation P = (1,2) that achieves it.

For the second test case, P = (1,2,3),(2,1,3) achieve the minimum cost of 7.

For the third test case, P = (1,2,3,4),(2,1,3,4),(1,2,4,3),(2,1,4,3) achieve the minimum cost of 6.

For the fourth test case, all permutations of (1,2,3,4,5) achieve the minimum cost of 5000000000.

Problem Statement

For a length-N sequence of positive integers A=(A_1,A_2,\dots,A_N), define f(A) as follows:

• The maximum value of A_iA_j + A_k over all triples of integers (i,j,k) satisfying 1 \le i < j < k \le N.

Find the number, modulo 998244353, of length-N sequences A of positive integers with all elements between 1 and M, inclusive, such that f(A) \le K.

Constraints

• 3 \le N \le 10^9
• 1 \le M,K \le 10^4

Sample Input 1

3 5 4

Sample Output 1

9

The sequences satisfying the condition are (1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,1,3),(1,2,2),(2,1,2),(1,3,1),(3,1,1), which is nine sequences.

Sample Input 2

4 5 7

Sample Output 2

66

Sample Input 3

123 456 789

Sample Output 3

436486661

Sample Input 4

1000000000 10000 10000

Sample Output 4

855626126

Problem Statement

Optimization Problem

You are given a length-N sequence of non-negative integers A=(A_1,A_2,\dots,A_N). Also, there is a length-N+1 sequence of non-negative integers X=(0,0,\dots,0).

You will now perform the following operation for i=1,2,\dots,N:

• Choose an integer v satisfying 0 \le v \le A_i, and add v and A_i-v to X_i and X_{i+1}, respectively.

Find the minimum possible value of the maximum value of X at the end of the operations.

You are given positive integers N, M, and a prime number P. Find the sum, modulo P, of the answers to the Optimization Problem for all sequences A=(A_1,A_2,\dots,A_N) of non-negative integers with length N and sum M.

Constraints

• 1 \le N \le 100
• 1 \le M \le 10^{18}
• 9 \times 10^8 \le P \le 10^9
• P is prime.

Sample Input 1

3 3 998244353

Sample Output 1

13

For example, we solve the Optimization Problem for A=(1,0,2). Here is a possible sequence of operations:

• For i = 1, let v = 1. X becomes (1,0,0,0).
• For i = 2, let v = 0. X remains (1,0,0,0).
• For i = 3, let v = 1. X becomes (1,0,1,1).

Since the maximum value of X cannot be made 0 or less, the answer is 1.

There are six other sequences with answer 1 and three sequences with answer 2, so the sum is 13.

Sample Input 2

10 135 998244353

Sample Output 2

679877945

Sample Input 3

100 1000000000000000000 924844033

Sample Output 3

789282612