版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "比赛记录 - Codeforces Round #841 (Div. 2) and Divide by Zero 2022" date: 2022-12-28 20:11:31 categories:

• 算法竞赛 tags:
• 算法竞赛
• Codeforces
• 数学
• 贪心
• 暴力
• 位运算
• 数论
• 二分
• 前缀和
• 组合数学
• Lagrange插值

比赛链接

进度: 6 / 6

A - Joey Takes Money

Joey is low on money. His friend Chandler wants to lend Joey some money, but can't give him directly, as Joey is too proud of himself to accept it. So, in order to trick him, Chandler asks Joey to play a game

In this game, Chandler gives Joey an array $a_1, a_2, \dots, a_n$ ($n \geq 2$) of positive integers ($a_i \ge 1$)

Joey can perform the following operation on the array any number of times:

1. Take two indices $i$ and $j$ $(1 \le i < j \le n)$
2. Choose two integers $x$ and $y$ ($x, y \ge 1$) such that $x \cdot y = a_i \cdot a_j$
3. Replace $a_i$ by $x$ and $a_j$ by $y$

In the end, Joey will get the money equal to the sum of elements of the final array

Find the maximum amount of money $\mathrm{ans}$ Joey can get but print $2022 \cdot \mathrm{ans}$. Why multiplied by $2022$? Because we are never gonna see it again!

It is guaranteed that the product of all the elements of the array $a$ doesn't exceed $10^{12}$

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 4000$). Description of the test cases follows

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 50$) — the length of the array $a$

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^6$) — the array itself

It's guaranteed that the product of all $a_i$ doesn't exceed $10^{12}$ (i. e. $a_1 \cdot a_2 \cdot \ldots \cdot a_n \le 10^{12}$)

Output

For each test case, print the maximum money Joey can get multiplied by $2022$

Example

input

3
3
2 3 2
2
1 3
3
1000000 1000000 1

output

28308
8088
2022000000004044

Note

In the first test case, Joey can do the following:

1. He chooses $i = 1$ and $j = 2$ (so he has $a[i] \cdot a[j] = 6$), chooses $x = 6$ and $y = 1$ and makes $a[i] = 6$ and $a[j] = 1$.

   $$ [2, 3, 2] \xrightarrow[x = 6,\; y = 1]{i = 1,\; j = 2} [6, 1, 2] $$

2. He chooses $i = 1$ and $j = 3$ (so he has $a[i] \cdot a[j] = 12$), chooses $x = 12$ and $y = 1$ and makes $a[i] = 12$ and $a[j] = 1$.

   $$ [6, 1, 2] \xrightarrow[x = 12,\; y = 1]{i = 1,\; j = 3} [12, 1, 1] $$

The sum is $14$ which is the maximum of all possible sums. The answer is $2022 \cdot 14 = 28308$

代码参考

B - Kill Demodogs

Demodogs from the Upside-down have attacked Hawkins again. El wants to reach Mike and also kill as many Demodogs in the way as possible

Hawkins can be represented as an $n \times n$ grid. The number of Demodogs in a cell at the $i$-th row and the $j$-th column is $i \cdot j$. El is at position $(1, 1)$ of the grid, and she has to reach $(n, n)$ where she can find Mike

The only directions she can move are the right (from $(i, j)$ to $(i, j + 1)$) and the down (from $(i, j)$ to $(i + 1, j)$). She can't go out of the grid, as there are doors to the Upside-down at the boundaries

Calculate the maximum possible number of Demodogs $\mathrm{ans}$ she can kill on the way, considering that she kills all Demodogs in cells she visits (including starting and finishing cells)

Print $2022 \cdot \mathrm{ans}$ modulo $10^9 + 7$. Modulo $10^9 + 7$ because the result can be too large and multiplied by $2022$ because we are never gonna see it again!

(Note, you firstly multiply by $2022$ and only after that take the remainder.)

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). Description of the test cases follows

The first line of each test case contains one integer $n$ ($2 \leq n \leq 10^9$) — the size of the grid

Output

For each test case, print a single integer — the maximum number of Demodogs that can be killed multiplied by $2022$, modulo $10^9 + 7$

Example

input

4
2
3
50
1000000000

output

14154
44484
171010650
999589541

Note

In the first test case, for any path chosen by her the number of Demodogs to be killed would be $7$, so the answer would be $2022 \cdot 7 = 14154$

代码参考

C - Even Subarrays

You are given an integer array $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)

Find the number of subarrays of $a$ whose $\operatorname{XOR}$ has an even number of divisors. In other words, find all pairs of indices $(i, j)$ ($i \le j$) such that $ai \oplus a{i + 1} \oplus \dots \oplus a_j$ has an even number of divisors

For example, numbers $2$, $3$, $5$ or $6$ have an even number of divisors, while $1$ and $4$ — odd. Consider that $0$ has an odd number of divisors in this task

Here $\operatorname{XOR}$ (or $\oplus$) denotes the bitwise XOR operation

Print the number of subarrays but multiplied by 2022... Okay, let's stop. Just print the actual answer

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). Description of the test cases follows

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the length of the array $a$

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$)

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$

Output

For each test case, print the number of subarrays, whose $\operatorname{XOR}$ has an even number of divisors

Example

input

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

output

4
11
0
20

Note

In the first test case, there are $4$ subarrays whose $\operatorname{XOR}$ has an even number of divisors: $[3]$, $[3,1]$, $[1,2]$, $[2]$

In the second test case, there are $11$ subarrays whose $\operatorname{XOR}$ has an even number of divisors: $[4,2]$, $[4,2,1]$, $[4,2,1,5]$, $[2]$, $[2,1]$, $[2,1,5]$, $[2,1,5,3]$, $[1,5,3]$, $[5]$, $[5,3]$, $[3]$

In the third test case, there is no subarray whose $\operatorname{XOR}$ has an even number of divisors since $\operatorname{XOR}$ of any subarray is either $4$ or $0$

代码参考

D - Valiant's New Map

Game studio "DbZ Games" wants to introduce another map in their popular game "Valiant". This time, the map named "Panvel" will be based on the city of Mumbai

Mumbai can be represented as $n \times m$ cellular grid. Each cell $(i, j)$ ($1 \le i \le n$; $1 \le j \le m$) of the grid is occupied by a cuboid building of height $a_{i,j}$

This time, DbZ Games want to make a map that has perfect vertical gameplay. That's why they want to choose an $l \times l$ square inside Mumbai, such that each building inside the square has a height of at least $l$

Can you help DbZ Games find such a square of the maximum possible size $l$?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 1000$). Description of the test cases follows

The first line of each test case contains two positive integers $n$ and $m$ ($1 \le n \le m$; $1 \leq n \cdot m \leq 10^6$)

The $i$-th of next $n$ lines contains $m$ integers $a{i,1}, a{i,2}, \dots, a{i,m}$ ($1 \leq a{i,j} \leq 10^6$) — heights of buildings on the $i$-th row

It's guaranteed that the sum of $n \cdot m$ over all test cases doesn't exceed $10^6$

Output

For each test case, print the maximum side length $l$ of the square DbZ Games can choose

Example

input

4
2 2
2 3
4 5
1 3
1 2 3
2 3
4 4 3
2 1 4
5 6
1 9 4 6 5 8
10 9 5 8 11 6
24 42 32 8 11 1
23 1 9 69 13 3
13 22 60 12 14 17

output

2
1
1
3

Note

In the first test case, we can choose the square of side $l = 2$ (i. e. the whole grid) since the heights of all buildings are greater than or equal to $2$

In the second test case, we can only choose the side as $1$, so the answer is $1$

In the third test case, there are no squares of size $2$ that have all buildings of height at least $2$, so the answer is $1$

代码参考

E - Graph Cost

You are given an initially empty undirected graph with $n$ nodes, numbered from $1$ to $n$ (i. e. $n$ nodes and $0$ edges). You want to add $m$ edges to the graph, so the graph won't contain any self-loop or multiple edges

If an edge connecting two nodes $u$ and $v$ is added, its weight must be equal to the greatest common divisor of $u$ and $v$, i. e. $\gcd(u, v)$

In order to add edges to the graph, you can repeat the following process any number of times (possibly zero):

• choose an integer $k \ge 1$;
• add exactly $k$ edges to the graph, each having a weight equal to $k + 1$. Adding these $k$ edges costs $k + 1$ in total

Note that you can't create self-loops or multiple edges. Also, if you can't add $k$ edges of weight $k + 1$, you can't choose such $k$

For example, if you can add $5$ more edges to the graph of weight $6$, you may add them, and it will cost $6$ for the whole pack of $5$ edges. But if you can only add $4$ edges of weight $6$ to the graph, you can't perform this operation for $k = 5$

Given two integers $n$ and $m$, find the minimum total cost to form a graph of $n$ vertices and exactly $m$ edges using the operation above. If such a graph can't be constructed, output $-1$

Note that the final graph may consist of several connected components

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). Description of the test cases follows

The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 10^6$; $1 \leq m \leq \frac{n(n-1)}{2}$)

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$

Output

For each test case, print the minimum cost to build the graph, or $-1$ if you can't build such a graph

Example

input

4
4 1
6 10
9 4
10 11

output

2
-1
7
21

Note

In the first test case, we can add an edge between the vertices $2$ and $4$ with $\gcd = 2$. This is the only possible way to add $1$ edge that will cost $2$

In the second test case, there is no way to add $10$ edges, so the answer is $-1$

In the third test case, we can add the following edges:

• $k = 1$: edge of weight $2$ between vertices $2$ and $4$ ($\gcd(2, 4) = 2$). Cost: $2$;
• $k = 1$: edge of weight $2$ between vertices $4$ and $6$ ($\gcd(4, 6) = 2$). Cost: $2$;
• $k = 2$: edges of weight $3$: $(3, 6)$ and $(3, 9)$ ($\gcd(3, 6) = \gcd(3, 9) = 3$). Cost: $3$

As a result, we added $1 + 1 + 2 = 4$ edges with total cost $2 + 2 + 3 = 7$, which is the minimal possible cost

代码参考

F - Function Sum

Suppose you have an integer array $a_1, a_2, \dots, a_n$

Let $\operatorname{lsl}(i)$ be the number of indices $j$ ($1 \le j < i$) such that $a_j < a_i$

Analogically, let $\operatorname{grr}(i)$ be the number of indices $j$ ($i < j \le n$) such that $a_j > a_i$

Let's name position $i$ good in the array $a$ if $\operatorname{lsl}(i) < \operatorname{grr}(i)$

Finally, let's define a function $f$ on array $a$ $f(a)$ as the sum of all $a_i$ such that $i$ is good in $a$

Given two integers $n$ and $k$, find the sum of $f(a)$ over all arrays $a$ of size $n$ such that $1 \leq a_i \leq k$ for all $1 \leq i \leq n$ modulo $998\,244\,353$

Input

The first and only line contains two integers $n$ and $k$ ($1 \leq n \leq 50$; $2 \leq k < 998\,244\,353$)

Output

Output a single integer — the sum of $f$ over all arrays $a$ of size $n$ modulo $998\,244\,353$

Examples

input

3 3

output

28

input

5 6

output

34475

input

12 30

output

920711694

Note

In the first test case:

$$ \begin{array}{c|c} f([1,1,1]) = 0&f([2,2,3]) = 2 + 2 = 4\ f([1,1,2]) = 1 + 1 = 2&f([2,3,1]) = 2\ f([1,1,3]) = 1 + 1 = 2&f([2,3,2]) = 2\ f([1,2,1]) = 1&f([2,3,3]) = 2\ f([1,2,2]) = 1&f([3,1,1]) = 0\ f([1,2,3]) = 1&f([3,1,2]) = 1\ f([1,3,1]) = 1&f([3,1,3]) = 1\ f([1,3,2]) = 1&f([3,2,1]) = 0\ f([1,3,3]) = 1&f([3,2,2]) = 0\ f([2,1,1]) = 0&f([3,2,3]) = 2\ f([2,1,2]) = 1&f([3,3,1]) = 0\ f([2,1,3]) = 2 + 1 = 3&f([3,3,2]) = 0\ f([2,2,1]) = 0&f([3,3,3]) = 0\ f([2,2,2]) = 0\ \end{array} $$

Adding up all of these values, we get $28$ as the answer

代码参考