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
William has array of $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$. He can perform the following sequence of operations any number of times:

1. Pick any two items from array $$$a_i$$$ and $$$a_j$$$, where $$$a_i$$$ must be a multiple of $$$2$$$
2. $$$a_i = \frac{a_i}{2}$$$
3. $$$a_j = a_j \cdot 2$$$

Help William find the maximal sum of array elements, which he can get by performing the sequence of operations described above.

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

The first line of each test case contains an integer $$$n$$$ $$$(1 \le n \le 15)$$$, the number of elements in William's array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i < 16)$$$, the contents of William's array.

## Output Format
For each test case output the maximal sum of array elements after performing an optimal sequence of operations.

## Examples
```input
5
3
6 4 2
5
1 2 3 4 5
1
10
3
2 3 4
15
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
```
```output
50
46
10
26
35184372088846
```

## Note
In the first example test case the optimal sequence would be:

1. Pick $$$i = 2$$$ and $$$j = 1$$$. After performing a sequence of operations $$$a_2 = \frac{4}{2} = 2$$$ and $$$a_1 = 6 \cdot 2 = 12$$$, making the array look as: [12, 2, 2].
2. Pick $$$i = 2$$$ and $$$j = 1$$$. After performing a sequence of operations $$$a_2 = \frac{2}{2} = 1$$$ and $$$a_1 = 12 \cdot 2 = 24$$$, making the array look as: [24, 1, 2].
3. Pick $$$i = 3$$$ and $$$j = 1$$$. After performing a sequence of operations $$$a_3 = \frac{2}{2} = 1$$$ and $$$a_1 = 24 \cdot 2 = 48$$$, making the array look as: [48, 1, 1].

The final answer $$$48 + 1 + 1 = 50$$$.

In the third example test case there is no way to change the sum of elements, so the answer is $$$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 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
William arrived at a conference dedicated to cryptocurrencies. Networking, meeting new people, and using friends' connections are essential to stay up to date with the latest news from the world of cryptocurrencies.

The conference has $$$n$$$ participants, who are initially unfamiliar with each other. William can introduce any two people, $$$a$$$ and $$$b$$$, who were not familiar before, to each other.

William has $$$d$$$ conditions, $$$i$$$'th of which requires person $$$x_i$$$ to have a connection to person $$$y_i$$$. Formally, two people $$$x$$$ and $$$y$$$ have a connection if there is such a chain $$$p_1=x, p_2, p_3, \dots, p_k=y$$$ for which for all $$$i$$$ from $$$1$$$ to $$$k - 1$$$ it's true that two people with numbers $$$p_i$$$ and $$$p_{i + 1}$$$ know each other.

For every $$$i$$$ ($$$1 \le i \le d$$$) William wants you to calculate the maximal number of acquaintances one person can have, assuming that William satisfied all conditions from $$$1$$$ and up to and including $$$i$$$ and performed exactly $$$i$$$ introductions. The conditions are being checked after William performed $$$i$$$ introductions. The answer for each $$$i$$$ must be calculated independently. It means that when you compute an answer for $$$i$$$, you should assume that no two people have been introduced to each other yet.

## Input Format
The first line contains two integers $$$n$$$ and $$$d$$$ ($$$2 \le n \le 10^3, 1 \le d \le n - 1$$$), the number of people, and number of conditions, respectively.

Each of the next $$$d$$$ lines each contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n, x_i \neq y_i$$$), the numbers of people which must have a connection according to condition $$$i$$$.

## Output Format
Output $$$d$$$ integers. $$$i$$$th number must equal the number of acquaintances the person with the maximal possible acquaintances will have, if William performed $$$i$$$ introductions and satisfied the first $$$i$$$ conditions.

## Examples
```input
7 6
1 2
3 4
2 4
7 6
6 5
1 7
```
```output
1
1
3
3
3
6
```
-----
```input
10 8
1 2
2 3
3 4
1 4
6 7
8 9
8 10
1 4
```
```output
1
2
3
4
5
5
6
8
```

## Note
The explanation for the first test case:

In this explanation, the circles and the numbers in them denote a person with the corresponding number. The line denotes that William introduced two connected people. The person marked with red has the most acquaintances. These are not the only correct ways to introduce people.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

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

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

Execution time limit: 6.0 seconds
Memory limit: 256.0 MB

# Problem
William has two arrays of numbers $$$a_1, a_2, \dots, a_n$$$ and $$$b_1, b_2, \dots, b_m$$$. The arrays satisfy the conditions of being convex. Formally an array $$$c$$$ of length $$$k$$$ is considered convex if $$$c_i - c_{i - 1} < c_{i + 1} - c_i$$$ for all $$$i$$$ from $$$2$$$ to $$$k - 1$$$ and $$$c_1 < c_2$$$.

Throughout William's life he observed $$$q$$$ changes of two types happening to the arrays:

1. Add the arithmetic progression $$$d, d \cdot 2, d \cdot 3, \dots, d \cdot k$$$ to the suffix of the array $$$a$$$ of length $$$k$$$. The array after the change looks like this: $$$[a_1, a_2, \dots, a_{n - k}, a_{n - k + 1} + d, a_{n - k + 2} + d \cdot 2, \dots, a_n + d \cdot k]$$$.
2. The same operation, but for array $$$b$$$.

After each change a matrix $$$d$$$ is created from arrays $$$a$$$ and $$$b$$$, of size $$$n \times m$$$, where $$$d_{i, j}=a_i + b_j$$$. William wants to get from cell ($$$1, 1$$$) to cell ($$$n, m$$$) of this matrix. From cell ($$$x, y$$$) he can only move to cells ($$$x + 1, y$$$) and ($$$x, y + 1$$$). The length of a path is calculated as the sum of numbers in cells visited by William, including the first and the last cells.

After each change William wants you to help find out the minimal length of the path he could take.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$2 \le n \le 100, 2 \le m \le 10^5$$$, $$$1 \le q \le 10^5$$$), the sizes of the arrays and the number of changes.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$), the contents of array $$$a$$$.

The third line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^{12}$$$), the contents of array $$$b$$$.

Each of the next $$$q$$$ lines contains three integers $$$type$$$, $$$k$$$ and $$$d$$$ ($$$1 \le type \le 2$$$, if $$$type = 1$$$, then $$$1 \le k \le n$$$ otherwise $$$1 \le k \le m$$$, $$$1 \le d \le 10^3$$$).

## Output Format
After each change, output one integer, the minimum length of the path in the constructed matrix.

## Examples
```input
5 3 4
1 2 4 7 11
5 7 10
1 3 2
2 2 5
1 5 4
2 1 7
```
```output
98
128
219
229
```
-----
```input
5 6 7
4 9 22 118 226
7 94 238 395 565 738
2 1 95
1 4 54
1 2 5
1 2 87
2 6 62
2 1 143
1 1 77
```
```output
3639
5122
5162
5617
7663
7806
7960
```

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
Polycarp has an integer $$$n$$$ that doesn't contain the digit 0. He can do the following operation with his number several (possibly zero) times:

- Reverse the prefix of length $$$l$$$ (in other words, $$$l$$$ leftmost digits) of $$$n$$$. So, the leftmost digit is swapped with the $$$l$$$-th digit from the left, the second digit from the left swapped with ($$$l-1$$$)-th left, etc. For example, if $$$n=123456789$$$ and $$$l=5$$$, then the new value of $$$n$$$ will be $$$543216789$$$.

Note that for different operations, the values of $$$l$$$ can be different. The number $$$l$$$ can be equal to the length of the number $$$n$$$ — in this case, the whole number $$$n$$$ is reversed.

Polycarp loves even numbers. Therefore, he wants to make his number even. At the same time, Polycarp is very impatient. He wants to do as few operations as possible.

Help Polycarp. Determine the minimum number of operations he needs to perform with the number $$$n$$$ to make it even or determine that this is impossible.

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

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

Each of the following $$$t$$$ lines contains one integer $$$n$$$ ($$$1 \le n < 10^9$$$). It is guaranteed that the given number doesn't contain the digit 0.

## Output Format
Print $$$t$$$ lines. On each line print one integer — the answer to the corresponding test case. If it is impossible to make an even number, print -1.

## Examples
```input
4
3876
387
4489
3
```
```output
0
2
1
-1
```

## Note
In the first test case, $$$n=3876$$$, which is already an even number. Polycarp doesn't need to do anything, so the answer is $$$0$$$.

In the second test case, $$$n=387$$$. Polycarp needs to do $$$2$$$ operations:

1. Select $$$l=2$$$ and reverse the prefix $$$\underline{38}7$$$. The number $$$n$$$ becomes $$$837$$$. This number is odd.
2. Select $$$l=3$$$ and reverse the prefix $$$\underline{837}$$$. The number $$$n$$$ becomes $$$738$$$. This number is even.

It can be shown that $$$2$$$ is the minimum possible number of operations that Polycarp needs to do with his number to make it even.

In the third test case, $$$n=4489$$$. Polycarp can reverse the whole number (choose a prefix of length $$$l=4$$$). It will become $$$9844$$$ and this is an even number.

In the fourth test case, $$$n=3$$$. No matter how hard Polycarp tried, he would not be able to make an even number.

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 All-Berland Team Programming Contest will take place very soon. This year, teams of four are allowed to participate.

There are $$$a$$$ programmers and $$$b$$$ mathematicians at Berland State University. How many maximum teams can be made if:

- each team must consist of exactly $$$4$$$ students,
- teams of $$$4$$$ mathematicians or $$$4$$$ programmers are unlikely to perform well, so the decision was made not to compose such teams.

Thus, each team must have at least one programmer and at least one mathematician.

Print the required maximum number of teams. Each person can be a member of no more than one team.

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

This is followed by descriptions of $$$t$$$ sets, one per line. Each set is given by two integers $$$a$$$ and $$$b$$$ ($$$0 \le a,b \le 10^9$$$).

## Output Format
Print $$$t$$$ lines. Each line must contain the answer to the corresponding set of input data — the required maximum number of teams.

## Examples
```input
6
5 5
10 1
2 3
0 0
17 2
1000000000 1000000000
```
```output
2
1
1
0
2
500000000
```

## Note
In the first test case of the example, two teams can be composed. One way to compose two teams is to compose two teams of $$$2$$$ programmers and $$$2$$$ mathematicians.

In the second test case of the example, only one team can be composed: $$$3$$$ programmers and $$$1$$$ mathematician in the team.

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 had $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ arranged in a circle. For each pair of neighboring numbers ($$$a_1$$$ and $$$a_2$$$, $$$a_2$$$ and $$$a_3$$$, ..., $$$a_{n - 1}$$$ and $$$a_n$$$, and $$$a_n$$$ and $$$a_1$$$), you wrote down: are the numbers in the pair equal or not.

Unfortunately, you've lost a piece of paper with the array $$$a$$$. Moreover, you are afraid that even information about equality of neighboring elements may be inconsistent. So, you are wondering: is there any array $$$a$$$ which is consistent with information you have about equality or non-equality of corresponding pairs?

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

The first and only line of each test case contains a non-empty string $$$s$$$ consisting of characters E and/or N. The length of $$$s$$$ is equal to the size of array $$$n$$$ and $$$2 \le n \le 50$$$. For each $$$i$$$ from $$$1$$$ to $$$n$$$:

- if $$$s_i =$$$ E then $$$a_i$$$ is equal to $$$a_{i + 1}$$$ ($$$a_n = a_1$$$ for $$$i = n$$$);
- if $$$s_i =$$$ N then $$$a_i$$$ is not equal to $$$a_{i + 1}$$$ ($$$a_n \neq a_1$$$ for $$$i = n$$$).

## Output Format
For each test case, print YES if it's possible to choose array $$$a$$$ that are consistent with information from $$$s$$$ you know. Otherwise, print NO.

It can be proved, that if there exists some array $$$a$$$, then there exists an array $$$a$$$ of positive integers with values less or equal to $$$10^9$$$.

## Examples
```input
4
EEE
EN
ENNEENE
NENN
```
```output
YES
NO
YES
YES
```

## Note
In the first test case, you can choose, for example, $$$a_1 = a_2 = a_3 = 5$$$.

In the second test case, there is no array $$$a$$$, since, according to $$$s_1$$$, $$$a_1$$$ is equal to $$$a_2$$$, but, according to $$$s_2$$$, $$$a_2$$$ is not equal to $$$a_1$$$.

In the third test case, you can, for example, choose array $$$a = [20, 20, 4, 50, 50, 50, 20]$$$.

In the fourth test case, you can, for example, choose $$$a = [1, 3, 3, 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 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
A rectangle with its opposite corners in $$$(0, 0)$$$ and $$$(w, h)$$$ and sides parallel to the axes is drawn on a plane.

You are given a list of lattice points such that each point lies on a side of a rectangle but not in its corner. Also, there are at least two points on every side of a rectangle.

Your task is to choose three points in such a way that:

- exactly two of them belong to the same side of a rectangle;
- the area of a triangle formed by them is maximum possible.

Print the doubled area of this triangle. It can be shown that the doubled area of any triangle formed by lattice points is always an integer.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains two integers $$$w$$$ and $$$h$$$ ($$$3 \le w, h \le 10^6$$$) — the coordinates of the corner of a rectangle.

The next two lines contain the description of the points on two horizontal sides. First, an integer $$$k$$$ ($$$2 \le k \le 2 \cdot 10^5$$$) — the number of points. Then, $$$k$$$ integers $$$x_1 < x_2 < \dots < x_k$$$ ($$$0 < x_i < w$$$) — the $$$x$$$ coordinates of the points in the ascending order. The $$$y$$$ coordinate for the first line is $$$0$$$ and for the second line is $$$h$$$.

The next two lines contain the description of the points on two vertical sides. First, an integer $$$k$$$ ($$$2 \le k \le 2 \cdot 10^5$$$) — the number of points. Then, $$$k$$$ integers $$$y_1 < y_2 < \dots < y_k$$$ ($$$0 < y_i < h$$$) — the $$$y$$$ coordinates of the points in the ascending order. The $$$x$$$ coordinate for the first line is $$$0$$$ and for the second line is $$$w$$$.

The total number of points on all sides in all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase print a single integer — the doubled maximum area of a triangle formed by such three points that exactly two of them belong to the same side.

## Examples
```input
3
5 8
2 1 2
3 2 3 4
3 1 4 6
2 4 5
10 7
2 3 9
2 1 7
3 1 3 4
3 4 5 6
11 5
3 1 6 8
3 3 6 8
3 1 3 4
2 2 4
```
```output
25
42
35
```

## Note
The points in the first testcase of the example:

- $$$(1, 0)$$$, $$$(2, 0)$$$;
- $$$(2, 8)$$$, $$$(3, 8)$$$, $$$(4, 8)$$$;
- $$$(0, 1)$$$, $$$(0, 4)$$$, $$$(0, 6)$$$;
- $$$(5, 4)$$$, $$$(5, 5)$$$.

The largest triangle is formed by points $$$(0, 1)$$$, $$$(0, 6)$$$ and $$$(5, 4)$$$ — its area is $$$\frac{25}{2}$$$. Thus, the doubled area is $$$25$$$. Two points that are on the same side are: $$$(0, 1)$$$ and $$$(0, 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
You are given an integer $$$k$$$ and a string $$$s$$$ that consists only of characters 'a' (a lowercase Latin letter) and '*' (an asterisk).

Each asterisk should be replaced with several (from $$$0$$$ to $$$k$$$ inclusive) lowercase Latin letters 'b'. Different asterisk can be replaced with different counts of letter 'b'.

The result of the replacement is called a BA-string.

Two strings $$$a$$$ and $$$b$$$ are different if they either have different lengths or there exists such a position $$$i$$$ that $$$a_i \neq b_i$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Now consider all different BA-strings and find the $$$x$$$-th lexicographically smallest of them.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of testcases.

The first line of each testcase contains three integers $$$n$$$, $$$k$$$ and $$$x$$$ ($$$1 \le n \le 2000$$$; $$$0 \le k \le 2000$$$; $$$1 \le x \le 10^{18}$$$). $$$n$$$ is the length of string $$$s$$$.

The second line of each testcase is a string $$$s$$$. It consists of $$$n$$$ characters, each of them is either 'a' (a lowercase Latin letter) or '*' (an asterisk).

The sum of $$$n$$$ over all testcases doesn't exceed $$$2000$$$. For each testcase $$$x$$$ doesn't exceed the total number of different BA-strings. String $$$s$$$ contains at least one character 'a'.

## Output Format
For each testcase, print a single string, consisting only of characters 'b' and 'a' (lowercase Latin letters) — the $$$x$$$-th lexicographically smallest BA-string.

## Examples
```input
3
2 4 3
a*
4 1 3
a**a
6 3 20
**a***
```
```output
abb
abba
babbbbbbbbb
```

## Note
In the first testcase of the example, BA-strings ordered lexicographically are:

1. a
2. ab
3. abb
4. abbb
5. abbbb

In the second testcase of the example, BA-strings ordered lexicographically are:

1. aa
2. aba
3. abba

Note that string "aba" is only counted once, even though there are two ways to replace asterisks with characters 'b' to get it.

Now solve the problem and return the code.