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.5 seconds
Memory limit: 256.0 MB

# Problem
One fine day Sasha went to the park for a walk. In the park, he saw that his favorite bench is occupied, and he had to sit down on the neighboring one. He sat down and began to listen to the silence. Suddenly, he got a question: what if in different parts of the park, the silence sounds in different ways? So it was. Let's divide the park into $$$1 \times 1$$$ meter squares and call them cells, and numerate rows from $$$1$$$ to $$$n$$$ from up to down, and columns from $$$1$$$ to $$$m$$$ from left to right. And now, every cell can be described with a pair of two integers $$$(x, y)$$$, where $$$x$$$ — the number of the row, and $$$y$$$ — the number of the column. Sasha knows that the level of silence in the cell $$$(i, j)$$$ equals to $$$f_{i,j}$$$, and all $$$f_{i,j}$$$ form a permutation of numbers from $$$1$$$ to $$$n \cdot m$$$. Sasha decided to count, how many are there pleasant segments of silence?

Let's take some segment $$$[l \ldots r]$$$. Denote $$$S$$$ as the set of cells $$$(i, j)$$$ that $$$l \le f_{i,j} \le r$$$. Then, the segment of silence $$$[l \ldots r]$$$ is pleasant if there is only one simple path between every pair of cells from $$$S$$$ (path can't contain cells, which are not in $$$S$$$). In other words, set $$$S$$$ should look like a tree on a plain. Sasha has done this task pretty quickly, and called the algorithm — "algorithm of silence's sounds".

Time passed, and the only thing left from the algorithm is a legend. To prove the truthfulness of this story, you have to help Sasha and to find the number of different pleasant segments of silence. Two segments $$$[l_1 \ldots r_1]$$$, $$$[l_2 \ldots r_2]$$$ are different, if $$$l_1 \neq l_2$$$ or $$$r_1 \neq r_2$$$ or both at the same time.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 1000$$$, $$$1 \le n \cdot m \le 2 \cdot 10^5$$$) — the size of the park.

Each from next $$$n$$$ lines contains $$$m$$$ integers $$$f_{i,j}$$$ ($$$1 \le f_{i,j} \le n \cdot m$$$) — the level of silence in the cell with number $$$(i, j)$$$.

It is guaranteed, that all $$$f_{i,j}$$$ are different.

## Output Format
Print one integer — the number of pleasant segments of silence.

## Examples
```input
1 5
1 2 3 4 5
```
```output
15
```
-----
```input
2 3
1 2 3
4 5 6
```
```output
15
```
-----
```input
4 4
4 3 2 16
1 13 14 15
5 7 8 12
6 11 9 10
```
```output
50
```

## Note
In the first example, all segments of silence are pleasant.

In the second example, pleasant segments of silence are the following:

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 all know that a superhero can transform to certain other superheroes. But not all Superheroes can transform to any other superhero. A superhero with name $$$s$$$ can transform to another superhero with name $$$t$$$ if $$$s$$$ can be made equal to $$$t$$$ by changing any vowel in $$$s$$$ to any other vowel and any consonant in $$$s$$$ to any other consonant. Multiple changes can be made.

In this problem, we consider the letters 'a', 'e', 'i', 'o' and 'u' to be vowels and all the other letters to be consonants.

Given the names of two superheroes, determine if the superhero with name $$$s$$$ can be transformed to the Superhero with name $$$t$$$.

## Input Format
The first line contains the string $$$s$$$ having length between $$$1$$$ and $$$1000$$$, inclusive.

The second line contains the string $$$t$$$ having length between $$$1$$$ and $$$1000$$$, inclusive.

Both strings $$$s$$$ and $$$t$$$ are guaranteed to be different and consist of lowercase English letters only.

## Output Format
Output "Yes" (without quotes) if the superhero with name $$$s$$$ can be transformed to the superhero with name $$$t$$$ and "No" (without quotes) otherwise.

You can print each letter in any case (upper or lower).

## Examples
```input
a
u
```
```output
Yes
```
-----
```input
abc
ukm
```
```output
Yes
```
-----
```input
akm
ua
```
```output
No
```

## Note
In the first sample, since both 'a' and 'u' are vowels, it is possible to convert string $$$s$$$ to $$$t$$$.

In the third sample, 'k' is a consonant, whereas 'a' is a vowel, so it is not possible to convert string $$$s$$$ to $$$t$$$.

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
Every superhero has been given a power value by the Felicity Committee. The avengers crew wants to maximize the average power of the superheroes in their team by performing certain operations.

Initially, there are $$$n$$$ superheroes in avengers team having powers $$$a_1, a_2, \ldots, a_n$$$, respectively. In one operation, they can remove one superhero from their team (if there are at least two) or they can increase the power of a superhero by $$$1$$$. They can do at most $$$m$$$ operations. Also, on a particular superhero at most $$$k$$$ operations can be done.

Can you help the avengers team to maximize the average power of their crew?

## Input Format
The first line contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n \le 10^{5}$$$, $$$1 \le k \le 10^{5}$$$, $$$1 \le m \le 10^{7}$$$) — the number of superheroes, the maximum number of times you can increase power of a particular superhero, and the total maximum number of operations.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{6}$$$) — the initial powers of the superheroes in the cast of avengers.

## Output Format
Output a single number — the maximum final average power.

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
2 4 6
4 7
```
```output
11.00000000000000000000
```
-----
```input
4 2 6
1 3 2 3
```
```output
5.00000000000000000000
```

## Note
In the first example, the maximum average is obtained by deleting the first element and increasing the second element four times.

In the second sample, one of the ways to achieve maximum average is to delete the first and the third element and increase the second and the fourth elements by $$$2$$$ each.

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
Thanos wants to destroy the avengers base, but he needs to destroy the avengers along with their base.

Let we represent their base with an array, where each position can be occupied by many avengers, but one avenger can occupy only one position. Length of their base is a perfect power of $$$2$$$. Thanos wants to destroy the base using minimum power. He starts with the whole base and in one step he can do either of following:

- if the current length is at least $$$2$$$, divide the base into $$$2$$$ equal halves and destroy them separately, or
- burn the current base. If it contains no avenger in it, it takes $$$A$$$ amount of power, otherwise it takes his $$$B \cdot n_a \cdot l$$$ amount of power, where $$$n_a$$$ is the number of avengers and $$$l$$$ is the length of the current base.

## Input Format
The first line contains four integers $$$n$$$, $$$k$$$, $$$A$$$ and $$$B$$$ ($$$1 \leq n \leq 30$$$, $$$1 \leq k \leq 10^5$$$, $$$1 \leq A,B \leq 10^4$$$), where $$$2^n$$$ is the length of the base, $$$k$$$ is the number of avengers and $$$A$$$ and $$$B$$$ are the constants explained in the question.

The second line contains $$$k$$$ integers $$$a_{1}, a_{2}, a_{3}, \ldots, a_{k}$$$ ($$$1 \leq a_{i} \leq 2^n$$$), where $$$a_{i}$$$ represents the position of avenger in the base.

## Output Format
Output one integer — the minimum power needed to destroy the avengers base.

## Examples
```input
2 2 1 2
1 3
```
```output
6
```
-----
```input
3 2 1 2
1 7
```
```output
8
```

## Note
Consider the first example.

One option for Thanos is to burn the whole base $$$1-4$$$ with power $$$2 \cdot 2 \cdot 4 = 16$$$.

Otherwise he can divide the base into two parts $$$1-2$$$ and $$$3-4$$$.

For base $$$1-2$$$, he can either burn it with power $$$2 \cdot 1 \cdot 2 = 4$$$ or divide it into $$$2$$$ parts $$$1-1$$$ and $$$2-2$$$.

For base $$$1-1$$$, he can burn it with power $$$2 \cdot 1 \cdot 1 = 2$$$. For $$$2-2$$$, he can destroy it with power $$$1$$$, as there are no avengers. So, the total power for destroying $$$1-2$$$ is $$$2 + 1 = 3$$$, which is less than $$$4$$$.

Similarly, he needs $$$3$$$ power to destroy $$$3-4$$$. The total minimum power needed is $$$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: 512.0 MB

# Problem
There is a colony of villains with several holes aligned in a row, where each hole contains exactly one villain.

Each colony arrangement can be expressed as a string of even length, where the $$$i$$$-th character of the string represents the type of villain in the $$$i$$$-th hole.

Iron Man can destroy a colony only if the colony arrangement is such that all villains of a certain type either live in the first half of the colony or in the second half of the colony.

His assistant Jarvis has a special power. It can swap villains of any two holes, i.e. swap any two characters in the string; he can do this operation any number of times.

Now Iron Man asks Jarvis $$$q$$$ questions. In each question, he gives Jarvis two numbers $$$x$$$ and $$$y$$$. Jarvis has to tell Iron Man the number of distinct colony arrangements he can create from the original one using his powers such that all villains having the same type as those originally living in $$$x$$$-th hole or $$$y$$$-th hole live in the same half and the Iron Man can destroy that colony arrangement.

Two colony arrangements are considered to be different if there exists a hole such that different types of villains are present in that hole in the arrangements.

## Input Format
The first line contains a string $$$s$$$ ($$$2 \le |s| \le 10^{5}$$$), representing the initial colony arrangement. String $$$s$$$ can have both lowercase and uppercase English letters and its length is even.

The second line contains a single integer $$$q$$$ ($$$1 \le q \le 10^{5}$$$) — the number of questions.

The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le |s|$$$, $$$x_i \ne y_i$$$) — the two numbers given to the Jarvis for the $$$i$$$-th question.

## Output Format
For each question output the number of arrangements possible modulo $$$10^9+7$$$.

## Examples
```input
abba
2
1 4
1 2
```
```output
2
0
```
-----
```input
AAaa
2
1 2
1 3
```
```output
2
0
```
-----
```input
abcd
1
1 3
```
```output
8
```

## Note
Consider the first example. For the first question, the possible arrangements are "aabb" and "bbaa", and for the second question, index $$$1$$$ contains 'a' and index $$$2$$$ contains 'b' and there is no valid arrangement in which all 'a' and 'b' are in the same half.

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
Arkady invited Anna for a dinner to a sushi restaurant. The restaurant is a bit unusual: it offers $$$n$$$ pieces of sushi aligned in a row, and a customer has to choose a continuous subsegment of these sushi to buy.

The pieces of sushi are of two types: either with tuna or with eel. Let's denote the type of the $$$i$$$-th from the left sushi as $$$t_i$$$, where $$$t_i = 1$$$ means it is with tuna, and $$$t_i = 2$$$ means it is with eel.

Arkady does not like tuna, Anna does not like eel. Arkady wants to choose such a continuous subsegment of sushi that it has equal number of sushi of each type and each half of the subsegment has only sushi of one type. For example, subsegment $$$[2, 2, 2, 1, 1, 1]$$$ is valid, but subsegment $$$[1, 2, 1, 2, 1, 2]$$$ is not, because both halves contain both types of sushi.

Find the length of the longest continuous subsegment of sushi Arkady can buy.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 100\,000$$$) — the number of pieces of sushi.

The second line contains $$$n$$$ integers $$$t_1$$$, $$$t_2$$$, ..., $$$t_n$$$ ($$$t_i = 1$$$, denoting a sushi with tuna or $$$t_i = 2$$$, denoting a sushi with eel), representing the types of sushi from left to right.

It is guaranteed that there is at least one piece of sushi of each type. Note that it means that there is at least one valid continuous segment.

## Output Format
Print a single integer — the maximum length of a valid continuous segment.

## Examples
```input
7
2 2 2 1 1 2 2
```
```output
4
```
-----
```input
6
1 2 1 2 1 2
```
```output
2
```
-----
```input
9
2 2 1 1 1 2 2 2 2
```
```output
6
```

## Note
In the first example Arkady can choose the subsegment $$$[2, 2, 1, 1]$$$ or the subsegment $$$[1, 1, 2, 2]$$$ with length $$$4$$$.

In the second example there is no way but to choose one of the subsegments $$$[2, 1]$$$ or $$$[1, 2]$$$ with length $$$2$$$.

In the third example Arkady's best choice is the subsegment $$$[1, 1, 1, 2, 2, 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 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
Polycarp is a head of a circus troupe. There are $$$n$$$ — an even number — artists in the troupe. It is known whether the $$$i$$$-th artist can perform as a clown (if yes, then $$$c_i = 1$$$, otherwise $$$c_i = 0$$$), and whether they can perform as an acrobat (if yes, then $$$a_i = 1$$$, otherwise $$$a_i = 0$$$).

Split the artists into two performances in such a way that:

- each artist plays in exactly one performance,
- the number of artists in the two performances is equal (i.e. equal to $$$\frac{n}{2}$$$),
- the number of artists that can perform as clowns in the first performance is the same as the number of artists that can perform as acrobats in the second performance.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 5\,000$$$, $$$n$$$ is even) — the number of artists in the troupe.

The second line contains $$$n$$$ digits $$$c_1 c_2 \ldots c_n$$$, the $$$i$$$-th of which is equal to $$$1$$$ if the $$$i$$$-th artist can perform as a clown, and $$$0$$$ otherwise.

The third line contains $$$n$$$ digits $$$a_1 a_2 \ldots a_n$$$, the $$$i$$$-th of which is equal to $$$1$$$, if the $$$i$$$-th artist can perform as an acrobat, and $$$0$$$ otherwise.

## Output Format
Print $$$\frac{n}{2}$$$ distinct integers — the indices of the artists that should play in the first performance.

If there are multiple answers, print any.

If there is no solution, print a single integer $$$-1$$$.

## Examples
```input
4
0011
0101
```
```output
1 4
```
-----
```input
6
000000
111111
```
```output
-1
```
-----
```input
4
0011
1100
```
```output
4 3
```
-----
```input
8
00100101
01111100
```
```output
1 2 3 6
```

## Note
In the first example, one of the possible divisions into two performances is as follows: in the first performance artists $$$1$$$ and $$$4$$$ should take part. Then the number of artists in the first performance who can perform as clowns is equal to $$$1$$$. And the number of artists in the second performance who can perform as acrobats is $$$1$$$ as well.

In the second example, the division is not possible.

In the third example, one of the possible divisions is as follows: in the first performance artists $$$3$$$ and $$$4$$$ should take part. Then in the first performance there are $$$2$$$ artists who can perform as clowns. And the number of artists in the second performance who can perform as acrobats is $$$2$$$ as well.

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
Traveling around the world you noticed that many shop owners raise prices to inadequate values if the see you are a foreigner.

You define inadequate numbers as follows:

- all integers from $$$1$$$ to $$$9$$$ are inadequate;
- for an integer $$$x \ge 10$$$ to be inadequate, it is required that the integer $$$\lfloor x / 10 \rfloor$$$ is inadequate, but that's not the only condition. Let's sort all the inadequate integers. Let $$$\lfloor x / 10 \rfloor$$$ have number $$$k$$$ in this order. Then, the integer $$$x$$$ is inadequate only if the last digit of $$$x$$$ is strictly less than the reminder of division of $$$k$$$ by $$$11$$$.

Here $$$\lfloor x / 10 \rfloor$$$ denotes $$$x/10$$$ rounded down.

Thus, if $$$x$$$ is the $$$m$$$-th in increasing order inadequate number, and $$$m$$$ gives the remainder $$$c$$$ when divided by $$$11$$$, then integers $$$10 \cdot x + 0, 10 \cdot x + 1 \ldots, 10 \cdot x + (c - 1)$$$ are inadequate, while integers $$$10 \cdot x + c, 10 \cdot x + (c + 1), \ldots, 10 \cdot x + 9$$$ are not inadequate.

The first several inadequate integers are $$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32 \ldots$$$. After that, since $$$4$$$ is the fourth inadequate integer, $$$40, 41, 42, 43$$$ are inadequate, while $$$44, 45, 46, \ldots, 49$$$ are not inadequate; since $$$10$$$ is the $$$10$$$-th inadequate number, integers $$$100, 101, 102, \ldots, 109$$$ are all inadequate. And since $$$20$$$ is the $$$11$$$-th inadequate number, none of $$$200, 201, 202, \ldots, 209$$$ is inadequate.

You wrote down all the prices you have seen in a trip. Unfortunately, all integers got concatenated in one large digit string $$$s$$$ and you lost the bounds between the neighboring integers. You are now interested in the number of substrings of the resulting string that form an inadequate number. If a substring appears more than once at different positions, all its appearances are counted separately.

## Input Format
The only line contains the string $$$s$$$ ($$$1 \le |s| \le 10^5$$$), consisting only of digits. It is guaranteed that the first digit of $$$s$$$ is not zero.

## Output Format
In the only line print the number of substrings of $$$s$$$ that form an inadequate number.

## Examples
```input
4021
```
```output
6
```
-----
```input
110
```
```output
3
```

## Note
In the first example the inadequate numbers in the string are $$$1, 2, 4, 21, 40, 402$$$.

In the second example the inadequate numbers in the string are $$$1$$$ and $$$10$$$, and $$$1$$$ appears twice (on the first and on the second positions).

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
Alice has a string $$$s$$$. She really likes the letter "a". She calls a string good if strictly more than half of the characters in that string are "a"s. For example "aaabb", "axaa" are good strings, and "baca", "awwwa", "" (empty string) are not.

Alice can erase some characters from her string $$$s$$$. She would like to know what is the longest string remaining after erasing some characters (possibly zero) to get a good string. It is guaranteed that the string has at least one "a" in it, so the answer always exists.

## Input Format
The first line contains a string $$$s$$$ ($$$1 \leq |s| \leq 50$$$) consisting of lowercase English letters. It is guaranteed that there is at least one "a" in $$$s$$$.

## Output Format
Print a single integer, the length of the longest good string that Alice can get after erasing some characters from $$$s$$$.

## Examples
```input
xaxxxxa
```
```output
3
```
-----
```input
aaabaa
```
```output
6
```

## Note
In the first example, it's enough to erase any four of the "x"s. The answer is $$$3$$$ since that is the maximum number of characters that can remain.

In the second example, we don't need to erase any characters.

Now solve the problem and return the code.