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

# Problem
You've been in love with Coronavirus-chan for a long time, but you didn't know where she lived until now. And just now you found out that she lives in a faraway place called Naha.

You immediately decided to take a vacation and visit Coronavirus-chan. Your vacation lasts exactly $$$x$$$ days and that's the exact number of days you will spend visiting your friend. You will spend exactly $$$x$$$ consecutive (successive) days visiting Coronavirus-chan.

They use a very unusual calendar in Naha: there are $$$n$$$ months in a year, $$$i$$$-th month lasts exactly $$$d_i$$$ days. Days in the $$$i$$$-th month are numbered from $$$1$$$ to $$$d_i$$$. There are no leap years in Naha.

The mood of Coronavirus-chan (and, accordingly, her desire to hug you) depends on the number of the day in a month. In particular, you get $$$j$$$ hugs if you visit Coronavirus-chan on the $$$j$$$-th day of the month.

You know about this feature of your friend and want to plan your trip to get as many hugs as possible (and then maybe you can win the heart of Coronavirus-chan).

Please note that your trip should not necessarily begin and end in the same year.

## Input Format
The first line of input contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of months in the year and the number of days you can spend with your friend.

The second line contains $$$n$$$ integers $$$d_1, d_2, \ldots, d_n$$$, $$$d_i$$$ is the number of days in the $$$i$$$-th month ($$$1 \le d_i \le 10^6$$$).

It is guaranteed that $$$1 \le x \le d_1 + d_2 + \ldots + d_n$$$.

## Output Format
Print one integer — the maximum number of hugs that you can get from Coronavirus-chan during the best vacation in your life.

## Examples
```input
3 2
1 3 1
```
```output
5
```
-----
```input
3 6
3 3 3
```
```output
12
```
-----
```input
5 6
4 2 3 1 3
```
```output
15
```

## Note
In the first test case, the numbers of the days in a year are (indices of days in a corresponding month) $$$\{1,1,2,3,1\}$$$. Coronavirus-chan will hug you the most if you come on the third day of the year: $$$2+3=5$$$ hugs.

In the second test case, the numbers of the days are $$$\{1,2,3,1,2,3,1,2,3\}$$$. You will get the most hugs if you arrive on the third day of the year: $$$3+1+2+3+1+2=12$$$ hugs.

In the third test case, the numbers of the days are $$$\{1,2,3,4,1,2, 1,2,3, 1, 1,2,3\}$$$. You will get the most hugs if you come on the twelfth day of the year: your friend will hug you $$$2+3+1+2+3+4=15$$$ times.

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
Levian works as an accountant in a large company. Levian knows how much the company has earned in each of the $$$n$$$ consecutive months — in the $$$i$$$-th month the company had income equal to $$$a_i$$$ (positive income means profit, negative income means loss, zero income means no change). Because of the general self-isolation, the first $$$\lceil \tfrac{n}{2} \rceil$$$ months income might have been completely unstable, but then everything stabilized and for the last $$$\lfloor \tfrac{n}{2} \rfloor$$$ months the income was the same.

Levian decided to tell the directors $$$n-k+1$$$ numbers — the total income of the company for each $$$k$$$ consecutive months. In other words, for each $$$i$$$ between $$$1$$$ and $$$n-k+1$$$ he will say the value $$$a_i + a_{i+1} + \ldots + a_{i + k - 1}$$$. For example, if $$$a=[-1, 0, 1, 2, 2]$$$ and $$$k=3$$$ he will say the numbers $$$0, 3, 5$$$.

Unfortunately, if at least one total income reported by Levian is not a profit (income $$$\le 0$$$), the directors will get angry and fire the failed accountant.

Save Levian's career: find any such $$$k$$$, that for each $$$k$$$ months in a row the company had made a profit, or report that it is impossible.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 5\cdot 10^5$$$) — the number of months for which Levian must account.

The second line contains $$$\lceil{\frac{n}{2}}\rceil$$$ integers $$$a_1, a_2, \ldots, a_{\lceil{\frac{n}{2}}\rceil}$$$, where $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the income of the company in the $$$i$$$-th month.

Third line contains a single integer $$$x$$$ ($$$-10^9 \le x \le 10^9$$$) — income in every month from $$$\lceil{\frac{n}{2}}\rceil + 1$$$ to $$$n$$$.

## Output Format
In a single line, print the appropriate integer $$$k$$$ or $$$-1$$$, if it does not exist.

If there are multiple possible answers, you can print any.

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

## Note
In the first example, $$$k=2$$$ and $$$k=3$$$ satisfy: in the first case, Levian will report the numbers $$$1, 1$$$, and in the second case — one number $$$3$$$.

In the second example, there is no such $$$k$$$.

In the third example, the only answer is $$$k=4$$$: he will report the numbers $$$1,2,3$$$.

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
Lee is going to fashionably decorate his house for a party, using some regular convex polygons...

Lee thinks a regular $$$n$$$-sided (convex) polygon is beautiful if and only if he can rotate it in such a way that at least one of its edges is parallel to the $$$OX$$$-axis and at least one of its edges is parallel to the $$$OY$$$-axis at the same time.

Recall that a regular $$$n$$$-sided polygon is a convex polygon with $$$n$$$ vertices such that all the edges and angles are equal.

Now he is shopping: the market has $$$t$$$ regular polygons. For each of them print YES if it is beautiful and NO otherwise.

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

Each of the next $$$t$$$ lines contains a single integer $$$n_i$$$ ($$$3 \le n_i \le 10^9$$$): it means that the $$$i$$$-th polygon is a regular $$$n_i$$$-sided polygon.

## Output Format
For each polygon, print YES if it's beautiful or NO otherwise (case insensitive).

## Examples
```input
4
3
4
12
1000000000
```
```output
NO
YES
YES
YES
```

## Note
In the example, there are $$$4$$$ polygons in the market. It's easy to see that an equilateral triangle (a regular $$$3$$$-sided polygon) is not beautiful, a square (a regular $$$4$$$-sided polygon) is beautiful and a regular $$$12$$$-sided polygon (is shown below) is beautiful 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Lee was cleaning his house for the party when he found a messy string under the carpets. Now he'd like to make it clean accurately and in a stylish way...

The string $$$s$$$ he found is a binary string of length $$$n$$$ (i. e. string consists only of 0-s and 1-s).

In one move he can choose two consecutive characters $$$s_i$$$ and $$$s_{i+1}$$$, and if $$$s_i$$$ is 1 and $$$s_{i + 1}$$$ is 0, he can erase exactly one of them (he can choose which one to erase but he can't erase both characters simultaneously). The string shrinks after erasing.

Lee can make an arbitrary number of moves (possibly zero) and he'd like to make the string $$$s$$$ as clean as possible. He thinks for two different strings $$$x$$$ and $$$y$$$, the shorter string is cleaner, and if they are the same length, then the lexicographically smaller string is cleaner.

Now you should answer $$$t$$$ test cases: for the $$$i$$$-th test case, print the cleanest possible string that Lee can get by doing some number of moves.

Small reminder: if we have two strings $$$x$$$ and $$$y$$$ of the same length then $$$x$$$ is lexicographically smaller than $$$y$$$ if there is a position $$$i$$$ such that $$$x_1 = y_1$$$, $$$x_2 = y_2$$$,..., $$$x_{i - 1} = y_{i - 1}$$$ and $$$x_i < y_i$$$.

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

Next $$$2t$$$ lines contain test cases — one per two lines.

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

The second line contains the binary string $$$s$$$. The string $$$s$$$ is a string of length $$$n$$$ which consists only of zeroes and ones.

It's guaranteed that sum of $$$n$$$ over test cases doesn't exceed $$$10^5$$$.

## Output Format
Print $$$t$$$ answers — one per test case.

The answer to the $$$i$$$-th test case is the cleanest string Lee can get after doing some number of moves (possibly zero).

## Examples
```input
5
10
0001111111
4
0101
8
11001101
10
1110000000
1
1
```
```output
0001111111
001
01
0
1
```

## Note
In the first test case, Lee can't perform any moves.

In the second test case, Lee should erase $$$s_2$$$.

In the third test case, Lee can make moves, for example, in the following order: 11001101 $$$\rightarrow$$$ 1100101 $$$\rightarrow$$$ 110101 $$$\rightarrow$$$ 10101 $$$\rightarrow$$$ 1101 $$$\rightarrow$$$ 101 $$$\rightarrow$$$ 01.

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
Lee just became Master in Codeforces, and so, he went out to buy some gifts for his friends. He bought $$$n$$$ integers, now it's time to distribute them between his friends rationally...

Lee has $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ in his backpack and he has $$$k$$$ friends. Lee would like to distribute all integers in his backpack between his friends, such that the $$$i$$$-th friend will get exactly $$$w_i$$$ integers and each integer will be handed over to exactly one friend.

Let's define the happiness of a friend as the sum of the maximum and the minimum integer he'll get.

Lee would like to make his friends as happy as possible, in other words, he'd like to maximize the sum of friends' happiness. Now he asks you to calculate the maximum sum of friends' happiness.

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

Next $$$3t$$$ lines contain test cases — one per three lines.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$) — the number of integers Lee has and the number of Lee's friends.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the integers Lee has.

The third line contains $$$k$$$ integers $$$w_1, w_2, \ldots, w_k$$$ ($$$1 \le w_i \le n$$$; $$$w_1 + w_2 + \ldots + w_k = n$$$) — the number of integers Lee wants to give to each friend.

It's guaranteed that the sum of $$$n$$$ over test cases is less than or equal to $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the maximum sum of happiness Lee can achieve.

## Examples
```input
3
4 2
1 13 7 17
1 3
6 2
10 10 10 10 11 11
3 3
4 4
1000000000 1000000000 1000000000 1000000000
1 1 1 1
```
```output
48
42
8000000000
```

## Note
In the first test case, Lee should give the greatest integer to the first friend (his happiness will be $$$17 + 17$$$) and remaining integers to the second friend (his happiness will be $$$13 + 1$$$).

In the second test case, Lee should give $$$\{10, 10, 11\}$$$ to the first friend and to the second friend, so the total happiness will be equal to $$$(11 + 10) + (11 + 10)$$$

In the third test case, Lee has four friends and four integers, it doesn't matter how he distributes the integers between his friends.

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
Lee tried so hard to make a good div.2 D problem to balance his recent contest, but it still doesn't feel good at all. Lee invented it so tediously slow that he managed to develop a phobia about div.2 D problem setting instead. And now he is hiding behind the bushes...

Let's define a Rooted Dead Bush (RDB) of level $$$n$$$ as a rooted tree constructed as described below.

A rooted dead bush of level $$$1$$$ is a single vertex. To construct an RDB of level $$$i$$$ we, at first, construct an RDB of level $$$i-1$$$, then for each vertex $$$u$$$:

- if $$$u$$$ has no children then we will add a single child to it;
- if $$$u$$$ has one child then we will add two children to it;
- if $$$u$$$ has more than one child, then we will skip it.

Rooted Dead Bushes of level $$$1$$$, $$$2$$$ and $$$3$$$.

Let's define a claw as a rooted tree with four vertices: one root vertex (called also as center) with three children. It looks like a claw:

The center of the claw is the vertex with label $$$1$$$.

Lee has a Rooted Dead Bush of level $$$n$$$. Initially, all vertices of his RDB are green.

In one move, he can choose a claw in his RDB, if all vertices in the claw are green and all vertices of the claw are children of its center, then he colors the claw's vertices in yellow.

He'd like to know the maximum number of yellow vertices he can achieve. Since the answer might be very large, print it modulo $$$10^9+7$$$.

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

Next $$$t$$$ lines contain test cases — one per line.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^6$$$) — the level of Lee's RDB.

## Output Format
For each test case, print a single integer — the maximum number of yellow vertices Lee can make modulo $$$10^9 + 7$$$.

## Examples
```input
7
1
2
3
4
5
100
2000000
```
```output
0
0
4
4
12
990998587
804665184
```

## Note
It's easy to see that the answer for RDB of level $$$1$$$ or $$$2$$$ is $$$0$$$.

The answer for RDB of level $$$3$$$ is $$$4$$$ since there is only one claw we can choose: $$$\{1, 2, 3, 4\}$$$.

The answer for RDB of level $$$4$$$ is $$$4$$$ since we can choose either single claw $$$\{1, 3, 2, 4\}$$$ or single claw $$$\{2, 7, 5, 6\}$$$. There are no other claws in the RDB of level $$$4$$$ (for example, we can't choose $$$\{2, 1, 7, 6\}$$$, since $$$1$$$ is not a child of center vertex $$$2$$$).

Rooted Dead Bush of level 4.

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
Lee is used to finish his stories in a stylish way, this time he barely failed it, but Ice Bear came and helped him. Lee is so grateful for it, so he decided to show Ice Bear his new game called "Critic"...

The game is a one versus one game. It has $$$t$$$ rounds, each round has two integers $$$s_i$$$ and $$$e_i$$$ (which are determined and are known before the game begins, $$$s_i$$$ and $$$e_i$$$ may differ from round to round). The integer $$$s_i$$$ is written on the board at the beginning of the corresponding round.

The players will take turns. Each player will erase the number on the board (let's say it was $$$a$$$) and will choose to write either $$$2 \cdot a$$$ or $$$a + 1$$$ instead. Whoever writes a number strictly greater than $$$e_i$$$ loses that round and the other one wins that round.

Now Lee wants to play "Critic" against Ice Bear, for each round he has chosen the round's $$$s_i$$$ and $$$e_i$$$ in advance. Lee will start the first round, the loser of each round will start the next round.

The winner of the last round is the winner of the game, and the loser of the last round is the loser of the game.

Determine if Lee can be the winner independent of Ice Bear's moves or not. Also, determine if Lee can be the loser independent of Ice Bear's moves or not.

## Input Format
The first line contains the integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of rounds the game has.

Then $$$t$$$ lines follow, each contains two integers $$$s_i$$$ and $$$e_i$$$ ($$$1 \le s_i \le e_i \le 10^{18}$$$) — the $$$i$$$-th round's information.

The rounds are played in the same order as given in input, $$$s_i$$$ and $$$e_i$$$ for all rounds are known to everyone before the game starts.

## Output Format
Print two integers.

The first one should be 1 if Lee can be the winner independent of Ice Bear's moves, and 0 otherwise.

The second one should be 1 if Lee can be the loser independent of Ice Bear's moves, and 0 otherwise.

## Examples
```input
3
5 8
1 4
3 10
```
```output
1 1
```
-----
```input
4
1 2
2 3
3 4
4 5
```
```output
0 0
```
-----
```input
1
1 1
```
```output
0 1
```
-----
```input
2
1 9
4 5
```
```output
0 0
```
-----
```input
2
1 2
2 8
```
```output
1 0
```
-----
```input
6
216986951114298167 235031205335543871
148302405431848579 455670351549314242
506251128322958430 575521452907339082
1 768614336404564650
189336074809158272 622104412002885672
588320087414024192 662540324268197150
```
```output
1 0
```

## Note
Remember, whoever writes an integer greater than $$$e_i$$$ loses.

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
A penguin Rocher has $$$n$$$ sticks. He has exactly one stick with length $$$i$$$ for all $$$1 \le i \le n$$$.

He can connect some sticks. If he connects two sticks that have lengths $$$a$$$ and $$$b$$$, he gets one stick with length $$$a + b$$$. Two sticks, that were used in the operation disappear from his set and the new connected stick appears in his set and can be used for the next connections.

He wants to create the maximum number of sticks that have the same length. It is not necessary to make all sticks have the same length, some sticks can have the other length. How many sticks with the equal length he can create?

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Next $$$t$$$ lines contain descriptions of test cases.

For each test case, the only line contains a single integer $$$n$$$ ($$$1 \le n \le 10^{9}$$$).

## Output Format
For each test case, print a single integer  — the answer to the problem.

## Examples
```input
4
1
2
3
4
```
```output
1
1
2
2
```

## Note
In the third case, he can connect two sticks with lengths $$$1$$$ and $$$2$$$ and he will get one stick with length $$$3$$$. So, he will have two sticks with lengths $$$3$$$.

In the fourth case, he can connect two sticks with lengths $$$1$$$ and $$$3$$$ and he will get one stick with length $$$4$$$. After that, he will have three sticks with lengths $$$\{2, 4, 4\}$$$, so two sticks have the same length, and one stick has the other length.

Now solve the problem and return the code.