Problem Statement

We have N_2 sticks of length 2 each, N_3 sticks of length 3 each, and N_4 sticks of length 4 each. You can do the following operation any number of times.

• Choose two sticks.
• Let x and y be the lengths of these sticks. Bond them to form a stick of length x+y.

Find the maximum number of sticks that can be made whose lengths are exactly 10.

Given T test cases, solve each of them.

Constraints

• 1\leq T\leq 100
• 0\leq N_2, N_3, N_4\leq 10^{15}

Sample Input 1

5
3 4 1
7 0 0
0 0 7
0 0 0
1000000000000000 1000000000000000 1000000000000000

Sample Output 1

2
1
0
0
900000000000000

Let us describe the first case. We have three sticks of length 2, four sticks of length 3, and one stick of length 4.

One way to make two sticks of length exactly 10 is as follows.

• Bond four sticks of length 2, 2, 3, 3 in some order to make one stick of length 10.
• Bond three sticks of length 3, 3, 4 in some order to make one stick of length 10.
• Now we have three sticks of length 2, 10, 10.

Problem Statement

In the coordinate plane, we have 2N vertices whose x-coordinates are 1, 2, \ldots, N and whose y-coordinates are 0 or 1: (1, 0),\ldots, (N,0), (1,1), \ldots, (N,1). There are M segments that connect two of these vertices: the i-th segment connects (a_i, 0) and (b_i, 1).

Consider choosing K of these M segments so that no two chosen segments contain the same point. Here, we consider both endpoints of a segment to be contained in that segment. Find the maximum possible value of K.

Constraints

• 1\leq N, M \leq 2\times 10^5
• 1\leq a_i, b_i\leq N
• a_i\neq a_j or b_i\neq b_j, if i\neq j.

Sample Input 1

3 3
1 2
2 3
3 1

Sample Output 1

2

One optimal solution is to choose the first and second segments.

The first and third segments, for example, contain the same point \left(\frac53, \frac23\right), so we cannot choose them both.

Sample Input 2

3 5
1 1
2 1
2 2
3 2
3 3

Sample Output 2

3

One optimal solution is to choose the first, third, and fifth segments.

The first and second segments, for example, contain the same point (1, 1), so we cannot choose them both.

Sample Input 3

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

Sample Output 3

1

Problem Statement

Given is a sequence of N positive integers: A = (A_1, A_2, \ldots, A_N). You can do the following operation on this sequence at least zero and at most K times:

• choose i\in \{1,2,\ldots,N\} and add 1 to A_i.

Find the maximum possible value of \gcd(A_1, A_2, \ldots, A_N) after your operations.

Constraints

• 2\leq N\leq 3\times 10^5
• 1\leq K\leq 10^{18}
• 1 \leq A_i\leq 3\times 10^5

Sample Input 1

3 6
3 4 9

Sample Output 1

5

One way to achieve \gcd(A_1, A_2, A_3) = 5 is as follows.

• Do the operation with i = 1 twice, with i = 2 once, and with i = 3 once, for a total of four times, which is not more than K=6.
• Now we have A_1 = 5, A_2 = 5, A_3 = 10, for which \gcd(A_1, A_2, A_3) = 5.

Sample Input 2

3 4
30 10 20

Sample Output 2

10

Doing no operation achieves \gcd(A_1, A_2, A_3) = 10.

Sample Input 3

5 12345
1 2 3 4 5

Sample Output 3

2472

Problem Statement

Given is a sequence of N positive integers A = (A_1, A_2, \ldots, A_N), where each A_i is 1, 2, \ldots, or K.

You can do the following operation on this sequence any number of times.

• Swap two adjacent elements, that is, choose i and j such that |i-j|=1 and swap A_i and A_j.

Find the minimum number of operations needed to make A satisfy the following condition.

• A contains (1, 2, \ldots, K) as a contiguous subsequence, that is, there is a positive integer n at most N-K+1 such that A_n = 1, A_{n+1} = 2, \ldots, and A_{n+K-1} = K.

Constraints

• 2\leq K\leq 16
• K \leq N\leq 200
• A_i is 1, 2, \ldots, or K.
• A contains at least one occurrence of each of 1, 2, \ldots, K.

Sample Input 1

4 3
3 1 2 1

Sample Output 1

2

One optimal sequence of operations is as follows.

• Swap A_1 and A_2, changing A to (1,3,2,1).
• Swap A_2 and A_3, changing A to (1,2,3,1).
• Now we have A_1 = 1, A_2 = 2, A_3 = 3, satisfying the condition.

Sample Input 2

5 5
4 1 5 2 3

Sample Output 2

5

Sample Input 3

8 4
4 2 3 2 4 2 1 4

Sample Output 3

5

Problem Statement

Given are a sequence of N positive integers A = (A_1, A_2, \ldots, A_N) and Q queries. The i-th query is as follows:

• given integers x_i and y_i (where 1\leq x_i\leq N), change A_{x_i} to y_i.

Each time the query changes the sequence, find the answer to the following problem modulo 998244353 (see Notes).

Let f(n) be the maximum total number of points when doing the following operation n times on A.

• Choose i, j such that A_i\leq A_j and choose non-negative real number x such that A_i + 2x \leq A_j.
• Add x to A_i and subtract x from A_j.
• Gain x points.

It can be proved that the limit \displaystyle \lim_{n\to\infty} f(n) exists. Find this limit.

Notes

We can prove that the limit in question is always a rational number. Additionally, under the Constraints of this problem, when that number is represented as \frac{P}{Q} using two coprime integers P and Q, we can prove that there is a unique integer R such that R\times Q\equiv P\pmod{998244353} and 0\leq R < 998244353. Find this R.

Constraints

• 2\leq N\leq 3\times 10^5
• 1\leq Q\leq 3\times 10^5
• 1\leq A_i \leq 10^9
• 1\leq x_i\leq N
• 1\leq y_i\leq 10^9

Sample Input 1

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

Sample Output 1

0
1
2
2

The first query changes the sequence to (5, 5, 5). Here, we have f(n) = 0 for any n, so the answer is 0.

The second query changes the sequence to (5, 6, 5). Here, one possible way to do the operations is as follows.

• Choose (i,j,x) = (3,2,0.4), changing the sequence to (5, 5.6, 5.4) and gaining 0.4 points.
• Choose (i,j,x) = (1,2,0.3), changing the sequence to (5.3, 5.3, 5.4) and gaining 0.3 points.

The above two operations gain 0.7 points, from which we can see that f(2) \geq 0.7.

We can prove that it is impossible to gain more than 1 point in total, and that the total number of points that can be gained by the optimal way to do the operations tends to 1 as the number of operations increases. Thus, we have \displaystyle \lim_{n\to\infty} f(n) = 1.

Sample Input 2

2 4
1 2
2 5
1 3
1 2
2 3

Sample Output 2

2
1
499122178
499122177

Problem Statement

Given is a sequence of N positive integers X = (X_1, X_2, \ldots, X_N).

For a positive integer K, let f(K) be the number of triples of integers (a,b,c) that satisfy all of the following conditions.

• 1\leq c \leq K.
• 0\leq a < c and 0\leq b < c.
• For each i, let Y_i be the remainder when aX_i + b is divided by c. Then, Y_1 < Y_2 < \cdots < Y_N holds.

It can be proved that the limit \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} exists. Find this value modulo 998244353 (see Notes).

Notes

We can prove that the limit in question is always a rational number. Additionally, under the Constraints of this problem, when that number is represented as \frac{P}{Q} using two coprime integers P and Q, we can prove that there is a unique integer R such that R\times Q\equiv P\pmod{998244353} and 0\leq R < 998244353. Find this R.

Constraints

• 2\leq N\leq 10^3
• X_i are positive integers such that \sum_{i=1}^N X_i \leq 5\times 10^5.
• X_i\neq X_j if i\neq j.

Sample Input 1

3
3 1 2

Sample Output 1

291154603

• For example, when (a,b,c) = (3,5,7), we have Y_1 = 0, Y_2 = 1, Y_3 = 4, which satisfy Y_1 < Y_2 < Y_3.
• We have f(1) = 0, f(2) = 0, f(3) = 1, f(4) = 2, f(5) = 5.
• We have \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{1}{24}.

Sample Input 2

3
5 9 2

Sample Output 2

832860616

We have \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{55}{1008} .

Sample Input 3

2
2 3

Sample Output 3

166374059

We have \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{1}{6}.

Sample Input 4

4
4 5 3 2

Sample Output 4

0

We have \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = 0.