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: 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 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
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 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_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 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
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 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: 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 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 two integers $$$a$$$ and $$$b$$$.

In one move, you can choose some integer $$$k$$$ from $$$1$$$ to $$$10$$$ and add it to $$$a$$$ or subtract it from $$$a$$$. In other words, you choose an integer $$$k \in [1; 10]$$$ and perform $$$a := a + k$$$ or $$$a := a - k$$$. You may use different values of $$$k$$$ in different moves.

Your task is to find the minimum number of moves required to obtain $$$b$$$ from $$$a$$$.

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

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The only line of the test case contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^9$$$).

## Output Format
For each test case, print the answer: the minimum number of moves required to obtain $$$b$$$ from $$$a$$$.

## Examples
```input
6
5 5
13 42
18 4
1337 420
123456789 1000000000
100500 9000
```
```output
0
3
2
92
87654322
9150
```

## Note
In the first test case of the example, you don't need to do anything.

In the second test case of the example, the following sequence of moves can be applied: $$$13 \rightarrow 23 \rightarrow 32 \rightarrow 42$$$ (add $$$10$$$, add $$$9$$$, add $$$10$$$).

In the third test case of the example, the following sequence of moves can be applied: $$$18 \rightarrow 10 \rightarrow 4$$$ (subtract $$$8$$$, subtract $$$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 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 $$$a$$$, $$$b$$$, $$$x$$$ and $$$y$$$. Initially, $$$a \ge x$$$ and $$$b \ge y$$$. You can do the following operation no more than $$$n$$$ times:

- Choose either $$$a$$$ or $$$b$$$ and decrease it by one. However, as a result of this operation, value of $$$a$$$ cannot become less than $$$x$$$, and value of $$$b$$$ cannot become less than $$$y$$$.

Your task is to find the minimum possible product of $$$a$$$ and $$$b$$$ ($$$a \cdot b$$$) you can achieve by applying the given operation no more than $$$n$$$ times.

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

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The only line of the test case contains five integers $$$a$$$, $$$b$$$, $$$x$$$, $$$y$$$ and $$$n$$$ ($$$1 \le a, b, x, y, n \le 10^9$$$). Additional constraint on the input: $$$a \ge x$$$ and $$$b \ge y$$$ always holds.

## Output Format
For each test case, print one integer: the minimum possible product of $$$a$$$ and $$$b$$$ ($$$a \cdot b$$$) you can achieve by applying the given operation no more than $$$n$$$ times.

## Examples
```input
7
10 10 8 5 3
12 8 8 7 2
12343 43 4543 39 123212
1000000000 1000000000 1 1 1
1000000000 1000000000 1 1 1000000000
10 11 2 1 5
10 11 9 1 10
```
```output
70
77
177177
999999999000000000
999999999
55
10
```

## Note
In the first test case of the example, you need to decrease $$$b$$$ three times and obtain $$$10 \cdot 7 = 70$$$.

In the second test case of the example, you need to decrease $$$a$$$ one time, $$$b$$$ one time and obtain $$$11 \cdot 7 = 77$$$.

In the sixth test case of the example, you need to decrease $$$a$$$ five times and obtain $$$5 \cdot 11 = 55$$$.

In the seventh test case of the example, you need to decrease $$$b$$$ ten times and obtain $$$10 \cdot 1 = 10$$$.

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
We have a secret array. You don't know this array and you have to restore it. However, you know some facts about this array:

- The array consists of $$$n$$$ distinct positive (greater than $$$0$$$) integers.
- The array contains two elements $$$x$$$ and $$$y$$$ (these elements are known for you) such that $$$x < y$$$.
- If you sort the array in increasing order (such that $$$a_1 < a_2 < \ldots < a_n$$$), differences between all adjacent (consecutive) elements are equal (i.e. $$$a_2 - a_1 = a_3 - a_2 = \ldots = a_n - a_{n-1})$$$.

It can be proven that such an array always exists under the constraints given below.

Among all possible arrays that satisfy the given conditions, we ask you to restore one which has the minimum possible maximum element. In other words, you have to minimize $$$\max(a_1, a_2, \dots, a_n)$$$.

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 only line of the test case contains three integers $$$n$$$, $$$x$$$ and $$$y$$$ ($$$2 \le n \le 50$$$; $$$1 \le x < y \le 50$$$) — the length of the array and two elements that are present in the array, respectively.

## Output Format
For each test case, print the answer: $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the $$$i$$$-th element of the required array. If there are several answers, you can print any (it also means that the order of elements doesn't matter).

It can be proven that such an array always exists under the given constraints.

## Examples
```input
5
2 1 49
5 20 50
6 20 50
5 3 8
9 13 22
```
```output
1 49 
20 40 30 50 10
26 32 20 38 44 50 
8 23 18 13 3 
1 10 13 4 19 22 25 16 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 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 a positive integer $$$n$$$. In one move, you can increase $$$n$$$ by one (i.e. make $$$n := n + 1$$$). Your task is to find the minimum number of moves you need to perform in order to make the sum of digits of $$$n$$$ be less than or equal to $$$s$$$.

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

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The only line of the test case contains two integers $$$n$$$ and $$$s$$$ ($$$1 \le n \le 10^{18}$$$; $$$1 \le s \le 162$$$).

## Output Format
For each test case, print the answer: the minimum number of moves you need to perform in order to make the sum of digits of $$$n$$$ be less than or equal to $$$s$$$.

## Examples
```input
5
2 1
1 1
500 4
217871987498122 10
100000000000000001 1
```
```output
8
0
500
2128012501878
899999999999999999
```

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 two strings $$$s$$$ and $$$t$$$ consisting of lowercase Latin letters. The length of $$$t$$$ is $$$2$$$ (i.e. this string consists only of two characters).

In one move, you can choose any character of $$$s$$$ and replace it with any lowercase Latin letter. More formally, you choose some $$$i$$$ and replace $$$s_i$$$ (the character at the position $$$i$$$) with some character from 'a' to 'z'.

You want to do no more than $$$k$$$ replacements in such a way that maximizes the number of occurrences of $$$t$$$ in $$$s$$$ as a subsequence.

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 200$$$; $$$0 \le k \le n$$$) — the length of $$$s$$$ and the maximum number of moves you can make. The second line of the input contains the string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters. The third line of the input contains the string $$$t$$$ consisting of two lowercase Latin letters.

## Output Format
Print one integer — the maximum possible number of occurrences of $$$t$$$ in $$$s$$$ as a subsequence if you replace no more than $$$k$$$ characters in $$$s$$$ optimally.

## Examples
```input
4 2
bbaa
ab
```
```output
3
```
-----
```input
7 3
asddsaf
sd
```
```output
10
```
-----
```input
15 6
qwertyhgfdsazxc
qa
```
```output
16
```
-----
```input
7 2
abacaba
aa
```
```output
15
```

## Note
In the first example, you can obtain the string "abab" replacing $$$s_1$$$ with 'a' and $$$s_4$$$ with 'b'. Then the answer is $$$3$$$.

In the second example, you can obtain the string "ssddsdd" and get the answer $$$10$$$.

In the fourth example, you can obtain the string "aaacaaa" and get the answer $$$15$$$.

Now solve the problem and return the code.