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 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
The USA Construction Operation (USACO) recently ordered Farmer John to arrange a row of $$$n$$$ haybale piles on the farm. The $$$i$$$-th pile contains $$$a_i$$$ haybales.

However, Farmer John has just left for vacation, leaving Bessie all on her own. Every day, Bessie the naughty cow can choose to move one haybale in any pile to an adjacent pile. Formally, in one day she can choose any two indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$) such that $$$|i-j|=1$$$ and $$$a_i>0$$$ and apply $$$a_i = a_i - 1$$$, $$$a_j = a_j + 1$$$. She may also decide to not do anything on some days because she is lazy.

Bessie wants to maximize the number of haybales in pile $$$1$$$ (i.e. to maximize $$$a_1$$$), and she only has $$$d$$$ days to do so before Farmer John returns. Help her find the maximum number of haybales that may be in pile $$$1$$$ if she acts optimally!

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$)  — the number of test cases. Next $$$2t$$$ lines contain a description of test cases  — two lines per test case.

The first line of each test case contains integers $$$n$$$ and $$$d$$$ ($$$1 \le n,d \le 100$$$) — the number of haybale piles and the number of days, respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 100$$$)  — the number of haybales in each pile.

## Output Format
For each test case, output one integer: the maximum number of haybales that may be in pile $$$1$$$ after $$$d$$$ days if Bessie acts optimally.

## Examples
```input
3
4 5
1 0 3 2
2 2
100 1
1 8
0
```
```output
3
101
0
```

## Note
In the first test case of the sample, this is one possible way Bessie can end up with $$$3$$$ haybales in pile $$$1$$$:

- On day one, move a haybale from pile $$$3$$$ to pile $$$2$$$
- On day two, move a haybale from pile $$$3$$$ to pile $$$2$$$
- On day three, move a haybale from pile $$$2$$$ to pile $$$1$$$
- On day four, move a haybale from pile $$$2$$$ to pile $$$1$$$
- On day five, do nothing

In the second test case of the sample, Bessie can do nothing on the first day and move a haybale from pile $$$2$$$ to pile $$$1$$$ on the second day.

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
Bessie the cow has just intercepted a text that Farmer John sent to Burger Queen! However, Bessie is sure that there is a secret message hidden inside.

The text is a string $$$s$$$ of lowercase Latin letters. She considers a string $$$t$$$ as hidden in string $$$s$$$ if $$$t$$$ exists as a subsequence of $$$s$$$ whose indices form an arithmetic progression. For example, the string aab is hidden in string aaabb because it occurs at indices $$$1$$$, $$$3$$$, and $$$5$$$, which form an arithmetic progression with a common difference of $$$2$$$. Bessie thinks that any hidden string that occurs the most times is the secret message. Two occurrences of a subsequence of $$$S$$$ are distinct if the sets of indices are different. Help her find the number of occurrences of the secret message!

For example, in the string aaabb, a is hidden $$$3$$$ times, b is hidden $$$2$$$ times, ab is hidden $$$6$$$ times, aa is hidden $$$3$$$ times, bb is hidden $$$1$$$ time, aab is hidden $$$2$$$ times, aaa is hidden $$$1$$$ time, abb is hidden $$$1$$$ time, aaab is hidden $$$1$$$ time, aabb is hidden $$$1$$$ time, and aaabb is hidden $$$1$$$ time. The number of occurrences of the secret message is $$$6$$$.

## Input Format
The first line contains a string $$$s$$$ of lowercase Latin letters ($$$1 \le |s| \le 10^5$$$) — the text that Bessie intercepted.

## Output Format
Output a single integer  — the number of occurrences of the secret message.

## Examples
```input
aaabb
```
```output
6
```
-----
```input
usaco
```
```output
1
```
-----
```input
lol
```
```output
2
```

## Note
In the first example, these are all the hidden strings and their indice sets:

- a occurs at $$$(1)$$$, $$$(2)$$$, $$$(3)$$$
- b occurs at $$$(4)$$$, $$$(5)$$$
- ab occurs at $$$(1,4)$$$, $$$(1,5)$$$, $$$(2,4)$$$, $$$(2,5)$$$, $$$(3,4)$$$, $$$(3,5)$$$
- aa occurs at $$$(1,2)$$$, $$$(1,3)$$$, $$$(2,3)$$$
- bb occurs at $$$(4,5)$$$
- aab occurs at $$$(1,3,5)$$$, $$$(2,3,4)$$$
- aaa occurs at $$$(1,2,3)$$$
- abb occurs at $$$(3,4,5)$$$
- aaab occurs at $$$(1,2,3,4)$$$
- aabb occurs at $$$(2,3,4,5)$$$
- aaabb occurs at $$$(1,2,3,4,5)$$$

In the second example, no hidden string occurs more than once.

In the third example, the hidden string is the letter l.

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
Bessie is out grazing on the farm, which consists of $$$n$$$ fields connected by $$$m$$$ bidirectional roads. She is currently at field $$$1$$$, and will return to her home at field $$$n$$$ at the end of the day.

The Cowfederation of Barns has ordered Farmer John to install one extra bidirectional road. The farm has $$$k$$$ special fields and he has decided to install the road between two different special fields. He may add the road between two special fields that already had a road directly connecting them.

After the road is added, Bessie will return home on the shortest path from field $$$1$$$ to field $$$n$$$. Since Bessie needs more exercise, Farmer John must maximize the length of this shortest path. Help him!

## Input Format
The first line contains integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n-1 \le m \le 2 \cdot 10^5$$$, $$$2 \le k \le n$$$)  — the number of fields on the farm, the number of roads, and the number of special fields.

The second line contains $$$k$$$ integers $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \le a_i \le n$$$)  — the special fields. All $$$a_i$$$ are distinct.

The $$$i$$$-th of the following $$$m$$$ lines contains integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$), representing a bidirectional road between fields $$$x_i$$$ and $$$y_i$$$.

It is guaranteed that one can reach any field from every other field. It is also guaranteed that for any pair of fields there is at most one road connecting them.

## Output Format
Output one integer, the maximum possible length of the shortest path from field $$$1$$$ to $$$n$$$ after Farmer John installs one road optimally.

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

## Note
The graph for the first example is shown below. The special fields are denoted by red. It is optimal for Farmer John to add a road between fields $$$3$$$ and $$$5$$$, and the resulting shortest path from $$$1$$$ to $$$5$$$ is length $$$3$$$.

The graph for the second example is shown below. Farmer John must add a road between fields $$$2$$$ and $$$4$$$, and the resulting shortest path from $$$1$$$ to $$$5$$$ is length $$$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 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
Bessie is planning a vacation! In Cow-lifornia, there are $$$n$$$ cities, with $$$n-1$$$ bidirectional roads connecting them. It is guaranteed that one can reach any city from any other city.

Bessie is considering $$$v$$$ possible vacation plans, with the $$$i$$$-th one consisting of a start city $$$a_i$$$ and destination city $$$b_i$$$.

It is known that only $$$r$$$ of the cities have rest stops. Bessie gets tired easily, and cannot travel across more than $$$k$$$ consecutive roads without resting. In fact, she is so desperate to rest that she may travel through the same city multiple times in order to do so.

For each of the vacation plans, does there exist a way for Bessie to travel from the starting city to the destination city?

## Input Format
The first line contains three integers $$$n$$$, $$$k$$$, and $$$r$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k,r \le n$$$)  — the number of cities, the maximum number of roads Bessie is willing to travel through in a row without resting, and the number of rest stops.

Each of the following $$$n-1$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \neq y_i$$$), meaning city $$$x_i$$$ and city $$$y_i$$$ are connected by a road.

The next line contains $$$r$$$ integers separated by spaces  — the cities with rest stops. Each city will appear at most once.

The next line contains $$$v$$$ ($$$1 \le v \le 2 \cdot 10^5$$$)  — the number of vacation plans.

Each of the following $$$v$$$ lines contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$)  — the start and end city of the vacation plan.

## Output Format
If Bessie can reach her destination without traveling across more than $$$k$$$ roads without resting for the $$$i$$$-th vacation plan, print YES. Otherwise, print NO.

## Examples
```input
6 2 1
1 2
2 3
2 4
4 5
5 6
2
3
1 3
3 5
3 6
```
```output
YES
YES
NO
```
-----
```input
8 3 3
1 2
2 3
3 4
4 5
4 6
6 7
7 8
2 5 8
2
7 1
8 1
```
```output
YES
NO
```

## Note
The graph for the first example is shown below. The rest stop is denoted by red.

For the first query, Bessie can visit these cities in order: $$$1, 2, 3$$$.

For the second query, Bessie can visit these cities in order: $$$3, 2, 4, 5$$$.

For the third query, Bessie cannot travel to her destination. For example, if she attempts to travel this way: $$$3, 2, 4, 5, 6$$$, she travels on more than $$$2$$$ roads without resting.

The graph for the second example is shown below.

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
Farmer John is obsessed with making Bessie exercise more!

Bessie is out grazing on the farm, which consists of $$$n$$$ fields connected by $$$m$$$ directed roads. Each road takes some time $$$w_i$$$ to cross. She is currently at field $$$1$$$ and will return to her home at field $$$n$$$ at the end of the day.

Farmer John has plans to increase the time it takes to cross certain roads. He can increase the time it takes to cross each road by a nonnegative amount, but the total increase cannot exceed $$$x_i$$$ for the $$$i$$$-th plan.

Determine the maximum he can make the shortest path from $$$1$$$ to $$$n$$$ for each of the $$$q$$$ independent plans.

## Input Format
The first line contains integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 50$$$, $$$1 \le m \le n \cdot (n-1)$$$) — the number of fields and number of roads, respectively.

Each of the following $$$m$$$ lines contains $$$3$$$ integers, $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w_i \le 10^6$$$), meaning there is an road from field $$$u_i$$$ to field $$$v_i$$$ that takes $$$w_i$$$ time to cross.

It is guaranteed that there exists a way to get to field $$$n$$$ from field $$$1$$$. It is guaranteed that the graph does not contain self-loops or parallel edges. It is possible to have a road from $$$u$$$ to $$$v$$$ and a road from $$$v$$$ to $$$u$$$.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$), the number of plans.

Each of the following $$$q$$$ lines contains a single integer $$$x_i$$$, the query ($$$0 \le x_i \le 10^5$$$).

## Output Format
For each query, output the maximum Farmer John can make the shortest path if the total increase does not exceed $$$x_i$$$.

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

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^{-6}$$$.

## Examples
```input
3 3
1 2 2
2 3 2
1 3 3
5
0
1
2
3
4
```
```output
3.0000000000
4.0000000000
4.5000000000
5.0000000000
5.5000000000
```

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
You are given an array $$$a$$$ of length $$$n$$$.

You are also given a set of distinct positions $$$p_1, p_2, \dots, p_m$$$, where $$$1 \le p_i < n$$$. The position $$$p_i$$$ means that you can swap elements $$$a[p_i]$$$ and $$$a[p_i + 1]$$$. You can apply this operation any number of times for each of the given positions.

Your task is to determine if it is possible to sort the initial array in non-decreasing order ($$$a_1 \le a_2 \le \dots \le a_n$$$) using only allowed swaps.

For example, if $$$a = [3, 2, 1]$$$ and $$$p = [1, 2]$$$, then we can first swap elements $$$a[2]$$$ and $$$a[3]$$$ (because position $$$2$$$ is contained in the given set $$$p$$$). We get the array $$$a = [3, 1, 2]$$$. Then we swap $$$a[1]$$$ and $$$a[2]$$$ (position $$$1$$$ is also contained in $$$p$$$). We get the array $$$a = [1, 3, 2]$$$. Finally, we swap $$$a[2]$$$ and $$$a[3]$$$ again and get the array $$$a = [1, 2, 3]$$$, sorted in non-decreasing order.

You can see that if $$$a = [4, 1, 2, 3]$$$ and $$$p = [3, 2]$$$ then you cannot sort the array.

You have to answer $$$t$$$ independent test cases.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

Then $$$t$$$ test cases follow. The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m < n \le 100$$$) — the number of elements in $$$a$$$ and the number of elements in $$$p$$$. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$). The third line of the test case contains $$$m$$$ integers $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i < n$$$, all $$$p_i$$$ are distinct) — the set of positions described in the problem statement.

## Output Format
For each test case, print the answer — "YES" (without quotes) if you can sort the initial array in non-decreasing order ($$$a_1 \le a_2 \le \dots \le a_n$$$) using only allowed swaps. Otherwise, print "NO".

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

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
You are given three integers $$$a \le b \le c$$$.

In one move, you can add $$$+1$$$ or $$$-1$$$ to any of these integers (i.e. increase or decrease any number by one). You can perform such operation any (possibly, zero) number of times, you can even perform this operation several times with one number. Note that you cannot make non-positive numbers using such operations.

You have to perform the minimum number of such operations in order to obtain three integers $$$A \le B \le C$$$ such that $$$B$$$ is divisible by $$$A$$$ and $$$C$$$ is divisible by $$$B$$$.

You have to answer $$$t$$$ independent test cases.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The next $$$t$$$ lines describe test cases. Each test case is given on a separate line as three space-separated integers $$$a, b$$$ and $$$c$$$ ($$$1 \le a \le b \le c \le 10^4$$$).

## Output Format
For each test case, print the answer. In the first line print $$$res$$$ — the minimum number of operations you have to perform to obtain three integers $$$A \le B \le C$$$ such that $$$B$$$ is divisible by $$$A$$$ and $$$C$$$ is divisible by $$$B$$$. On the second line print any suitable triple $$$A, B$$$ and $$$C$$$.

## Examples
```input
8
1 2 3
123 321 456
5 10 15
15 18 21
100 100 101
1 22 29
3 19 38
6 30 46
```
```output
1
1 1 3
102
114 228 456
4
4 8 16
6
18 18 18
1
100 100 100
7
1 22 22
2
1 19 38
8
6 24 48
```

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
There are $$$n$$$ points on a coordinate axis $$$OX$$$. The $$$i$$$-th point is located at the integer point $$$x_i$$$ and has a speed $$$v_i$$$. It is guaranteed that no two points occupy the same coordinate. All $$$n$$$ points move with the constant speed, the coordinate of the $$$i$$$-th point at the moment $$$t$$$ ($$$t$$$ can be non-integer) is calculated as $$$x_i + t \cdot v_i$$$.

Consider two points $$$i$$$ and $$$j$$$. Let $$$d(i, j)$$$ be the minimum possible distance between these two points over any possible moments of time (even non-integer). It means that if two points $$$i$$$ and $$$j$$$ coincide at some moment, the value $$$d(i, j)$$$ will be $$$0$$$.

Your task is to calculate the value $$$\sum\limits_{1 \le i < j \le n}$$$ $$$d(i, j)$$$ (the sum of minimum distances over all pairs of points).

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of points.

The second line of the input contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le 10^8$$$), where $$$x_i$$$ is the initial coordinate of the $$$i$$$-th point. It is guaranteed that all $$$x_i$$$ are distinct.

The third line of the input contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$-10^8 \le v_i \le 10^8$$$), where $$$v_i$$$ is the speed of the $$$i$$$-th point.

## Output Format
Print one integer — the value $$$\sum\limits_{1 \le i < j \le n}$$$ $$$d(i, j)$$$ (the sum of minimum distances over all pairs of points).

## Examples
```input
3
1 3 2
-100 2 3
```
```output
3
```
-----
```input
5
2 1 4 3 5
2 2 2 3 4
```
```output
19
```
-----
```input
2
2 1
-3 0
```
```output
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Shakespeare is a widely known esoteric programming language in which programs look like plays by Shakespeare, and numbers are given by combinations of ornate epithets. In this problem we will have a closer look at the way the numbers are described in Shakespeare.

Each constant in Shakespeare is created from non-negative powers of 2 using arithmetic operations. For simplicity we'll allow only addition and subtraction and will look for a representation of the given number which requires a minimal number of operations.

You are given an integer n. You have to represent it as n = a1 + a2 + ... + am, where each of ai is a non-negative power of 2, possibly multiplied by -1. Find a representation which minimizes the value of m.

## Input Format
The only line of input contains a positive integer n, written as its binary notation. The length of the notation is at most 106. The first digit of the notation is guaranteed to be 1.

## Output Format
Output the required minimal m. After it output m lines. Each line has to be formatted as "+2^x" or "-2^x", where x is the power coefficient of the corresponding term. The order of the lines doesn't matter.

## Examples
```input
1111
```
```output
2
+2^4
-2^0
```
-----
```input
1010011
```
```output
4
+2^0
+2^1
+2^4
+2^6
```

Now solve the problem and return the code.