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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Let $$$p$$$ be any permutation of length $$$n$$$. We define the fingerprint $$$F(p)$$$ of $$$p$$$ as the sorted array of sums of adjacent elements in $$$p$$$. More formally,

$$$$$$F(p)=\mathrm{sort}([p_1+p_2,p_2+p_3,\ldots,p_{n-1}+p_n]).$$$$$$

For example, if $$$n=4$$$ and $$$p=[1,4,2,3],$$$ then the fingerprint is given by $$$F(p)=\mathrm{sort}([1+4,4+2,2+3])=\mathrm{sort}([5,6,5])=[5,5,6]$$$.

You are given a permutation $$$p$$$ of length $$$n$$$. Your task is to find a different permutation $$$p'$$$ with the same fingerprint. Two permutations $$$p$$$ and $$$p'$$$ are considered different if there is some index $$$i$$$ such that $$$p_i \ne p'_i$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 668$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\le n\le 100$$$)  — the length of the permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1,\ldots,p_n$$$ ($$$1\le p_i\le n$$$). It is guaranteed that $$$p$$$ is a permutation.

## Output Format
For each test case, output $$$n$$$ integers $$$p'_1,\ldots, p'_n$$$ — a permutation such that $$$p'\ne p$$$ and $$$F(p')=F(p)$$$.

We can prove that for every permutation satisfying the input constraints, a solution exists.

If there are multiple solutions, you may output any.

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

## Note
In the first test case, $$$F(p)=\mathrm{sort}([1+2])=[3]$$$.

And $$$F(p')=\mathrm{sort}([2+1])=[3]$$$.

In the second test case, $$$F(p)=\mathrm{sort}([2+1,1+6,6+5,5+4,4+3])=\mathrm{sort}([3,7,11,9,7])=[3,7,7,9,11]$$$.

And $$$F(p')=\mathrm{sort}([1+2,2+5,5+6,6+3,3+4])=\mathrm{sort}([3,7,11,9,7])=[3,7,7,9,11]$$$.

In the third test case, $$$F(p)=\mathrm{sort}([2+4,4+3,3+1,1+5])=\mathrm{sort}([6,7,4,6])=[4,6,6,7]$$$.

And $$$F(p')=\mathrm{sort}([3+1,1+5,5+2,2+4])=\mathrm{sort}([4,6,7,6])=[4,6,6,7]$$$.

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're given an array $$$a$$$ of $$$n$$$ integers, such that $$$a_1 + a_2 + \cdots + a_n = 0$$$.

In one operation, you can choose two different indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$), decrement $$$a_i$$$ by one and increment $$$a_j$$$ by one. If $$$i < j$$$ this operation is free, otherwise it costs one coin.

How many coins do you have to spend in order to make all elements equal to $$$0$$$?

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5000$$$). Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$)  — the number of elements.

The next line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$). It is given that $$$\sum_{i=1}^n a_i = 0$$$.

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

## Output Format
For each test case, print the minimum number of coins we have to spend in order to make all elements equal to $$$0$$$.

## Examples
```input
7
4
-3 5 -3 1
2
1 -1
4
-3 2 -3 4
4
-1 1 1 -1
7
-5 7 -6 -4 17 -13 4
6
-1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000
1
0
```
```output
3
0
4
1
8
3000000000
0
```

## Note
Possible strategy for the first test case:

- Do $$$(i=2, j=3)$$$ three times (free), $$$a = [-3, 2, 0, 1]$$$.
- Do $$$(i=2, j=1)$$$ two times (pay two coins), $$$a = [-1, 0, 0, 1]$$$.
- Do $$$(i=4, j=1)$$$ one time (pay one coin), $$$a = [0, 0, 0, 0]$$$.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Yura is tasked to build a closed fence in shape of an arbitrary non-degenerate simple quadrilateral. He's already got three straight fence segments with known lengths $$$a$$$, $$$b$$$, and $$$c$$$. Now he needs to find out some possible integer length $$$d$$$ of the fourth straight fence segment so that he can build the fence using these four segments. In other words, the fence should have a quadrilateral shape with side lengths equal to $$$a$$$, $$$b$$$, $$$c$$$, and $$$d$$$. Help Yura, find any possible length of the fourth side.

A non-degenerate simple quadrilateral is such a quadrilateral that no three of its corners lie on the same line, and it does not cross itself.

## Input Format
The first line contains a single integer $$$t$$$ — the number of test cases ($$$1 \le t \le 1000$$$). The next $$$t$$$ lines describe the test cases.

Each line contains three integers $$$a$$$, $$$b$$$, and $$$c$$$ — the lengths of the three fence segments ($$$1 \le a, b, c \le 10^9$$$).

## Output Format
For each test case print a single integer $$$d$$$ — the length of the fourth fence segment that is suitable for building the fence. If there are multiple answers, print any. We can show that an answer always exists.

## Examples
```input
2
1 2 3
12 34 56
```
```output
4
42
```

## Note
We can build a quadrilateral with sides $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$.

We can build a quadrilateral with sides $$$12$$$, $$$34$$$, $$$56$$$, $$$42$$$.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A matrix of size $$$n \times m$$$ is called nice, if all rows and columns of the matrix are palindromes. A sequence of integers $$$(a_1, a_2, \dots , a_k)$$$ is a palindrome, if for any integer $$$i$$$ ($$$1 \le i \le k$$$) the equality $$$a_i = a_{k - i + 1}$$$ holds.

Sasha owns a matrix $$$a$$$ of size $$$n \times m$$$. In one operation he can increase or decrease any number in the matrix by one. Sasha wants to make the matrix nice. He is interested what is the minimum number of operations he needs.

Help him!

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

The first line of each test contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 100$$$) — the size of the matrix.

Each of the next $$$n$$$ lines contains $$$m$$$ integers $$$a_{i, j}$$$ ($$$0 \le a_{i, j} \le 10^9$$$) — the elements of the matrix.

## Output Format
For each test output the smallest number of operations required to make the matrix nice.

## Examples
```input
2
4 2
4 2
2 4
4 2
2 4
3 4
1 2 3 4
5 6 7 8
9 10 11 18
```
```output
8
42
```

## Note
In the first test case we can, for example, obtain the following nice matrix in $$$8$$$ operations:

In the second test case we can, for example, obtain the following nice matrix in $$$42$$$ operations:

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Sometimes it is not easy to come to an agreement in a bargain. Right now Sasha and Vova can't come to an agreement: Sasha names a price as high as possible, then Vova wants to remove as many digits from the price as possible. In more details, Sasha names some integer price $$$n$$$, Vova removes a non-empty substring of (consecutive) digits from the price, the remaining digits close the gap, and the resulting integer is the price.

For example, is Sasha names $$$1213121$$$, Vova can remove the substring $$$1312$$$, and the result is $$$121$$$.

It is allowed for result to contain leading zeros. If Vova removes all digits, the price is considered to be $$$0$$$.

Sasha wants to come up with some constraints so that Vova can't just remove all digits, but he needs some arguments supporting the constraints. To start with, he wants to compute the sum of all possible resulting prices after Vova's move.

Help Sasha to compute this sum. Since the answer can be very large, print it modulo $$$10^9 + 7$$$.

## Input Format
The first and only line contains a single integer $$$n$$$ ($$$1 \le n < 10^{10^5}$$$).

## Output Format
In the only line print the required sum modulo $$$10^9 + 7$$$.

## Examples
```input
107
```
```output
42
```
-----
```input
100500100500
```
```output
428101984
```

## Note
Consider the first example.

Vova can choose to remove $$$1$$$, $$$0$$$, $$$7$$$, $$$10$$$, $$$07$$$, or $$$107$$$. The results are $$$07$$$, $$$17$$$, $$$10$$$, $$$7$$$, $$$1$$$, $$$0$$$. Their sum is $$$42$$$.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Yura has been walking for some time already and is planning to return home. He needs to get home as fast as possible. To do this, Yura can use the instant-movement locations around the city.

Let's represent the city as an area of $$$n \times n$$$ square blocks. Yura needs to move from the block with coordinates $$$(s_x,s_y)$$$ to the block with coordinates $$$(f_x,f_y)$$$. In one minute Yura can move to any neighboring by side block; in other words, he can move in four directions. Also, there are $$$m$$$ instant-movement locations in the city. Their coordinates are known to you and Yura. Yura can move to an instant-movement location in no time if he is located in a block with the same coordinate $$$x$$$ or with the same coordinate $$$y$$$ as the location.

Help Yura to find the smallest time needed to get home.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ — the size of the city and the number of instant-movement locations ($$$1 \le n \le 10^9$$$, $$$0 \le m \le 10^5$$$).

The next line contains four integers $$$s_x$$$ $$$s_y$$$ $$$f_x$$$ $$$f_y$$$ — the coordinates of Yura's initial position and the coordinates of his home ($$$ 1 \le s_x, s_y, f_x, f_y \le n$$$).

Each of the next $$$m$$$ lines contains two integers $$$x_i$$$ $$$y_i$$$ — coordinates of the $$$i$$$-th instant-movement location ($$$1 \le x_i, y_i \le n$$$).

## Output Format
In the only line print the minimum time required to get home.

## Examples
```input
5 3
1 1 5 5
1 2
4 1
3 3
```
```output
5
```
-----
```input
84 5
67 59 41 2
39 56
7 2
15 3
74 18
22 7
```
```output
42
```

## Note
In the first example Yura needs to reach $$$(5, 5)$$$ from $$$(1, 1)$$$. He can do that in $$$5$$$ minutes by first using the second instant-movement location (because its $$$y$$$ coordinate is equal to Yura's $$$y$$$ coordinate), and then walking $$$(4, 1) \to (4, 2) \to (4, 3) \to (5, 3) \to (5, 4) \to (5, 5)$$$.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Some time ago Lesha found an entertaining string $$$s$$$ consisting of lowercase English letters. Lesha immediately developed an unique algorithm for this string and shared it with you. The algorithm is as follows.

Lesha chooses an arbitrary (possibly zero) number of pairs on positions $$$(i, i + 1)$$$ in such a way that the following conditions are satisfied:

- for each pair $$$(i, i + 1)$$$ the inequality $$$0 \le i < |s| - 1$$$ holds;
- for each pair $$$(i, i + 1)$$$ the equality $$$s_i = s_{i + 1}$$$ holds;
- there is no index that is contained in more than one pair.

Lesha is interested in the lexicographically smallest strings he can obtain by applying the algorithm to the suffixes of the given string.

## Input Format
The only line contains the string $$$s$$$ ($$$1 \le |s| \le 10^5$$$) — the initial string consisting of lowercase English letters only.

## Output Format
In $$$|s|$$$ lines print the lengths of the answers and the answers themselves, starting with the answer for the longest suffix. The output can be large, so, when some answer is longer than $$$10$$$ characters, instead print the first $$$5$$$ characters, then "...", then the last $$$2$$$ characters of the answer.

## Examples
```input
abcdd
```
```output
3 abc
2 bc
1 c
0 
1 d
```
-----
```input
abbcdddeaaffdfouurtytwoo
```
```output
18 abbcd...tw
17 bbcdd...tw
16 bcddd...tw
15 cddde...tw
14 dddea...tw
13 ddeaa...tw
12 deaad...tw
11 eaadf...tw
10 aadfortytw
9 adfortytw
8 dfortytw
9 fdfortytw
8 dfortytw
7 fortytw
6 ortytw
5 rtytw
6 urtytw
5 rtytw
4 tytw
3 ytw
2 tw
1 w
0 
1 o
```

## Note
Consider the first example.

- The longest suffix is the whole string "abcdd". Choosing one pair $$$(4, 5)$$$, Lesha obtains "abc".
- The next longest suffix is "bcdd". Choosing one pair $$$(3, 4)$$$, we obtain "bc".
- The next longest suffix is "cdd". Choosing one pair $$$(2, 3)$$$, we obtain "c".
- The next longest suffix is "dd". Choosing one pair $$$(1, 2)$$$, we obtain "" (an empty string).
- The last suffix is the string "d". No pair can be chosen, so the answer is "d".

In the second example, for the longest suffix "abbcdddeaaffdfouurtytwoo" choose three pairs $$$(11, 12)$$$, $$$(16, 17)$$$, $$$(23, 24)$$$ and we obtain "abbcdddeaadfortytw"

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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Shikamaru and Asuma like to play different games, and sometimes they play the following: given an increasing list of numbers, they take turns to move. Each move consists of picking a number from the list.

Assume the picked numbers are $$$v_{i_1}$$$, $$$v_{i_2}$$$, $$$\ldots$$$, $$$v_{i_k}$$$. The following conditions must hold:

- $$$i_{j} < i_{j+1}$$$ for all $$$1 \leq j \leq k-1$$$;
- $$$v_{i_{j+1}} - v_{i_j} < v_{i_{j+2}} - v_{i_{j+1}}$$$ for all $$$1 \leq j \leq k-2$$$.

However, it's easy to play only one instance of game, so today Shikamaru and Asuma decided to play $$$n$$$ simultaneous games. They agreed on taking turns as for just one game, Shikamaru goes first. At each turn, the player performs a valid move in any single game. The player who cannot move loses. Find out who wins, provided that both play optimally.

## Input Format
The first line contains the only integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) standing for the number of games Shikamaru and Asuma play at once. Next lines describe the games.

Each description starts from a line with the only number $$$m$$$ ($$$m\geq 1$$$) denoting the length of the number list. The second line contains the increasing space-separated sequence $$$v_1$$$, $$$v_2$$$, ..., $$$v_m$$$ from the game ($$$1 \leq v_{1} < v_{2} < ... < v_{m} \leq 10^{5}$$$).

The total length of all sequences doesn't exceed $$$10^5$$$.

## Output Format
Print "YES" if Shikamaru can secure the victory, and "NO" otherwise.

## Examples
```input
1
10
1 2 3 4 5 6 7 8 9 10
```
```output
YES
```
-----
```input
2
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
```
```output
NO
```
-----
```input
4
7
14404 32906 41661 47694 51605 75933 80826
5
25374 42550 60164 62649 86273
2
7002 36731
8
23305 45601 46404 47346 47675 58125 74092 87225
```
```output
NO
```

## Note
In the first example Shikamaru can pick the last number, and Asuma cannot do anything because of the first constraint.

In the second sample test Asuma can follow the symmetric strategy, repeating Shikamaru's moves in the other instance each time, and therefore win.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given four integers $$$n$$$, $$$c_0$$$, $$$c_1$$$ and $$$h$$$ and a binary string $$$s$$$ of length $$$n$$$.

A binary string is a string consisting of characters $$$0$$$ and $$$1$$$.

You can change any character of the string $$$s$$$ (the string should be still binary after the change). You should pay $$$h$$$ coins for each change.

After some changes (possibly zero) you want to buy the string. To buy the string you should buy all its characters. To buy the character $$$0$$$ you should pay $$$c_0$$$ coins, to buy the character $$$1$$$ you should pay $$$c_1$$$ coins.

Find the minimum number of coins needed to buy the string.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10$$$) — the number of test cases. Next $$$2t$$$ lines contain descriptions of test cases.

The first line of the description of each test case contains four integers $$$n$$$, $$$c_{0}$$$, $$$c_{1}$$$, $$$h$$$ ($$$1 \leq n, c_{0}, c_{1}, h \leq 1000$$$).

The second line of the description of each test case contains the binary string $$$s$$$ of length $$$n$$$.

## Output Format
For each test case print a single integer — the minimum number of coins needed to buy the string.

## Examples
```input
6
3 1 1 1
100
5 10 100 1
01010
5 10 1 1
11111
5 1 10 1
11111
12 2 1 10
101110110101
2 100 1 10
00
```
```output
3
52
5
10
16
22
```

## Note
In the first test case, you can buy all characters and pay $$$3$$$ coins, because both characters $$$0$$$ and $$$1$$$ costs $$$1$$$ coin.

In the second test case, you can firstly change $$$2$$$-nd and $$$4$$$-th symbols of the string from $$$1$$$ to $$$0$$$ and pay $$$2$$$ coins for that. Your string will be $$$00000$$$. After that, you can buy the string and pay $$$5 \cdot 10 = 50$$$ coins for that. The total number of coins paid will be $$$2 + 50 = 52$$$.

Now solve the problem and return the code.