Problem Statement

You are given integers x_1, x_2, and x_3. For these integers, you can perform the following operation any number of times, possibly zero.

• Choose a permutation (i,j,k) of (1,2,3), that is, a triple of integers (i,j,k) such that 1\leq i,j,k\leq 3 and i\neq j, i\neq k, j\neq k.
• Then, simultaneously replace x_i with x_i+3, x_j with x_j+5, and x_k with x_k+7.

Your objective is to satisfy x_1=x_2=x_3. Determine whether it is achievable. If it is, print the minimum number of times you need to perform the operation to achieve it.

You have T test cases to solve.

Constraints

• 1\leq T\leq 2\times 10^5
• 1\leq x_1, x_2, x_3 \leq 10^9

Sample Input 1

4
2 8 8
1 1 1
5 5 10
10 100 1000

Sample Output 1

2
0
-1
315

For the first test case, you can do the following to satisfy x_1=x_2=x_3.

• Perform the operation with (i,j,k) = (3,2,1), replacing (x_1,x_2,x_3) with (9,13,11).
• Perform the operation with (i,j,k) = (2,3,1), replacing (x_1,x_2,x_3) with (16,16,16).

Problem Statement

You are given non-zero integers x_1, \ldots, x_N. Find the minimum and maximum values of \dfrac{x_i+x_j+x_k}{x_ix_jx_k} for integers i, j, k such that 1\leq i < j < k\leq N.

Constraints

• 3\leq N\leq 2\times 10^5
• -10^6\leq x_i \leq 10^6
• x_i\neq 0

Sample Input 1

4
-2 -4 4 5

Sample Output 1

-0.175000000000000
-0.025000000000000

\dfrac{x_i+x_j+x_k}{x_ix_jx_k} can take the following four values.

• (i,j,k) = (1,2,3): \dfrac{(-2) + (-4) + 4}{(-2)\cdot (-4)\cdot 4} = -\dfrac{1}{16}.
• (i,j,k) = (1,2,4): \dfrac{(-2) + (-4) + 5}{(-2)\cdot (-4)\cdot 5} = -\dfrac{1}{40}．
• (i,j,k) = (1,3,4): \dfrac{(-2) + 4 + 5}{(-2)\cdot 4\cdot 5} = -\dfrac{7}{40}．
• (i,j,k) = (2,3,4): \dfrac{(-4) + 4 + 5}{(-4)\cdot 4\cdot 5} = -\dfrac{1}{16}.

Among them, the minimum is -\dfrac{7}{40}, and the maximum is -\dfrac{1}{40}.

Sample Input 2

4
1 1 1 1

Sample Output 2

3.000000000000000
3.000000000000000

Sample Input 3

5
1 2 3 4 5

Sample Output 3

0.200000000000000
1.000000000000000

Problem Statement

For a positive integer x, let f(x) denote the sum of its digits. For instance, f(158) = 1 + 5 + 8 = 14, f(2023) = 2 + 0 + 2 + 3 = 7, and f(1) = 1.

You are given a sequence of positive integers A = (A_1, \ldots, A_N). Find \sum_{i=1}^N\sum_{j=1}^N f(A_i + A_j).

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq A_i < 10^{15}

Sample Input 1

2
53 28

Sample Output 1

36

We have \sum_{i=1}^N\sum_{j=1}^N f(A_i + A_j) = f(A_1+A_1)+f(A_1+A_2)+f(A_2+A_1)+f(A_2+A_2)=7+9+9+11=36.

Sample Input 2

1
999999999999999

Sample Output 2

135

We have \sum_{i=1}^N\sum_{j=1}^N f(A_i + A_j) = f(A_1+A_1) = 135.

Sample Input 3

5
123 456 789 101 112

Sample Output 3

321

Problem Statement

You are given a positive integer n, and a prime number p at least 5.

Find a triple of integers (x,y,z) that satisfies all of the following conditions.

• 1\leq x < y < z \leq p - 1.
• (x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) \equiv x^{3n}+y^{3n}+z^{3n}\pmod{p}.

It can be proved that such a triple (x,y,z) always exists.

You have T test cases to solve.

Constraints

• 1\leq T\leq 10^5
• 1\leq n\leq 10^9
• p is a prime number satisfying 5\leq p\leq 10^9.

Sample Input 1

3
1 7
2 7
10 998244353

Sample Output 1

1 4 6
1 2 5
20380119 21549656 279594297

For the first test case:

• (x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) = (1+4+6)(1+4+6)(1+16+36) = 6413, and
• x^{3n}+y^{3n}+z^{3n} = 1 + 64 + 216 = 281.

We have 6413\equiv 281\pmod{7}, so the conditions are satisfied.

Problem Statement

We have a grid with 2 rows and N columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left. (i,j) has a postive integer x_{i,j} written on it.

Two squares are said to be adjacent when they share a side.

A path from square X to Y is a sequence (P_1, \ldots, P_n) of distinct squares such that P_1 = X, P_n = Y, and P_i and P_{i+1} are adjacent for every 1\leq i \leq n-1. Additionally, the weight of that path is the sum of integers written on P_1, \ldots, P_n.

For two squares X and Y, let f(X, Y) denote the minimum weight of a path from X to Y. Find the sum of f(X, Y) over all pairs of squares (X,Y), modulo 998244353.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq x_{i,j} \leq 10^9

Sample Input 1

1
3
5

Sample Output 1

24

You should find the sum of the following four values.

• For X = (1,1), Y = (1,1): f(X, Y) = 3.
• For X = (1,1), Y = (2,1): f(X, Y) = 8.
• For X = (2,1), Y = (1,1): f(X, Y) = 8.
• For X = (2,1), Y = (2,1): f(X, Y) = 5.

Sample Input 2

2
1 2
3 4

Sample Output 2

76

Sample Input 3

5
1 1000000000 1 1 1
1 1 1 1000000000 1

Sample Output 3

66714886

Problem Statement

For non-negative integers x and k, the k-th lowest digit of x is the remainder when \bigl\lfloor \frac{x}{10^k}\bigr\rfloor is divided by 10. For instance, the 0-th, 1-st, 2-nd, and 3-rd lowest digits of 123 are 3, 2, 1, and 0, respectively.

You are given positive integers N, M, K, and sequences of non-negative integers A = (A_1, \ldots, A_N) and B = (B_1, \ldots, B_N).

Consider rearranging A by the following process.

• Do the following M times.
  • Choose an integer k such that 0\leq k \leq K - 1.
  • Then, perform a stable sort on A by k-th lowest digit. That is, let A^{(d)} be the subsequence of A composed of all elements of A whose k-th lowest digits are d, and replace A with the concatenation of A^{(0)}, A^{(1)}, \ldots, A^{(9)} in this order.

There are K^M ways to execute this process. How many of them end up making A equal B? Find this count modulo 998244353.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq M\leq 10^9
• 1\leq K\leq 18
• 0\leq A_i < 10^K
• 0\leq B_i < 10^K
• A and B are equal as multisets. That is, every integer x occurs the same number of times in A and B.

Sample Input 1

3 2 3
74 42 54
42 54 74

Sample Output 1

5

Let k_1 and k_2 be the k chosen in the first and second iterations, respectively. For instance, if k_1 = 0 and k_2 = 1, then A changes as follows.

• A stable sort by k_1-th (0-th) lowest digit makes A = (42,74,54).
• A stable sort by k_2-th (1-st) lowest digit makes A = (42,54,74).

Here are all the ways to execute the process and the resulting A.

• (k_1, k_2) = (0,0): A = (42,74,54).
• (k_1, k_2) = (0,1): A = (42,54,74).
• (k_1, k_2) = (0,2): A = (42,74,54).
• (k_1, k_2) = (1,0): A = (42,54,74).
• (k_1, k_2) = (1,1): A = (42,54,74).
• (k_1, k_2) = (1,2): A = (42,54,74).
• (k_1, k_2) = (2,0): A = (42,74,54).
• (k_1, k_2) = (2,1): A = (42,54,74).
• (k_1, k_2) = (2,2): A = (74,42,54).

Sample Input 2

2 1 1
2 3
3 2

Sample Output 2

0

There is no way to satisfy the condition.

Sample Input 3

5 100 4
0 12 34 56 78
0 12 34 56 78

Sample Output 3

982924732

All 4^{100} ways satisfy the condition.