Problem Statement

There is an integer X written on a blackboard. You can do the operation below any number of times (possibly zero).

• Choose an integer x written on the blackboard.
• Erase one x from the blackboard and write two new integers \lfloor \frac{x}{2}\rfloor and \lceil \frac{x}{2}\rceil.

Find the maximum possible product of the integers on the blackboard after your operations, modulo 998244353.

Constraints

• 1\leq X \leq 10^{18}

Sample Input 1

15

Sample Output 1

192

Here is a sequence of operations that makes the product of the integers on the blackboard 192.

• The initial state of the blackboard is (15).
• An operation with x = 15 changes it to (7, 8).
• An operation with x = 7 changes it to (8, 3, 4).
• An operation with x = 4 changes it to (8, 3, 2, 2).
• An operation with x = 8 changes it to (3, 2, 2, 4, 4).

Here, the product of the integers on the blackboard is 3\times 2\times 2\times 4\times 4 = 192.

Sample Input 2

3

Sample Output 2

3

Doing zero operations makes the product of the integers on the blackboard 3.

Sample Input 3

100

Sample Output 3

824552442

The maximum possible product of the integers on the blackboard after your operations is 5856458868470016, which should be printed modulo 998244353.

Problem Statement

You are given a sequence of N integers S = (S_1, \ldots, S_N). Determine whether there is a sequence of N+2 integers A = (A_1, \ldots, A_{N+2}) that satisfies the conditions below.

• 0\leq A_i for every i (1\leq i\leq N+2).
• S_i = A_{i} + A_{i+1} + A_{i+2} for every i (1\leq i\leq N).

If it exists, print one such sequence.

Constraints

• 1\leq N\leq 3\times 10^5
• 0\leq S_i\leq 10^9

Sample Input 1

5
6 9 6 6 5

Sample Output 1

Yes
0 4 2 3 1 2 2

We can verify that S_i = A_i + A_{i+1} + A_{i+2} for every i (1\leq i\leq N), as follows.

• 6 = 0 + 4 + 2.
• 9 = 4 + 2 + 3.
• 6 = 2 + 3 + 1.
• 6 = 3 + 1 + 2.
• 5 = 1 + 2 + 2.

Sample Input 2

5
0 1 2 1 0

Sample Output 2

No

Sample Input 3

1
10

Sample Output 3

Yes
0 0 10

Problem Statement

You are given a sequence of non-negative integers A = (A_1, \ldots, A_N). You can do the operation below any number of times (possibly zero).

• Choose an integer x\in \{A_1,\ldots,A_N\}.
• Replace A_i with A_i\oplus x for every i (\oplus denotes the bitwise \mathrm{XOR} operation).

Find the maximum possible value of \sum_{i=1}^N A_i after your operations.

Constraints

• 1\leq N \leq 3\times 10^{5}
• 0\leq A_i < 2^{30}

Sample Input 1

5
1 2 3 4 5

Sample Output 1

19

Here is a sequence of operations that achieves \sum_{i=1}^N A_i = 19.

• Initially, the sequence A is (1,2,3,4,5).
• An operation with x = 1 changes it to (0,3,2,5,4).
• An operation with x = 5 changes it to (5,6,7,0,1), where \sum_{i=1}^N A_i = 5 + 6 + 7 + 0 + 1 = 19.

Sample Input 2

5
10 10 10 10 10

Sample Output 2

50

Doing zero operations achieves \sum_{i=1}^N A_i = 50.

Sample Input 3

5
3 1 4 1 5

Sample Output 3

18

Problem Statement

We have an H \times W grid, where each square has one integer written on it. For 1\leq i\leq H and 1\leq j\leq W, let A_{i,j} denote the integer written on the square at the i-th row and j-th column.

You can do the operation below any number of times (possibly zero).

• Choose integers i and j such that 1\leq i\leq H - 1 and 1\leq j\leq W - 1.
• Choose another integer x.
• Add x to each of A_{i,j}, A_{i,j+1}, A_{i+1,j}, and A_{i+1,j+1}.

Print the minimum possible value of \sum_{i=1}^H \sum_{j=1}^W |A_{i,j}| after your operations, and the integers on the grid when that value is achieved.

Constraints

• 2\leq H, W \leq 500
• |A_{i,j}|\leq 10^9

Sample Input 1

2 3
1 2 3
4 5 6

Sample Output 1

9
0 -3 -1
3 0 2

Here is a sequence of operations that produces the grid in the Sample Output.

• Do the operation with (i, j, x) = (1, 1, -1).
• Do the operation with (i, j, x) = (1, 2, -4).

Here, we have \sum_{i=1}^H \sum_{j=1}^W |A_{i,j}| = 0 + 3 + 1 + 3 + 0 + 2 = 9.

Sample Input 2

2 2
1000000000 -1000000000
-1000000000 1000000000

Sample Output 2

4000000000
2000000000 0
0 2000000000

It is fine if |A_{i,j}| > 10^9 after your operations.

Sample Input 3

3 4
0 2 0 -2
-3 -1 2 0
-3 -3 2 2

Sample Output 3

0
0 0 0 0
0 0 0 0
0 0 0 0

Problem Statement

You are given integers N and X. Assume that an integer sequence A = (A_1, \ldots, A_N) satisfies all of the conditions below.

• A_1 = X.
• For every i (1\leq i\leq N), A_i is a multiple of i.
• A is strictly increasing. In other words, A_1 < \cdots < A_N holds.

Find the minimum possible value of \sum_{i=1}^N A_i, modulo 998244353.

There are T test cases, each of which should be solved.

Constraints

• 1\leq T\leq 10
• 1\leq N \leq 10^{18}
• 1\leq X \leq 10^{18}

Sample Input 1

5
5 100
1 10
10 1
1000000000000000000 1
100 100

Sample Output 1

525
10
55
75433847
61074

Here is a sequence A that minimizes \sum_{i=1}^N A_i for each of the first three test cases.

• The first test case: A = (100, 102, 105, 108, 110).
• The second test case: A = (10).
• The third test case: A = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10).

Problem Statement

You are given an integer N. On an integer sequence A = (1, 2, \ldots, N), let us do the operation below exactly K times.

• Let n be the current number of terms in A. For all i such that 1\leq i \leq n and i\equiv 1\pmod{3}, delete the i-th term of A, simultaneously.

Find the sum of the terms of A after K operations, modulo 998244353.

Constraints

• 1\leq N\leq 10^{14}
• 1\leq K\leq 100

Sample Input 1

10 2

Sample Output 1

25

• Initially, we have A = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10).
• After the first operation, we have A = (2, 3, 5, 6, 8, 9).
• After the second operation, we have A = (3, 5, 8, 9).
• The sum of the terms here is 3 + 5 + 8 + 9 = 25.

Sample Input 2

10 10

Sample Output 2

0

• After the second operation, we have A = (3, 5, 8, 9) (same as Sample Input 1).
• After the third operation, we have A = (5, 8).
• After the fourth operation, we have A = (8).
• After the fifth operation, A is empty.
• In the sixth and subsequent operations, A remains empty, where the sum of the terms is 0.

Sample Input 3

10000 10

Sample Output 3

862816