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
There are $$$n$$$ warriors in a row. The power of the $$$i$$$-th warrior is $$$a_i$$$. All powers are pairwise distinct.

You have two types of spells which you may cast:

1. Fireball: you spend $$$x$$$ mana and destroy exactly $$$k$$$ consecutive warriors;
2. Berserk: you spend $$$y$$$ mana, choose two consecutive warriors, and the warrior with greater power destroys the warrior with smaller power.

For example, let the powers of warriors be $$$[2, 3, 7, 8, 11, 5, 4]$$$, and $$$k = 3$$$. If you cast Berserk on warriors with powers $$$8$$$ and $$$11$$$, the resulting sequence of powers becomes $$$[2, 3, 7, 11, 5, 4]$$$. Then, for example, if you cast Fireball on consecutive warriors with powers $$$[7, 11, 5]$$$, the resulting sequence of powers becomes $$$[2, 3, 4]$$$.

You want to turn the current sequence of warriors powers $$$a_1, a_2, \dots, a_n$$$ into $$$b_1, b_2, \dots, b_m$$$. Calculate the minimum amount of mana you need to spend on it.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the length of sequence $$$a$$$ and the length of sequence $$$b$$$ respectively.

The second line contains three integers $$$x, k, y$$$ ($$$1 \le x, y, \le 10^9; 1 \le k \le n$$$) — the cost of fireball, the range of fireball and the cost of berserk respectively.

The third line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$). It is guaranteed that all integers $$$a_i$$$ are pairwise distinct.

The fourth line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le n$$$). It is guaranteed that all integers $$$b_i$$$ are pairwise distinct.

## Output Format
Print the minimum amount of mana for turning the sequnce $$$a_1, a_2, \dots, a_n$$$ into $$$b_1, b_2, \dots, b_m$$$, or $$$-1$$$ if it is impossible.

## Examples
```input
5 2
5 2 3
3 1 4 5 2
3 5
```
```output
8
```
-----
```input
4 4
5 1 4
4 3 1 2
2 4 3 1
```
```output
-1
```
-----
```input
4 4
2 1 11
1 3 2 4
1 3 2 4
```
```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 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
The length of the longest common prefix of two strings $$$s = s_1 s_2 \ldots s_n$$$ and $$$t = t_1 t_2 \ldots t_m$$$ is defined as the maximum integer $$$k$$$ ($$$0 \le k \le min(n,m)$$$) such that $$$s_1 s_2 \ldots s_k$$$ equals $$$t_1 t_2 \ldots t_k$$$.

Koa the Koala initially has $$$n+1$$$ strings $$$s_1, s_2, \dots, s_{n+1}$$$.

For each $$$i$$$ ($$$1 \le i \le n$$$) she calculated $$$a_i$$$ — the length of the longest common prefix of $$$s_i$$$ and $$$s_{i+1}$$$.

Several days later Koa found these numbers, but she couldn't remember the strings.

So Koa would like to find some strings $$$s_1, s_2, \dots, s_{n+1}$$$ which would have generated numbers $$$a_1, a_2, \dots, a_n$$$. Can you help her?

If there are many answers print any. We can show that answer always exists for the given constraints.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of elements in the list $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 50$$$) — the elements of $$$a$$$.

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

## Output Format
For each test case:

Output $$$n+1$$$ lines. In the $$$i$$$-th line print string $$$s_i$$$ ($$$1 \le |s_i| \le 200$$$), consisting of lowercase Latin letters. Length of the longest common prefix of strings $$$s_i$$$ and $$$s_{i+1}$$$ has to be equal to $$$a_i$$$.

If there are many answers print any. We can show that answer always exists for the given constraints.

## Examples
```input
4
4
1 2 4 2
2
5 3
3
1 3 1
3
0 0 0
```
```output
aeren
ari
arousal
around
ari
monogon
monogamy
monthly
kevinvu
kuroni
kurioni
korone
anton
loves
adhoc
problems
```

## Note
In the $$$1$$$-st test case one of the possible answers is $$$s = [aeren, ari, arousal, around, ari]$$$.

Lengths of longest common prefixes are:

- Between $$$\color{red}{a}eren$$$ and $$$\color{red}{a}ri$$$ $$$\rightarrow 1$$$
- Between $$$\color{red}{ar}i$$$ and $$$\color{red}{ar}ousal$$$ $$$\rightarrow 2$$$
- Between $$$\color{red}{arou}sal$$$ and $$$\color{red}{arou}nd$$$ $$$\rightarrow 4$$$
- Between $$$\color{red}{ar}ound$$$ and $$$\color{red}{ar}i$$$ $$$\rightarrow 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
You are given an array $$$a_1, a_2, \dots , a_n$$$, which is sorted in non-decreasing order ($$$a_i \le a_{i + 1})$$$.

Find three indices $$$i$$$, $$$j$$$, $$$k$$$ such that $$$1 \le i < j < k \le n$$$ and it is impossible to construct a non-degenerate triangle (a triangle with nonzero area) having sides equal to $$$a_i$$$, $$$a_j$$$ and $$$a_k$$$ (for example it is possible to construct a non-degenerate triangle with sides $$$3$$$, $$$4$$$ and $$$5$$$ but impossible with sides $$$3$$$, $$$4$$$ and $$$7$$$). If it is impossible to find such triple, report it.

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

The first line of each test case contains one integer $$$n$$$ ($$$3 \le n \le 5 \cdot 10^4$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le 10^9$$$; $$$a_{i - 1} \le a_i$$$) — the array $$$a$$$.

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 answer to it in one line.

If there is a triple of indices $$$i$$$, $$$j$$$, $$$k$$$ ($$$i < j < k$$$) such that it is impossible to construct a non-degenerate triangle having sides equal to $$$a_i$$$, $$$a_j$$$ and $$$a_k$$$, print that three indices in ascending order. If there are multiple answers, print any of them.

Otherwise, print -1.

## Examples
```input
3
7
4 6 11 11 15 18 20
4
10 10 10 11
3
1 1 1000000000
```
```output
2 3 6
-1
1 2 3
```

## Note
In the first test case it is impossible with sides $$$6$$$, $$$11$$$ and $$$18$$$. Note, that this is not the only correct answer.

In the second test case you always can construct a non-degenerate triangle.

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
Alice and Bob play a game. They have a binary string $$$s$$$ (a string such that each character in it is either $$$0$$$ or $$$1$$$). Alice moves first, then Bob, then Alice again, and so on.

During their move, the player can choose any number (not less than one) of consecutive equal characters in $$$s$$$ and delete them.

For example, if the string is $$$10110$$$, there are $$$6$$$ possible moves (deleted characters are bold):

1. $$$\textbf{1}0110 \to 0110$$$;
2. $$$1\textbf{0}110 \to 1110$$$;
3. $$$10\textbf{1}10 \to 1010$$$;
4. $$$101\textbf{1}0 \to 1010$$$;
5. $$$10\textbf{11}0 \to 100$$$;
6. $$$1011\textbf{0} \to 1011$$$.

After the characters are removed, the characters to the left and to the right of the removed block become adjacent. I. e. the following sequence of moves is valid: $$$10\textbf{11}0 \to 1\textbf{00} \to 1$$$.

The game ends when the string becomes empty, and the score of each player is the number of $$$1$$$-characters deleted by them.

Each player wants to maximize their score. Calculate the resulting score of Alice.

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

Each test case contains exactly one line containing a binary string $$$s$$$ ($$$1 \le |s| \le 100$$$).

## Output Format
For each test case, print one integer — the resulting score of Alice (the number of $$$1$$$-characters deleted by her).

## Examples
```input
5
01111001
0000
111111
101010101
011011110111
```
```output
4
0
6
3
6
```

## Note
Questions about the optimal strategy will be ignored.

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
You are given an array $$$a_1, a_2, \dots , a_n$$$ consisting of integers from $$$0$$$ to $$$9$$$. A subarray $$$a_l, a_{l+1}, a_{l+2}, \dots , a_{r-1}, a_r$$$ is good if the sum of elements of this subarray is equal to the length of this subarray ($$$\sum\limits_{i=l}^{r} a_i = r - l + 1$$$).

For example, if $$$a = [1, 2, 0]$$$, then there are $$$3$$$ good subarrays: $$$a_{1 \dots 1} = [1], a_{2 \dots 3} = [2, 0]$$$ and $$$a_{1 \dots 3} = [1, 2, 0]$$$.

Calculate the number of good subarrays of the array $$$a$$$.

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains a string consisting of $$$n$$$ decimal digits, where the $$$i$$$-th digit is equal to the value of $$$a_i$$$.

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

## Output Format
For each test case print one integer — the number of good subarrays of the array $$$a$$$.

## Examples
```input
3
3
120
5
11011
6
600005
```
```output
3
6
1
```

## Note
The first test case is considered in the statement.

In the second test case, there are $$$6$$$ good subarrays: $$$a_{1 \dots 1}$$$, $$$a_{2 \dots 2}$$$, $$$a_{1 \dots 2}$$$, $$$a_{4 \dots 4}$$$, $$$a_{5 \dots 5}$$$ and $$$a_{4 \dots 5}$$$.

In the third test case there is only one good subarray: $$$a_{2 \dots 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: 256.0 MB

# Problem
Alice and Bob play a game. The game consists of several sets, and each set consists of several rounds. Each round is won either by Alice or by Bob, and the set ends when one of the players has won $$$x$$$ rounds in a row. For example, if Bob won five rounds in a row and $$$x = 2$$$, then two sets ends.

You know that Alice and Bob have already played $$$n$$$ rounds, and you know the results of some rounds. For each $$$x$$$ from $$$1$$$ to $$$n$$$, calculate the maximum possible number of sets that could have already finished if each set lasts until one of the players wins $$$x$$$ rounds in a row. It is possible that the last set is still not finished — in that case, you should not count it in the answer.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of rounds.

The second line contains one string $$$s$$$ of length $$$n$$$ — the descriptions of rounds. If the $$$i$$$-th element of the string is 0, then Alice won the $$$i$$$-th round; if it is 1, then Bob won the $$$i$$$-th round, and if it is ?, then you don't know who won the $$$i$$$-th round.

## Output Format
In the only line print $$$n$$$ integers. The $$$i$$$-th integer should be equal to the maximum possible number of sets that could have already finished if each set lasts until one of the players wins $$$i$$$ rounds in a row.

## Examples
```input
6
11?000
```
```output
6 3 2 1 0 0
```
-----
```input
5
01?01
```
```output
5 1 0 0 0
```
-----
```input
12
???1??????1?
```
```output
12 6 4 3 2 2 1 1 1 1 1 1
```

## Note
Let's consider the first test case:

- if $$$x = 1$$$ and $$$s = 110000$$$ or $$$s = 111000$$$ then there are six finished sets;
- if $$$x = 2$$$ and $$$s = 110000$$$ then there are three finished sets;
- if $$$x = 3$$$ and $$$s = 111000$$$ then there are two finished sets;
- if $$$x = 4$$$ and $$$s = 110000$$$ then there is one finished set;
- if $$$x = 5$$$ then there are no finished sets;
- if $$$x = 6$$$ then there are no finished sets.

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
A running competition is going to be held soon. The stadium where the competition will be held can be represented by several segments on the coordinate plane:

- two horizontal segments: one connecting the points $$$(0, 0)$$$ and $$$(x, 0)$$$, the other connecting the points $$$(0, y)$$$ and $$$(x, y)$$$;
- $$$n + 1$$$ vertical segments, numbered from $$$0$$$ to $$$n$$$. The $$$i$$$-th segment connects the points $$$(a_i, 0)$$$ and $$$(a_i, y)$$$; $$$0 = a_0 < a_1 < a_2 < \dots < a_{n - 1} < a_n = x$$$.

For example, here is a picture of the stadium with $$$x = 10$$$, $$$y = 5$$$, $$$n = 3$$$ and $$$a = [0, 3, 5, 10]$$$:

A lap is a route that goes along the segments, starts and finishes at the same point, and never intersects itself (the only two points of a lap that coincide are its starting point and ending point). The length of a lap is a total distance travelled around it. For example, the red route in the picture representing the stadium is a lap of length $$$24$$$.

The competition will be held in $$$q$$$ stages. The $$$i$$$-th stage has length $$$l_i$$$, and the organizers want to choose a lap for each stage such that the length of the lap is a divisor of $$$l_i$$$. The organizers don't want to choose short laps for the stages, so for each stage, they want to find the maximum possible length of a suitable lap.

Help the organizers to calculate the maximum possible lengths of the laps for the stages! In other words, for every $$$l_i$$$, find the maximum possible integer $$$L$$$ such that $$$l_i \bmod L = 0$$$, and there exists a lap of length exactly $$$L$$$.

If it is impossible to choose such a lap then print $$$-1$$$.

## Input Format
The first line contains three integers $$$n$$$, $$$x$$$ and $$$y$$$ ($$$1 \le n, x, y \le 2 \cdot 10^5$$$, $$$n \le x$$$).

The second line contains $$$n + 1$$$ integers $$$a_0$$$, $$$a_1$$$, ..., $$$a_n$$$ ($$$0 = a_0 < a_1 < a_2 < \dots < a_{n - 1} < a_n = x$$$).

The third line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of stages.

The fourth line contains $$$q$$$ even integers $$$l_1$$$, $$$l_2$$$, ..., $$$l_q$$$ ($$$4 \le l_i \le 10^6$$$) — the lengths of the stages.

## Output Format
Print $$$q$$$ numbers. The $$$i$$$-th number should be equal to the maximum possible length of a suitable lap for the $$$i$$$-th stage, or $$$-1$$$ if it is impossible to choose a lap for that stage.

## Examples
```input
3 10 5
0 3 5 10
6
24 30 14 16 18 10
```
```output
24 30 14 16 -1 -1
```

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
Gerald is setting the New Year table. The table has the form of a circle; its radius equals R. Gerald invited many guests and is concerned whether the table has enough space for plates for all those guests. Consider all plates to be round and have the same radii that equal r. Each plate must be completely inside the table and must touch the edge of the table. Of course, the plates must not intersect, but they can touch each other. Help Gerald determine whether the table is large enough for n plates.

## Input Format
The first line contains three integers n, R and r (1 ≤ n ≤ 100, 1 ≤ r, R ≤ 1000) — the number of plates, the radius of the table and the plates' radius.

## Output Format
Print "YES" (without the quotes) if it is possible to place n plates on the table by the rules given above. If it is impossible, print "NO".

Remember, that each plate must touch the edge of the table.

## Examples
```input
4 10 4
```
```output
YES
```
-----
```input
5 10 4
```
```output
NO
```
-----
```input
1 10 10
```
```output
YES
```

## Note
The possible arrangement of the plates for the first sample is:

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
As meticulous Gerald sets the table and caring Alexander sends the postcards, Sergey makes snowmen. Each showman should consist of three snowballs: a big one, a medium one and a small one. Sergey's twins help him: they've already made n snowballs with radii equal to r1, r2, ..., rn. To make a snowman, one needs any three snowballs whose radii are pairwise different. For example, the balls with radii 1, 2 and 3 can be used to make a snowman but 2, 2, 3 or 2, 2, 2 cannot. Help Sergey and his twins to determine what maximum number of snowmen they can make from those snowballs.

## Input Format
The first line contains integer n (1 ≤ n ≤ 105) — the number of snowballs. The next line contains n integers — the balls' radii r1, r2, ..., rn (1 ≤ ri ≤ 109). The balls' radii can coincide.

## Output Format
Print on the first line a single number k — the maximum number of the snowmen. Next k lines should contain the snowmen's descriptions. The description of each snowman should consist of three space-separated numbers — the big ball's radius, the medium ball's radius and the small ball's radius. It is allowed to print the snowmen in any order. If there are several solutions, print any of them.

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

Now solve the problem and return the code.