apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Argus was charged with guarding Io, which is not an ordinary cow. Io is quite an explorer, and she wanders off rather frequently, making Argus' life stressful. So the cowherd decided to construct an enclosed pasture for Io.

There are $$$n$$$ trees growing along the river, where Argus tends Io. For this problem, the river can be viewed as the $$$OX$$$ axis of the Cartesian coordinate system, and the $$$n$$$ trees as points with the $$$y$$$-coordinate equal $$$0$$$. There is also another tree growing in the point $$$(0, 1)$$$.

Argus will tie a rope around three of the trees, creating a triangular pasture. Its exact shape doesn't matter to Io, but its area is crucial to her. There may be many ways for Argus to arrange the fence, but only the ones which result in different areas of the pasture are interesting for Io. Calculate the number of different areas that her pasture may have. Note that the pasture must have nonzero area.

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. Then $$$t$$$ test cases follow, each one is described in two lines.

In the first line of each test case there is a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) denoting the number of trees growing along the river. Next line contains $$$n$$$ distinct integers $$$x_1 < x_2 < \ldots < x_{n - 1} < x_n$$$ ($$$1 \leq x_i \leq 50$$$), the $$$x$$$-coordinates of trees growing along the river.

## Output Format
In a single line output an integer, the number of different nonzero areas that triangles with trees as vertices may have.

## Examples
```input
8
4
1 2 4 5
3
1 3 5
3
2 6 8
2
1 2
1
50
5
3 4 5 6 8
3
1 25 26
6
1 2 4 8 16 32
```
```output
4
2
3
1
0
5
3
15
```

## Note
In the first test case, we have $$$6$$$ non-degenerate triangles with the following areas: $$$0.5$$$, $$$0.5$$$, $$$1$$$, $$$1.5$$$, $$$1.5$$$ and $$$2$$$. The pasture can have $$$4$$$ different areas, and thus $$$4$$$ is the answer.

In the second test case, we have $$$3$$$ non-degenerate triangles with the following areas: $$$1$$$, $$$1$$$ and $$$2$$$. The pasture can have $$$2$$$ different areas, so $$$2$$$ is the answer.

The following two drawings present the situation in the second test case. The blue triangles in the first drawing have area $$$1$$$. The red triangle in the second drawing has area $$$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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
After his wife's tragic death, Eurydice, Orpheus descended to the realm of death to see her. Reaching its gates was uneasy, but passing through them proved to be even more challenging. Mostly because of Cerberus, the three-headed hound of Hades.

Orpheus, a famous poet, and musician plans to calm Cerberus with his poetry and safely walk past him. He created a very peculiar poem for Cerberus. It consists only of lowercase English letters.

We call a poem's substring a palindrome if and only if it reads the same backwards and forwards. A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deleting several (possibly zero or all) characters from the beginning and several (possibly zero or all) characters from the end.

Unfortunately, Cerberus dislikes palindromes of length greater than $$$1$$$. For example in the poem abaa the hound of Hades wouldn't like substrings aba and aa.

Orpheus can only calm Cerberus if the hound likes his poetry. That's why he wants to change his poem so that it does not contain any palindrome substrings of length greater than $$$1$$$.

Orpheus can modify the poem by replacing a letter at any position with any lowercase English letter. He can use this operation arbitrarily many times (possibly zero). Since there can be many palindromes in his poem, he may have to make some corrections. But how many, exactly? Given the poem, determine the minimal number of letters that have to be changed so that the poem does not contain any palindromes of length greater than $$$1$$$.

## Input Format
The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) denoting the number of test cases, then $$$t$$$ test cases follow.

The first and only line of each test case contains a non-empty string of lowercase English letters, Orpheus' poem.

The sum of the length of Orpheus' poems in all test cases will not exceed $$$10^5$$$.

## Output Format
You should output $$$t$$$ lines, $$$i$$$-th line should contain a single integer, answer to the $$$i$$$-th test case.

## Examples
```input
7
babba
abaac
codeforces
zeroorez
abcdcba
bbbbbbb
a
```
```output
1
1
0
1
1
4
0
```

## Note
In the first test case, we can replace the third character with c and obtain a palindrome-less poem bacba.

In the second test case, we can replace the third character with d and obtain a palindrome-less poem abdac.

In the third test case, the initial poem already doesn't contain any palindromes, so Orpheus doesn't need to change anything there.

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
In the times of Jason and the Argonauts, it was well known that sirens use the sound of their songs to lure sailors into their demise. Yet only a few knew that every time sirens call a sailor by his name, his will weakens, making him more vulnerable.

For the purpose of this problem, both siren songs and names of the sailors will be represented as strings of lowercase English letters. The more times the sailor's name occurs as a contiguous substring of the song, the greater danger he is in.

Jason found out that sirens can sing one of the $$$n+1$$$ songs, which have the following structure: let $$$s_i$$$ ($$$0 \leq i \leq n$$$) be the $$$i$$$-th song and $$$t$$$ be a string of length $$$n$$$, then for every $$$i < n$$$: $$$s_{i+1} = s_i t_i s_i$$$. In other words $$$i+1$$$-st song is the concatenation of $$$i$$$-th song, $$$i$$$-th letter ($$$0$$$-indexed) of $$$t$$$ and the $$$i$$$-th song.

Fortunately, he also knows $$$s_0$$$ and $$$t$$$. Jason wonders how many times a sailor's name is mentioned in a particular song. Answer $$$q$$$ queries: given the sailor's name ($$$w$$$) and the index of a song ($$$i$$$) output the number of occurrences of $$$w$$$ in $$$s_i$$$ as a substring. As this number can be quite large, output its remainder modulo $$$10^9+7$$$.

## Input Format
In the first line of input there are two integers $$$n$$$, $$$q$$$ ( $$$ 1 \leq n, q \leq 10^5$$$) meaning that there are $$$n+1$$$ songs and $$$q$$$ queries. In the next two lines strings $$$s_0$$$ and $$$t$$$ follow ($$$1 \leq |s_0| \leq 100, |t| = n$$$).

Next $$$q$$$ lines describe the queries; each one contains an integer $$$k$$$ ($$$ 0 \leq k \leq n$$$), the index of the song sung by the sirens, and a non-empty string $$$w$$$, which is the name of a sailor. All strings in this problem consist only of lowercase English letters, and the sum of lengths of sailors' names does not exceed $$$10^6$$$.

## Output Format
Output $$$q$$$ lines, $$$i$$$-th of them should contain the remainder modulo $$$10^9+7$$$ of the number of occurrences of $$$w$$$ in $$$s_k$$$.

## Examples
```input
3 3
aa
bcd
2 aba
3 ca
3 aa
```
```output
2
2
8
```
-----
```input
4 5
aba
bbac
1 a
3 baca
3 ab
2 bab
4 aba
```
```output
4
0
14
6
28
```

## Note
In the first example songs of the sirens are as follows:

- Song $$$0$$$: aa
- Song $$$1$$$: aabaa
- Song $$$2$$$: aabaacaabaa
- Song $$$3$$$: aabaacaabaadaabaacaabaa

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
For the New Year, Polycarp decided to send postcards to all his $$$n$$$ friends. He wants to make postcards with his own hands. For this purpose, he has a sheet of paper of size $$$w \times h$$$, which can be cut into pieces.

Polycarp can cut any sheet of paper $$$w \times h$$$ that he has in only two cases:

- If $$$w$$$ is even, then he can cut the sheet in half and get two sheets of size $$$\frac{w}{2} \times h$$$;
- If $$$h$$$ is even, then he can cut the sheet in half and get two sheets of size $$$w \times \frac{h}{2}$$$;

If $$$w$$$ and $$$h$$$ are even at the same time, then Polycarp can cut the sheet according to any of the rules above.

After cutting a sheet of paper, the total number of sheets of paper is increased by $$$1$$$.

Help Polycarp to find out if he can cut his sheet of size $$$w \times h$$$ at into $$$n$$$ or more pieces, using only the rules described above.

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

Each test case consists of one line containing three integers $$$w$$$, $$$h$$$, $$$n$$$ ($$$1 \le w, h \le 10^4, 1 \le n \le 10^9$$$) — the width and height of the sheet Polycarp has and the number of friends he needs to send a postcard to.

## Output Format
For each test case, output on a separate line:

- "YES", if it is possible to cut a sheet of size $$$w \times h$$$ into at least $$$n$$$ pieces;
- "NO" otherwise.

You can output "YES" and "NO" in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

## Examples
```input
5
2 2 3
3 3 2
5 10 2
11 13 1
1 4 4
```
```output
YES
NO
YES
YES
YES
```

## Note
In the first test case, you can first cut the $$$2 \times 2$$$ sheet into two $$$2 \times 1$$$ sheets, and then cut each of them into two more sheets. As a result, we get four sheets $$$1 \times 1$$$. We can choose any three of them and send them to our friends.

In the second test case, a $$$3 \times 3$$$ sheet cannot be cut, so it is impossible to get two sheets.

In the third test case, you can cut a $$$5 \times 10$$$ sheet into two $$$5 \times 5$$$ sheets.

In the fourth test case, there is no need to cut the sheet, since we only need one sheet.

In the fifth test case, you can first cut the $$$1 \times 4$$$ sheet into two $$$1 \times 2$$$ sheets, and then cut each of them into two more sheets. As a result, we get four sheets $$$1 \times 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
During their New Year holidays, Alice and Bob play the following game using an array $$$a$$$ of $$$n$$$ integers:

- Players take turns, Alice moves first.
- Each turn a player chooses any element and removes it from the array.
- If Alice chooses even value, then she adds it to her score. If the chosen value is odd, Alice's score does not change.
- Similarly, if Bob chooses odd value, then he adds it to his score. If the chosen value is even, then Bob's score does not change.

If there are no numbers left in the array, then the game ends. The player with the highest score wins. If the scores of the players are equal, then a draw is declared.

For example, if $$$n = 4$$$ and $$$a = [5, 2, 7, 3]$$$, then the game could go as follows (there are other options):

- On the first move, Alice chooses $$$2$$$ and get two points. Her score is now $$$2$$$. The array $$$a$$$ is now $$$[5, 7, 3]$$$.
- On the second move, Bob chooses $$$5$$$ and get five points. His score is now $$$5$$$. The array $$$a$$$ is now $$$[7, 3]$$$.
- On the third move, Alice chooses $$$7$$$ and get no points. Her score is now $$$2$$$. The array $$$a$$$ is now $$$[3]$$$.
- On the last move, Bob chooses $$$3$$$ and get three points. His score is now $$$8$$$. The array $$$a$$$ is empty now.
- Since Bob has more points at the end of the game, he is the winner.

You want to find out who will win if both players play optimally. Note that there may be duplicate numbers in the array.

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

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

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array $$$a$$$ used to play the game.

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

## Output Format
For each test case, output on a separate line:

- "Alice" if Alice wins with the optimal play;
- "Bob" if Bob wins with the optimal play;
- "Tie", if a tie is declared during the optimal play.

## Examples
```input
4
4
5 2 7 3
3
3 2 1
4
2 2 2 2
2
7 8
```
```output
Bob
Tie
Alice
Alice
```

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
Every year Santa Claus gives gifts to all children. However, each country has its own traditions, and this process takes place in different ways. For example, in Berland you need to solve the New Year's puzzle.

Polycarp got the following problem: given a grid strip of size $$$2 \times n$$$, some cells of it are blocked. You need to check if it is possible to tile all free cells using the $$$2 \times 1$$$ and $$$1 \times 2$$$ tiles (dominoes).

For example, if $$$n = 5$$$ and the strip looks like this (black cells are blocked):

Then it can be tiled, for example, using two vertical and two horizontal tiles, as in the picture below (different tiles are marked by different colors).

And if $$$n = 3$$$ and the strip looks like this:

It is impossible to tile free cells.

Polycarp easily solved this task and received his New Year's gift. Can you solve it?

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case is preceded by an empty line.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — the length of the strip and the number of blocked cells on it.

Each of the next $$$m$$$ lines contains two integers $$$r_i, c_i$$$ ($$$1 \le r_i \le 2, 1 \le c_i \le n$$$) — numbers of rows and columns of blocked cells. It is guaranteed that all blocked cells are different, i.e. $$$(r_i, c_i) \ne (r_j, c_j), i \ne j$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print on a separate line:

- "YES", if it is possible to tile all unblocked squares with the $$$2 \times 1$$$ and $$$1 \times 2$$$ tiles;
- "NO" otherwise.

You can output "YES" and "NO" in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

## Examples
```input
3

5 2
2 2
1 4

3 2
2 1
2 3

6 4
2 1
2 3
2 4
2 6
```
```output
YES
NO
NO
```

## Note
The first two test cases are explained in the statement.

In the third test case the strip looks like this:

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
«One dragon. Two dragon. Three dragon», — the princess was counting. She had trouble falling asleep, and she got bored of counting lambs when she was nine.

However, just counting dragons was boring as well, so she entertained herself at best she could. Tonight she imagined that all dragons were here to steal her, and she was fighting them off. Every k-th dragon got punched in the face with a frying pan. Every l-th dragon got his tail shut into the balcony door. Every m-th dragon got his paws trampled with sharp heels. Finally, she threatened every n-th dragon to call her mom, and he withdrew in panic.

How many imaginary dragons suffered moral or physical damage tonight, if the princess counted a total of d dragons?

## Input Format
Input data contains integer numbers k, l, m, n and d, each number in a separate line (1 ≤ k, l, m, n ≤ 10, 1 ≤ d ≤ 105).

## Output Format
Output the number of damaged dragons.

## Examples
```input
1
2
3
4
12
```
```output
12
```
-----
```input
2
3
4
5
24
```
```output
17
```

## Note
In the first case every first dragon got punched with a frying pan. Some of the dragons suffered from other reasons as well, but the pan alone would be enough.

In the second case dragons 1, 7, 11, 13, 17, 19 and 23 escaped unharmed.

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 princess is going to escape the dragon's cave, and she needs to plan it carefully.

The princess runs at vp miles per hour, and the dragon flies at vd miles per hour. The dragon will discover the escape after t hours and will chase the princess immediately. Looks like there's no chance to success, but the princess noticed that the dragon is very greedy and not too smart. To delay him, the princess decides to borrow a couple of bijous from his treasury. Once the dragon overtakes the princess, she will drop one bijou to distract him. In this case he will stop, pick up the item, return to the cave and spend f hours to straighten the things out in the treasury. Only after this will he resume the chase again from the very beginning.

The princess is going to run on the straight. The distance between the cave and the king's castle she's aiming for is c miles. How many bijous will she need to take from the treasury to be able to reach the castle? If the dragon overtakes the princess at exactly the same moment she has reached the castle, we assume that she reached the castle before the dragon reached her, and doesn't need an extra bijou to hold him off.

## Input Format
The input data contains integers vp, vd, t, f and c, one per line (1 ≤ vp, vd ≤ 100, 1 ≤ t, f ≤ 10, 1 ≤ c ≤ 1000).

## Output Format
Output the minimal number of bijous required for the escape to succeed.

## Examples
```input
1
2
1
1
10
```
```output
2
```
-----
```input
1
2
1
1
8
```
```output
1
```

## Note
In the first case one hour after the escape the dragon will discover it, and the princess will be 1 mile away from the cave. In two hours the dragon will overtake the princess 2 miles away from the cave, and she will need to drop the first bijou. Return to the cave and fixing the treasury will take the dragon two more hours; meanwhile the princess will be 4 miles away from the cave. Next time the dragon will overtake the princess 8 miles away from the cave, and she will need the second bijou, but after this she will reach the castle without any further trouble.

The second case is similar to the first one, but the second time the dragon overtakes the princess when she has reached the castle, and she won't need the second bijou.

Now solve the problem and return the code.