Problem Statement

There are N items 1, 2, \dots, N.
Item i has weight w_i and value v_i.
For i = 2, 3, \dots, N, the following holds:

• \sum_{j=1}^{i-1}{w_j} < w_i

Choose some (possibly zero) items such that the total weight is at most W.
Find the maximum possible total value of the chosen items.
Solve T test cases per input.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 60
• 1 \leq w_i \leq W \leq 10^{18}
• \sum_{j=1}^{i-1}{w_j} < w_i \; (2 \leq i \leq N)
• 1 \leq v_i \leq 10^{16}
• 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 10
1 2
3 1
9 3
3 20
1 2
3 1
9 3
4 15
1 1
3 2
5 3
10 4

Sample Output 1

5
6
7

For the first test case, choosing items 1 and 3 gives a total weight of 10 and a total value of 5.
Moreover, it is impossible to achieve a total value of 6 or more while satisfying the condition.

Problem Statement

You are given an integer sequence A of length N and a positive integer K.
You can perform the following operation on A any number of times:

• Choose an integer i with 1 \leq i \leq N-1 such that A_i + A_{i+1} is divisible by K, and swap A_i and A_{i+1}.

Find the total number, modulo 998244353, of distinct sequences that A can become after performing the operation zero or more times.

Solve T test cases per input.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^9
• 1 \leq A_i \leq 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

3
4 3
1 2 4 7
6 4
1 5 3 6 2 4
3 2
2 2 3

Sample Output 1

4
6
1

For the first test case, the sequences that A can become after performing the operation zero or more times are these four: (1,2,4,7),(1,4,2,7),(1,4,7,2),(2,1,4,7).

Problem Statement

You are given a sequence A of N positive integers.
Find the remainder when \prod_{1 \leq i < j \leq N}|A_i-A_j| is divided by N.

Solve T test cases per input.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 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

3
3
1 9 5
3
2 2 3
5
11 33 22 55 44

Sample Output 1

2
0
3

For the first test case, |A_1-A_2| \times |A_1-A_3| \times |A_2-A_3|=8 \times 4 \times 4=128, and the remainder when this is divided by 3 is 2.

Problem Statement

There are A "draw" cards and B normal cards. Among the (A+B)! permutations of these A+B cards, one is chosen uniformly at random, and the cards are stacked top to bottom in that order to form a deck. Then, K cards are drawn from the top of the deck and placed in your hand. As long as your hand contains at least one draw card, repeat the following operation:

• Discard one draw card from your hand. The discarded card is removed from your hand and does not return to the deck.
• Let c be the number of cards remaining in the deck. Add \min(c,2) cards from the top of the deck to your hand.

Find the expected number, modulo 998244353, of cards in your final hand.

Solve T test cases per input.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq A, B
• 1 \leq K \leq A+B \leq 10^7
• The sum of A+B over all test cases is at most 10^7.
• All input values are integers.

Sample Input 1

4
2 2 3
1 2 1
10 20 4
20 10 4

Sample Output 1

2
332748119
944679050
774829082

For the first test case, the initial hand always contains at least 1 draw card, and the deck has 1 card remaining. After performing the operation once, the hand contains 1 draw card and 2 normal cards. After performing the operation once more, the hand contains 0 draw cards and 2 normal cards.
For the second test case, the final hand size is 2 if the first drawn card is a draw card, and 1 if it is a normal card. The expected value is \frac{1}{3} \times 2 + \frac{2}{3} \times 1 = \frac{4}{3}.

Problem Statement

You are given integer sequences A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_M) of length 2 or more, consisting of 0s and 1s.
You can perform the following operation on A any number of times:

• Choose an integer i satisfying 1 \leq i \leq |A|-1.
• Insert 1-A_i and 1-A_{i+1} in this order between A_i and A_{i+1}.

Determine whether it is possible to make A equal to B.

Solve T test cases per input.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq M \leq 2 \times 10^5
• A_i, B_i \in \{0,1\}
• The sum of N+M over all test cases is at most 4 \times 10^5.
• All input values are integers.

Sample Input 1

3
3 7
0 1 1
0 1 0 1 1 0 1
2 4
0 1
0 1 0 1
3 4
0 0 0
0 0 0 1

Sample Output 1

Yes
Yes
No

For the first test case, initially A=(0,1,1).
First, choosing i=2 gives A=(0,1,0,0,1).
Next, choosing i=3 gives A=(0,1,0,1,1,0,1).

Problem Statement

Define the score of a positive integer sequence with length 2 or more as the sum of its maximum and minimum values.
For a positive integer sequence A of length 2 or more, let f(A) be the maximum possible value of the total score of the contiguous subsequences when A is divided into one or more contiguous subsequences each of length 2 or more.
More formally, for a positive integer K, let f(A) be the maximum possible value of \sum_{k=1}^{K}\left(\max(B_k)+\min(B_k)\right) when concatenating K positive integer sequences B_1, B_2, \dots, B_K, each of length 2 or more, in this order yields the same sequence as A.

You are given an integer sequence Q of length N where each element is either an integer between 1 and N inclusive or -1, and a positive integer X.
Find the total number, modulo 998244353, of permutations P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N) satisfying all of the following conditions.

• For i=1,2,\dots,N, if Q_i \neq -1 then P_i=Q_i.
• f(P)=X

Solve T test cases per input.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 10^5
• 1 \leq X \leq 10^{18}
• Q_i=-1 or 1 \leq Q_i \leq N
• If Q_i \neq -1 and Q_j \neq -1, then Q_i \neq Q_j\;(i \neq j).
• The sum of N over all test cases is at most 10^5.
• All input values are integers.

Sample Input 1

3
3 4
2 -1 -1
4 10
1 3 4 2
9 42
-1 -1 -1 -1 -1 -1 -1 -1 -1

Sample Output 1

2
1
155520

For the first test case, the permutations P satisfying the first condition are these two: (2,1,3) and (2,3,1). In either case, the only way to divide P into contiguous subsequences each of length 2 or more is to take P itself as a single contiguous subsequence. The total score in that case is 3+1=4, so f(P)=4.
For the second test case, dividing P=(1,3,4,2) into (1,3) and (4,2) gives a total score of 10, which cannot be exceeded, so f(P)=10.