Problem Statement

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

Determine whether it is possible to make A non-decreasing by performing the following operation at most 500000 times, and if possible, provide one sequence of operations to do so.

• Choose an integer i between 1 and N-1, inclusive. Simultaneously replace A_i with A_{i+1} + K, and A_{i+1} with A_i.

Constraints

• All input numbers are integers.
• 2 \leq N \leq 50
• 1 \leq K \leq 50
• 1 \leq A_i \leq 50

Sample Input 1

3 2
3 6 4

Sample Output 1

Yes
1
2

Let us perform the operation with i=2. This simultaneously replaces A_2 with A_3 + 2 = 6, and A_3 with A_2 = 6, making A = (3,6,6).

Now A is non-decreasing, so this output satisfies the conditions.

Sample Input 2

3 3
1 5 8

Sample Output 2

Yes
2
2 2

It is not necessary to minimize the number of operations.

Problem Statement

For a sequence A = (A_1, \ldots, A_N) of length N, define f(A) as follows.

• Prepare a graph with N vertices labeled 1 to N and zero edges. For every integer pair (i, j) satisfying 1 \leq i < j \leq N, if A_i \leq A_j, draw a bidirectional edge connecting vertices i and j. Define f(A) as the number of connected components in the resulting graph.

You are given a sequence B = (B_1, \ldots, B_N) of length N. Each element of B is -1 or an integer between 1 and M, inclusive.

By replacing every occurrence of -1 in B with an integer between 1 and M, one can obtain M^q sequences B', where q is the number of -1 in B.

Find the sum, modulo 998244353, of f(B') over all possible B'.

Constraints

• All input numbers are integers.
• 2 \leq N \leq 2000
• 1 \leq M \leq 2000
• Each B_i is -1 or an integer between 1 and M, inclusive.

Sample Input 1

3 3
2 -1 1

Sample Output 1

6

There are three possible sequences B': (2,1,1), (2,2,1), and (2,3,1).

When B' = (2,1,1), an edge is drawn only between vertices 2 and 3, so the number of connected components is 2. Thus, f(B') = 2.

Similarly, f(B') = 2 for B' = (2,2,1) and f(B') = 2 for B' = (2,3,1), so the answer is 2 + 2 + 2 = 6.

Sample Input 2

10 8
-1 7 -1 -1 -1 2 -1 1 -1 2

Sample Output 2

329785

Sample Input 3

11 12
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Sample Output 3

529513150

Remember to find the sum modulo 998244353.

Problem Statement

For a permutation P = (P_1, \ldots, P_N) of (1, \ldots, N), let P' = (P'_1, \ldots, P'_N) be the permutation obtained by performing the following operation once.

• For i = 1, 2, \ldots, N-1 in this order, if P_i > P_{i+1}, swap P_i and P_{i+1}.

You are given a sequence Q = (Q_1, \ldots, Q_N) of length N. Each Q_i is -1 or an integer between 1 and N, inclusive.

Find the number, modulo 998244353, of permutations P of (1, \ldots, N) such that, for every i, if Q_i \neq -1 then Q_i = P'_i.

Constraints

• All input numbers are integers.
• 2 \leq N \leq 5000
• Each Q_i is -1 or an integer between 1 and N.
• Each of 1,2,\ldots,N appears at most once in Q.

Sample Input 1

4
-1 -1 2 4

Sample Output 1

6

For example, P = (3,1,4,2) satisfies the conditions. This can be confirmed by the following behavior of the operation.

• For i=1, since P_1 > P_2, swap P_1 and P_2, resulting in P = (1,3,4,2).
• For i=2, since P_2 < P_3, do nothing.
• For i=3, since P_3 > P_4, swap P_3 and P_4, resulting in P = (1,3,2,4).
• Thus, P' = (1,3,2,4), satisfying P'_3=2 and P'_4=4.

There are six permutations P that satisfy the conditions:

• (1,3,4,2)
• (1,4,3,2)
• (3,1,4,2)
• (3,4,1,2)
• (4,1,3,2)
• (4,3,1,2)

Sample Input 2

6
-1 -1 -1 -1 2 -1

Sample Output 2

120

Sample Input 3

15
-1 -1 -1 -1 -1 4 -1 -1 -1 -1 7 -1 -1 -1 -1

Sample Output 3

237554682

Remember to find the count modulo 998244353.

Problem Statement

Define the cost of a sequence X as (the maximum value of X minus the minimum value of X).

You are given sequences A = (A_1, \ldots, A_N) and B = (B_1, \ldots, B_N) of length N. Solve the following problem for k = 1, 2, \ldots, N.

• Find the minimum possible cost of the sequence C = (C_1, \ldots, C_k) whose i-th element C_i is A_i or B_i.

Constraints

• All input numbers are integers.
• 1 \leq N \leq 5 \times 10^5
• 1 \leq A_i, B_i \leq 10^9

Sample Input 1

3
8 11 10
7 6 1

Sample Output 1

0
1
3

For k=1, if we choose C = (8), the cost of C is 0, which is the minimum.

For k=2, if we choose C = (7,6), the cost of C is 1, which is the minimum.

For k=3, if we choose C = (8,11,10), the cost of C is 3, which is the minimum.

Sample Input 2

10
43 35 36 58 25 7 61 4 96 3
55 29 88 15 99 49 67 57 92 49

Sample Output 2

0
8
8
23
28
33
36
36
64
64

Problem Statement

You are given a sequence A = (A_1, \ldots, A_N) of length N. Here, N is an integer not less than 3.

You can perform the following operation any number of times (zero or more).

• Choose an integer i satisfying 1 \leq i \leq N and A_i = A_{i+1} = A_{i+2}. Replace two of A_i, A_{i+1}, and A_{i+2} with integers between 1 and N, inclusive. Here, assume A_{N+1} = A_1 and A_{N+2} = A_2.

Find the number, modulo 998244353, of possible resulting sequences A that are permutations of (1, \ldots, N).

Constraints

• All input numbers are integers.
• 3 \leq N \leq 5 \times 10^5
• 1 \leq A_i \leq N

Sample Input 1

6
1 2 3 3 1 1

Sample Output 1

360

For example, we can obtain the permutation A = (1,2,4,3,5,6) through the following steps.

• Perform the operation with i=5. Replace A_5 with 3 and A_6 with 6. Now, A = (1,2,3,3,3,6).
• Perform the operation with i=3. Replace A_3 with 4 and A_5 with 5. Now, A = (1,2,4,3,5,6).

There are 360 possible resulting sequences A that are permutations of (1, \ldots, 6).

Sample Input 2

5
3 1 3 4 1

Sample Output 2

0

There are no possible resulting sequences A that are permutations of (1, \ldots, 5).

Sample Input 3

10
1 1 1 8 8 8 7 7 7 10

Sample Output 3

604800