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: 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 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
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 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
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 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
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 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
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.
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
You are given an array $$$a$$$ of length $$$n$$$, which initially is a permutation of numbers from $$$1$$$ to $$$n$$$. In one operation, you can choose an index $$$i$$$ ($$$1 \leq i < n$$$) such that $$$a_i < a_{i + 1}$$$, and remove either $$$a_i$$$ or $$$a_{i + 1}$$$ from the array (after the removal, the remaining parts are concatenated).

For example, if you have the array $$$[1, 3, 2]$$$, you can choose $$$i = 1$$$ (since $$$a_1 = 1 < a_2 = 3$$$), then either remove $$$a_1$$$ which gives the new array $$$[3, 2]$$$, or remove $$$a_2$$$ which gives the new array $$$[1, 2]$$$.

Is it possible to make the length of this array equal to $$$1$$$ with these operations?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$)  — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq n$$$, $$$a_i$$$ are pairwise distinct) — elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, output on a single line the word "YES" if it is possible to reduce the array to a single element using the aforementioned operation, or "NO" if it is impossible to do so.

## Examples
```input
4
3
1 2 3
4
3 1 2 4
3
2 3 1
6
2 4 6 1 3 5
```
```output
YES
YES
NO
YES
```

## Note
For the first two test cases and the fourth test case, we can operate as follow (the bolded elements are the pair chosen for that operation):

$$$[\text{1}, \textbf{2}, \textbf{3}] \rightarrow [\textbf{1}, \textbf{2}] \rightarrow [\text{1}]$$$

$$$[\text{3}, \textbf{1}, \textbf{2}, \text{4}] \rightarrow [\text{3}, \textbf{1}, \textbf{4}] \rightarrow [\textbf{3}, \textbf{4}] \rightarrow [\text{4}]$$$

$$$[\textbf{2}, \textbf{4}, \text{6}, \text{1}, \text{3}, \text{5}] \rightarrow [\textbf{4}, \textbf{6}, \text{1}, \text{3}, \text{5}] \rightarrow [\text{4}, \text{1}, \textbf{3}, \textbf{5}] \rightarrow [\text{4}, \textbf{1}, \textbf{5}] \rightarrow [\textbf{4}, \textbf{5}] \rightarrow [\text{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 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
You are given a tree with $$$n$$$ vertices. You are allowed to modify the structure of the tree through the following multi-step operation:

1. Choose three vertices $$$a$$$, $$$b$$$, and $$$c$$$ such that $$$b$$$ is adjacent to both $$$a$$$ and $$$c$$$.
2. For every vertex $$$d$$$ other than $$$b$$$ that is adjacent to $$$a$$$, remove the edge connecting $$$d$$$ and $$$a$$$ and add the edge connecting $$$d$$$ and $$$c$$$.
3. Delete the edge connecting $$$a$$$ and $$$b$$$ and add the edge connecting $$$a$$$ and $$$c$$$.

As an example, consider the following tree:

The following diagram illustrates the sequence of steps that happen when we apply an operation to vertices $$$2$$$, $$$4$$$, and $$$5$$$:

It can be proven that after each operation, the resulting graph is still a tree.

Find the minimum number of operations that must be performed to transform the tree into a star. A star is a tree with one vertex of degree $$$n - 1$$$, called its center, and $$$n - 1$$$ vertices of degree $$$1$$$.

## Input Format
The first line contains an integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$)  — the number of vertices in the tree.

The $$$i$$$-th of the following $$$n - 1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) denoting that there exists an edge connecting vertices $$$u_i$$$ and $$$v_i$$$. It is guaranteed that the given edges form a tree.

## Output Format
Print a single integer  — the minimum number of operations needed to transform the tree into a star.

It can be proven that under the given constraints, it is always possible to transform the tree into a star using at most $$$10^{18}$$$ operations.

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

## Note
The first test case corresponds to the tree shown in the statement. As we have seen before, we can transform the tree into a star with center at vertex $$$5$$$ by applying a single operation to vertices $$$2$$$, $$$4$$$, and $$$5$$$.

In the second test case, the given tree is already a star with the center at vertex $$$4$$$, so no operations have to be performed.

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

# Problem
A cubic lattice $$$L$$$ in $$$3$$$-dimensional euclidean space is a set of points defined in the following way: $$$$$$L=\{u \cdot \vec r_1 + v \cdot \vec r_2 + w \cdot \vec r_3\}_{u, v, w \in \mathbb Z}$$$$$$ Where $$$\vec r_1, \vec r_2, \vec r_3 \in \mathbb{Z}^3$$$ are some integer vectors such that:

- $$$\vec r_1$$$, $$$\vec r_2$$$ and $$$\vec r_3$$$ are pairwise orthogonal: $$$$$$\vec r_1 \cdot \vec r_2 = \vec r_1 \cdot \vec r_3 = \vec r_2 \cdot \vec r_3 = 0$$$$$$ Where $$$\vec a \cdot \vec b$$$ is a dot product of vectors $$$\vec a$$$ and $$$\vec b$$$.
- $$$\vec r_1$$$, $$$\vec r_2$$$ and $$$\vec r_3$$$ all have the same length: $$$$$$|\vec r_1| = |\vec r_2| = |\vec r_3| = r$$$$$$

You have to find a cubic lattice $$$L$$$ such that $$$A \subset L$$$ and $$$r$$$ is the maximum possible.

## Input Format
First line contains single integer $$$n$$$ ($$$1 \leq n \leq 10^4$$$) — the number of points in $$$A$$$.

The $$$i$$$-th of the following $$$n$$$ lines contains integers $$$x_i$$$, $$$y_i$$$, $$$z_i$$$ ($$$0 < x_i^2 + y_i^2 + z_i^2 \leq 10^{16}$$$) — coordinates of the $$$i$$$-th point.

It is guaranteed that $$$\gcd(g_1,g_2,\dots,g_n)=1$$$ where $$$g_i=\gcd(x_i,y_i,z_i)$$$.

## Output Format
In first line output a single integer $$$r^2$$$, the square of maximum possible $$$r$$$.

In following $$$3$$$ lines output coordinates of vectors $$$\vec r_1$$$, $$$\vec r_2$$$ and $$$\vec r_3$$$ respectively.

If there are multiple possible answers, output any.

## Examples
```input
2
1 2 3
1 2 1
```
```output
1
1 0 0
0 1 0
0 0 1
```
-----
```input
1
1 2 2
```
```output
9
2 -2 1
1 2 2
-2 -1 2
```
-----
```input
1
2 5 5
```
```output
9
-1 2 2
2 -1 2
2 2 -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
There are $$$n$$$ programmers that you want to split into several non-empty teams. The skill of the $$$i$$$-th programmer is $$$a_i$$$. You want to assemble the maximum number of teams from them. There is a restriction for each team: the number of programmers in the team multiplied by the minimum skill among all programmers in the team must be at least $$$x$$$.

Each programmer should belong to at most one team. Some programmers may be left without a team.

Calculate the maximum number of teams that you can assemble.

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

The first line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 10^5; 1 \le x \le 10^9$$$) — the number of programmers and the restriction of team skill respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the skill of the $$$i$$$-th programmer.

The sum of $$$n$$$ over all inputs does not exceed $$$10^5$$$.

## Output Format
For each test case print one integer — the maximum number of teams that you can assemble.

## Examples
```input
3
5 10
7 11 2 9 5
4 8
2 4 2 3
4 11
1 3 3 7
```
```output
2
1
0
```

Now solve the problem and return the code.