apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of $$$n$$$ ($$$n \geq 2$$$) positive integers and an integer $$$p$$$. Consider an undirected weighted graph of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$ for which the edges between the vertices $$$i$$$ and $$$j$$$ ($$$i<j$$$) are added in the following manner:

- If $$$gcd(a_i, a_{i+1}, a_{i+2}, \dots, a_{j}) = min(a_i, a_{i+1}, a_{i+2}, \dots, a_j)$$$, then there is an edge of weight $$$min(a_i, a_{i+1}, a_{i+2}, \dots, a_j)$$$ between $$$i$$$ and $$$j$$$.
- If $$$i+1=j$$$, then there is an edge of weight $$$p$$$ between $$$i$$$ and $$$j$$$.

Here $$$gcd(x, y, \ldots)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$, $$$y$$$, ....

Note that there could be multiple edges between $$$i$$$ and $$$j$$$ if both of the above conditions are true, and if both the conditions fail for $$$i$$$ and $$$j$$$, then there is no edge between these vertices.

The goal is to find the weight of the minimum spanning tree of this graph.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) and $$$p$$$ ($$$1 \leq p \leq 10^9$$$) — the number of nodes and the parameter $$$p$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

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

## Output Format
Output $$$t$$$ lines. For each test case print the weight of the corresponding graph.

## Examples
```input
4
2 5
10 10
2 5
3 3
4 5
5 2 4 9
8 8
5 3 3 6 10 100 9 15
```
```output
5
3
12
46
```

## Note
Here are the graphs for the four test cases of the example (the edges of a possible MST of the graphs are marked pink):

For test case 1

For test case 2

For test case 3

For test case 4

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
An array is called beautiful if all the elements in the array are equal.

You can transform an array using the following steps any number of times:

1. Choose two indices $$$i$$$ and $$$j$$$ ($$$1 \leq i,j \leq n$$$), and an integer $$$x$$$ ($$$1 \leq x \leq a_i$$$). Let $$$i$$$ be the source index and $$$j$$$ be the sink index.
2. Decrease the $$$i$$$-th element by $$$x$$$, and increase the $$$j$$$-th element by $$$x$$$. The resulting values at $$$i$$$-th and $$$j$$$-th index are $$$a_i-x$$$ and $$$a_j+x$$$ respectively.
3. The cost of this operation is $$$x \cdot |j-i| $$$.
4. Now the $$$i$$$-th index can no longer be the sink and the $$$j$$$-th index can no longer be the source.

For example, array $$$[0, 2, 3, 3]$$$ can be transformed into a beautiful array $$$[2, 2, 2, 2]$$$ with total cost $$$1 \cdot |1-3| + 1 \cdot |1-4| = 5$$$.

An array is called balanced, if it can be transformed into a beautiful array, and the cost of such transformation is uniquely defined. In other words, the minimum cost of transformation into a beautiful array equals the maximum cost.

You are given an array $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, consisting of non-negative integers. Your task is to find the number of balanced arrays which are permutations of the given array. Two arrays are considered different, if elements at some position differ. Since the answer can be large, output it modulo $$$10^9 + 7$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the size of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

## Output Format
Output a single integer — the number of balanced permutations modulo $$$10^9+7$$$.

## Examples
```input
3
1 2 3
```
```output
6
```
-----
```input
4
0 4 0 4
```
```output
2
```
-----
```input
5
0 11 12 13 14
```
```output
120
```

## Note
In the first example, $$$[1, 2, 3]$$$ is a valid permutation as we can consider the index with value $$$3$$$ as the source and index with value $$$1$$$ as the sink. Thus, after conversion we get a beautiful array $$$[2, 2, 2]$$$, and the total cost would be $$$2$$$. We can show that this is the only transformation of this array that leads to a beautiful array. Similarly, we can check for other permutations too.

In the second example, $$$[0, 0, 4, 4]$$$ and $$$[4, 4, 0, 0]$$$ are balanced permutations.

In the third example, all permutations are balanced.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given 2 arrays $$$a$$$ and $$$b$$$, both of size $$$n$$$. You can swap two elements in $$$b$$$ at most once (or leave it as it is), and you are required to minimize the value $$$$$$\sum_{i}|a_{i}-b_{i}|.$$$$$$

Find the minimum possible value of this sum.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le {10^9}$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le {10^9}$$$).

## Output Format
Output the minimum value of $$$\sum_{i}|a_{i}-b_{i}|$$$.

## Examples
```input
5
5 4 3 2 1
1 2 3 4 5
```
```output
4
```
-----
```input
2
1 3
4 2
```
```output
2
```

## Note
In the first example, we can swap the first and fifth element in array $$$b$$$, so that it becomes $$$[ 5, 2, 3, 4, 1 ]$$$.

Therefore, the minimum possible value of this sum would be $$$|5-5| + |4-2| + |3-3| + |2-4| + |1-1| = 4$$$.

In the second example, we can swap the first and second elements. So, our answer would be $$$2$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A number is called 2050-number if it is $$$2050$$$, $$$20500$$$, ..., ($$$2050 \cdot 10^k$$$ for integer $$$k \ge 0$$$).

Given a number $$$n$$$, you are asked to represent $$$n$$$ as the sum of some (not necessarily distinct) 2050-numbers. Compute the minimum number of 2050-numbers required for that.

## Input Format
The first line contains a single integer $$$T$$$ ($$$1\le T\leq 1\,000$$$) denoting the number of test cases.

The only line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 10^{18}$$$) denoting the number to be represented.

## Output Format
For each test case, output the minimum number of 2050-numbers in one line.

If $$$n$$$ cannot be represented as the sum of 2050-numbers, output $$$-1$$$ instead.

## Examples
```input
6
205
2050
4100
20500
22550
25308639900
```
```output
-1
1
2
1
2
36
```

## Note
In the third case, $$$4100 = 2050 + 2050$$$.

In the fifth case, $$$22550 = 20500 + 2050$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Fillomino is a classic logic puzzle. (You do not need to know Fillomino in order to solve this problem.) In one classroom in Yunqi town, some volunteers are playing a board game variant of it:

Consider an $$$n$$$ by $$$n$$$ chessboard. Its rows are numbered from $$$1$$$ to $$$n$$$ from the top to the bottom. Its columns are numbered from $$$1$$$ to $$$n$$$ from the left to the right. A cell on an intersection of $$$x$$$-th row and $$$y$$$-th column is denoted $$$(x, y)$$$. The main diagonal of the chessboard is cells $$$(x, x)$$$ for all $$$1 \le x \le n$$$.

A permutation of $$$\{1, 2, 3, \dots, n\}$$$ is written on the main diagonal of the chessboard. There is exactly one number written on each of the cells. The problem is to partition the cells under and on the main diagonal (there are exactly $$$1+2+ \ldots +n$$$ such cells) into $$$n$$$ connected regions satisfying the following constraints:

1. Every region should be connected. That means that we can move from any cell of a region to any other cell of the same region visiting only cells of the same region and moving from a cell to an adjacent cell.
2. The $$$x$$$-th region should contain cell on the main diagonal with number $$$x$$$ for all $$$1\le x\le n$$$.
3. The number of cells that belong to the $$$x$$$-th region should be equal to $$$x$$$ for all $$$1\le x\le n$$$.
4. Each cell under and on the main diagonal should belong to exactly one region.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1\le n \le 500$$$) denoting the size of the chessboard.

The second line contains $$$n$$$ integers $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$. $$$p_i$$$ is the number written on cell $$$(i, i)$$$. It is guaranteed that each integer from $$$\{1, \ldots, n\}$$$ appears exactly once in $$$p_1$$$, ..., $$$p_n$$$.

## Output Format
If no solution exists, output $$$-1$$$.

Otherwise, output $$$n$$$ lines. The $$$i$$$-th line should contain $$$i$$$ numbers. The $$$j$$$-th number on the $$$i$$$-th line should be $$$x$$$ if cell $$$(i, j)$$$ belongs to the the region with $$$x$$$ cells.

## Examples
```input
3
2 3 1
```
```output
2
2 3
3 3 1
```
-----
```input
5
1 2 3 4 5
```
```output
1
2 2
3 3 3
4 4 4 4
5 5 5 5 5
```

## Note
The solutions to the examples are illustrated in the following pictures:

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of $$$2n$$$ distinct integers. You want to arrange the elements of the array in a circle such that no element is equal to the the arithmetic mean of its $$$2$$$ neighbours.

More formally, find an array $$$b$$$, such that:

- $$$b$$$ is a permutation of $$$a$$$.
- For every $$$i$$$ from $$$1$$$ to $$$2n$$$, $$$b_i \neq \frac{b_{i-1}+b_{i+1}}{2}$$$, where $$$b_0 = b_{2n}$$$ and $$$b_{2n+1} = b_1$$$.

It can be proved that under the constraints of this problem, such array $$$b$$$ always exists.

## Input Format
The first line of input contains a single integer $$$t$$$ $$$(1 \leq t \leq 1000)$$$ — the number of testcases. The description of testcases follows.

The first line of each testcase contains a single integer $$$n$$$ $$$(1 \leq n \leq 25)$$$.

The second line of each testcase contains $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2n}$$$ $$$(1 \leq a_i \leq 10^9)$$$ — elements of the array.

Note that there is no limit to the sum of $$$n$$$ over all testcases.

## Output Format
For each testcase, you should output $$$2n$$$ integers, $$$b_1, b_2, \ldots b_{2n}$$$, for which the conditions from the statement are satisfied.

## Examples
```input
3
3
1 2 3 4 5 6
2
123 456 789 10
1
6 9
```
```output
3 1 4 2 5 6
123 10 456 789
9 6
```

## Note
In the first testcase, array $$$[3, 1, 4, 2, 5, 6]$$$ works, as it's a permutation of $$$[1, 2, 3, 4, 5, 6]$$$, and $$$\frac{3+4}{2}\neq 1$$$, $$$\frac{1+2}{2}\neq 4$$$, $$$\frac{4+5}{2}\neq 2$$$, $$$\frac{2+6}{2}\neq 5$$$, $$$\frac{5+3}{2}\neq 6$$$, $$$\frac{6+1}{2}\neq 3$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an integer $$$x$$$. Can you make $$$x$$$ by summing up some number of $$$11, 111, 1111, 11111, \ldots$$$? (You can use any number among them any number of times).

For instance,

- $$$33=11+11+11$$$
- $$$144=111+11+11+11$$$

## Input Format
The first line of input contains a single integer $$$t$$$ $$$(1 \leq t \leq 10000)$$$ — the number of testcases.

The first and only line of each testcase contains a single integer $$$x$$$ $$$(1 \leq x \leq 10^9)$$$ — the number you have to make.

## Output Format
For each testcase, you should output a single string. If you can make $$$x$$$, output "YES" (without quotes). Otherwise, output "NO".

You can print each letter of "YES" and "NO" in any case (upper or lower).

## Examples
```input
3
33
144
69
```
```output
YES
YES
NO
```

## Note
Ways to make $$$33$$$ and $$$144$$$ were presented in the statement. It can be proved that we can't present $$$69$$$ this way.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Once upon a time, Oolimry saw a suffix array. He wondered how many strings can produce this suffix array.

More formally, given a suffix array of length $$$n$$$ and having an alphabet size $$$k$$$, count the number of strings that produce such a suffix array.

Let $$$s$$$ be a string of length $$$n$$$. Then the $$$i$$$-th suffix of $$$s$$$ is the substring $$$s[i \ldots n-1]$$$. A suffix array is the array of integers that represent the starting indexes of all the suffixes of a given string, after the suffixes are sorted in the lexicographic order. For example, the suffix array of oolimry is $$$[3,2,4,1,0,5,6]$$$ as the array of sorted suffixes is $$$[\texttt{imry},\texttt{limry},\texttt{mry},\texttt{olimry},\texttt{oolimry},\texttt{ry},\texttt{y}]$$$.

A string $$$x$$$ is lexicographically smaller than string $$$y$$$, if either $$$x$$$ is a prefix of $$$y$$$ (and $$$x\neq y$$$), or there exists such $$$i$$$ that $$$x_i < y_i$$$, and for any $$$1\leq j < i$$$ , $$$x_j = y_j$$$.

## Input Format
The first line contain 2 integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 200000,1 \leq k \leq 200000$$$) — the length of the suffix array and the alphabet size respectively.

The second line contains $$$n$$$ integers $$$s_0, s_1, s_2, \ldots, s_{n-1}$$$ ($$$0 \leq s_i \leq n-1$$$) where $$$s_i$$$ is the $$$i$$$-th element of the suffix array i.e. the starting position of the $$$i$$$-th lexicographically smallest suffix. It is guaranteed that for all $$$0 \leq i< j \leq n-1$$$, $$$s_i \neq s_j$$$.

## Output Format
Print how many strings produce such a suffix array. Since the number can be very large, print the answer modulo $$$998244353$$$.

## Examples
```input
3 2
0 2 1
```
```output
1
```
-----
```input
5 1
0 1 2 3 4
```
```output
0
```
-----
```input
6 200000
0 1 2 3 4 5
```
```output
822243495
```
-----
```input
7 6
3 2 4 1 0 5 6
```
```output
36
```

## Note
In the first test case, "abb" is the only possible solution.

In the second test case, it can be easily shown no possible strings exist as all the letters have to be equal.

In the fourth test case, one possible string is "ddbacef".

Please remember to print your answers modulo $$$998244353$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Andi and Budi were given an assignment to tidy up their bookshelf of $$$n$$$ books. Each book is represented by the book title — a string $$$s_i$$$ numbered from $$$1$$$ to $$$n$$$, each with length $$$m$$$. Andi really wants to sort the book lexicographically ascending, while Budi wants to sort it lexicographically descending.

Settling their fight, they decided to combine their idea and sort it asc-desc-endingly, where the odd-indexed characters will be compared ascendingly, and the even-indexed characters will be compared descendingly.

A string $$$a$$$ occurs before a string $$$b$$$ in asc-desc-ending order if and only if in the first position where $$$a$$$ and $$$b$$$ differ, the following holds:

- if it is an odd position, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$;
- if it is an even position, the string $$$a$$$ has a letter that appears later in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \cdot m \leq 10^6$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains a string $$$s_i$$$ consisting of $$$m$$$ uppercase Latin letters — the book title. The strings are pairwise distinct.

## Output Format
Output $$$n$$$ integers — the indices of the strings after they are sorted asc-desc-endingly.

## Examples
```input
5 2
AA
AB
BB
BA
AZ
```
```output
5 2 1 3 4
```

## Note
The following illustrates the first example.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 5.0 seconds
Memory limit: 512.0 MB

# Problem
Mr. Chanek lives in a city represented as a plane. He wants to build an amusement park in the shape of a circle of radius $$$r$$$. The circle must touch the origin (point $$$(0, 0)$$$).

There are $$$n$$$ bird habitats that can be a photo spot for the tourists in the park. The $$$i$$$-th bird habitat is at point $$$p_i = (x_i, y_i)$$$.

Find the minimum radius $$$r$$$ of a park with at least $$$k$$$ bird habitats inside.

A point is considered to be inside the park if and only if the distance between $$$p_i$$$ and the center of the park is less than or equal to the radius of the park. Note that the center and the radius of the park do not need to be integers.

In this problem, it is guaranteed that the given input always has a solution with $$$r \leq 2 \cdot 10^5$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq n$$$) — the number of bird habitats in the city and the number of bird habitats required to be inside the park.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \leq |x_i|, |y_i| \leq 10^5$$$) — the position of the $$$i$$$-th bird habitat.

## Output Format
Output a single real number $$$r$$$ denoting the minimum radius of a park with at least $$$k$$$ bird habitats inside. It is guaranteed that the given input always has a solution with $$$r \leq 2 \cdot 10^5$$$.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-4}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$.

## Examples
```input
8 4
-3 1
-4 4
1 5
2 2
2 -2
-2 -4
-1 -1
-6 0
```
```output
3.1622776589
```
-----
```input
1 1
0 0
```
```output
0.0000000000
```

## Note
In the first example, Mr. Chanek can put the center of the park at $$$(-3, -1)$$$ with radius $$$\sqrt{10} \approx 3.162$$$. It can be proven this is the minimum $$$r$$$.

The following illustrates the first example. The blue points represent bird habitats and the red circle represents the amusement park.

Now solve the problem and return the code.