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 a string $$$s$$$. You can build new string $$$p$$$ from $$$s$$$ using the following operation no more than two times:

1. choose any subsequence $$$s_{i_1}, s_{i_2}, \dots, s_{i_k}$$$ where $$$1 \le i_1 < i_2 < \dots < i_k \le |s|$$$;
2. erase the chosen subsequence from $$$s$$$ ($$$s$$$ can become empty);
3. concatenate chosen subsequence to the right of the string $$$p$$$ (in other words, $$$p = p + s_{i_1}s_{i_2}\dots s_{i_k}$$$).

Of course, initially the string $$$p$$$ is empty.

For example, let $$$s = \text{ababcd}$$$. At first, let's choose subsequence $$$s_1 s_4 s_5 = \text{abc}$$$ — we will get $$$s = \text{bad}$$$ and $$$p = \text{abc}$$$. At second, let's choose $$$s_1 s_2 = \text{ba}$$$ — we will get $$$s = \text{d}$$$ and $$$p = \text{abcba}$$$. So we can build $$$\text{abcba}$$$ from $$$\text{ababcd}$$$.

Can you build a given string $$$t$$$ using the algorithm above?

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

Next $$$2T$$$ lines contain test cases — two per test case. The first line contains string $$$s$$$ consisting of lowercase Latin letters ($$$1 \le |s| \le 400$$$) — the initial string.

The second line contains string $$$t$$$ consisting of lowercase Latin letters ($$$1 \le |t| \le |s|$$$) — the string you'd like to build.

It's guaranteed that the total length of strings $$$s$$$ doesn't exceed $$$400$$$.

## Output Format
Print $$$T$$$ answers — one per test case. Print YES (case insensitive) if it's possible to build $$$t$$$ and NO (case insensitive) otherwise.

## Examples
```input
4
ababcd
abcba
a
b
defi
fed
xyz
x
```
```output
YES
NO
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 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: 6.0 seconds
Memory limit: 512.0 MB

# Problem
We define the sum of prefix sums of an array $$$[s_1, s_2, \dots, s_k]$$$ as $$$s_1 + (s_1 + s_2) + (s_1 + s_2 + s_3) + \dots + (s_1 + s_2 + \dots + s_k)$$$.

You are given a tree consisting of $$$n$$$ vertices. Each vertex $$$i$$$ has an integer $$$a_i$$$ written on it. We define the value of the simple path from vertex $$$u$$$ to vertex $$$v$$$ as follows: consider all vertices appearing on the path from $$$u$$$ to $$$v$$$, write down all the numbers written on these vertices in the order they appear on the path, and compute the sum of prefix sums of the resulting sequence.

Your task is to calculate the maximum value over all paths in the tree.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 150000$$$) — the number of vertices in the tree.

Then $$$n - 1$$$ lines follow, representing the edges of the tree. Each line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$), denoting an edge between vertices $$$u_i$$$ and $$$v_i$$$. It is guaranteed that these edges form a tree.

The last line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^6$$$).

## Output Format
Print one integer — the maximum value over all paths in the tree.

## Examples
```input
4
4 2
3 2
4 1
1 3 3 7
```
```output
36
```

## Note
The best path in the first example is from vertex $$$3$$$ to vertex $$$1$$$. It gives the sequence $$$[3, 3, 7, 1]$$$, and the sum of prefix sums is $$$36$$$.

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: 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 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
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 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
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 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
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 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
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 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
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.
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
Bob is playing a game named "Walk on Matrix".

In this game, player is given an $$$n \times m$$$ matrix $$$A=(a_{i,j})$$$, i.e. the element in the $$$i$$$-th row in the $$$j$$$-th column is $$$a_{i,j}$$$. Initially, player is located at position $$$(1,1)$$$ with score $$$a_{1,1}$$$.

To reach the goal, position $$$(n,m)$$$, player can move right or down, i.e. move from $$$(x,y)$$$ to $$$(x,y+1)$$$ or $$$(x+1,y)$$$, as long as player is still on the matrix.

However, each move changes player's score to the bitwise AND of the current score and the value at the position he moves to.

Bob can't wait to find out the maximum score he can get using the tool he recently learnt  — dynamic programming. Here is his algorithm for this problem.

However, he suddenly realize that the algorithm above fails to output the maximum score for some matrix $$$A$$$. Thus, for any given non-negative integer $$$k$$$, he wants to find out an $$$n \times m$$$ matrix $$$A=(a_{i,j})$$$ such that

- $$$1 \le n,m \le 500$$$ (as Bob hates large matrix);
- $$$0 \le a_{i,j} \le 3 \cdot 10^5$$$ for all $$$1 \le i\le n,1 \le j\le m$$$ (as Bob hates large numbers);
- the difference between the maximum score he can get and the output of his algorithm is exactly $$$k$$$.

It can be shown that for any given integer $$$k$$$ such that $$$0 \le k \le 10^5$$$, there exists a matrix satisfying the above constraints.

Please help him with it!

## Input Format
The only line of the input contains one single integer $$$k$$$ ($$$0 \le k \le 10^5$$$).

## Output Format
Output two integers $$$n$$$, $$$m$$$ ($$$1 \le n,m \le 500$$$) in the first line, representing the size of the matrix.

Then output $$$n$$$ lines with $$$m$$$ integers in each line, $$$a_{i,j}$$$ in the $$$(i+1)$$$-th row, $$$j$$$-th column.

## Examples
```input
0
```
```output
1 1
300000
```
-----
```input
1
```
```output
3 4
7 3 3 1
4 8 3 6
7 7 7 3
```

## Note
In the first example, the maximum score Bob can achieve is $$$300000$$$, while the output of his algorithm is $$$300000$$$.

In the second example, the maximum score Bob can achieve is $$$7\&3\&3\&3\&7\&3=3$$$, while the output of his algorithm is $$$2$$$.

Now solve the problem and return the code.