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

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ positive integers. You can perform operations on it.

In one operation you can replace any element of the array $$$a_i$$$ with $$$\lfloor \frac{a_i}{2} \rfloor$$$, that is, by an integer part of dividing $$$a_i$$$ by $$$2$$$ (rounding down).

See if you can apply the operation some number of times (possible $$$0$$$) to make the array $$$a$$$ become a permutation of numbers from $$$1$$$ to $$$n$$$ —that is, so that it contains all numbers from $$$1$$$ to $$$n$$$, each exactly once.

For example, if $$$a = [1, 8, 25, 2]$$$, $$$n = 4$$$, then the answer is yes. You could do the following:

1. Replace $$$8$$$ with $$$\lfloor \frac{8}{2} \rfloor = 4$$$, then $$$a = [1, 4, 25, 2]$$$.
2. Replace $$$25$$$ with $$$\lfloor \frac{25}{2} \rfloor = 12$$$, then $$$a = [1, 4, 12, 2]$$$.
3. Replace $$$12$$$ with $$$\lfloor \frac{12}{2} \rfloor = 6$$$, then $$$a = [1, 4, 6, 2]$$$.
4. Replace $$$6$$$ with $$$\lfloor \frac{6}{2} \rfloor = 3$$$, then $$$a = [1, 4, 3, 2]$$$.

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

Each test case contains exactly two lines. The first one contains an integer $$$n$$$ ($$$1 \le n \le 50$$$), the second one contains integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

- YES if you can make the array $$$a$$$ become a permutation of numbers from $$$1$$$ to $$$n$$$,
- NO otherwise.

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

## Examples
```input
6
4
1 8 25 2
2
1 1
9
9 8 3 4 2 7 1 5 6
3
8 2 1
4
24 7 16 7
5
22 6 22 4 22
```
```output
YES
NO
YES
NO
NO
YES
```

## Note
The first test case is explained in the text of the problem statement.

In the second test case, it is not possible to get a permutation.

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
Recently, Vlad has been carried away by spanning trees, so his friends, without hesitation, gave him a connected weighted undirected graph of $$$n$$$ vertices and $$$m$$$ edges for his birthday.

Vlad defined the ority of a spanning tree as the bitwise OR of all its weights, and now he is interested in what is the minimum possible ority that can be achieved by choosing a certain spanning tree. A spanning tree is a connected subgraph of a given graph that does not contain cycles.

In other words, you want to keep $$$n-1$$$ edges so that the graph remains connected and the bitwise OR weights of the edges are as small as possible. You have to find the minimum bitwise OR itself.

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

An empty line is written in front of each test case.

This is followed by two numbers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 2 \cdot 10^5, n - 1 \le m \le 2 \cdot 10^5$$$) — the number of vertices and edges of the graph, respectively.

The next $$$m$$$ lines contain the description of the edges. Line $$$i$$$ contains three numbers $$$v_i$$$, $$$u_i$$$ and $$$w_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$1 \le w_i \le 10^9$$$, $$$v_i \neq u_i$$$) — the vertices that the edge connects and its weight.

It is guaranteed that the sum $$$m$$$ and the sum $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ and each test case contains a connected graph.

## Output Format
Print $$$t$$$ lines, each of which contains the answer to the corresponding set of input data — the minimum possible spanning tree ority.

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

## Note
Graph from the first test case.

Ority of this tree equals to 2 or 2 = 2 and it's minimal.

Without excluding edge with weight $$$1$$$ ority is 1 or 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Recently, the students of School 179 have developed a unique algorithm, which takes in a binary string $$$s$$$ as input. However, they soon found out that if some substring $$$t$$$ of $$$s$$$ is a palindrome of length greater than 1, the algorithm will work incorrectly. Can the students somehow reorder the characters of $$$s$$$ so that the algorithm will work correctly on the string?

A binary string is a string where each character is either 0 or 1.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

A palindrome is a string that reads the same backwards as forwards.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the string $$$s$$$.

The second line of each test case contains the string $$$s$$$ of length $$$n$$$ consisting only of the characters 0 and 1.

## Output Format
For each test case, print YES (case-insensitive) if it is possible to reorder the characters of $$$s$$$ so that there are no substrings that are a palindrome of length greater than 1, or NO (case-insensitive) otherwise.

## Examples
```input
4
1
1
2
10
2
01
4
1010
```
```output
YES
YES
YES
NO
```

## Note
In the first three test cases, the given strings do not contain palindromes of length greater than 1, so the answers are YES.

In the last test case, it is impossible to reorder the characters so that the string does not contain palindromes of length greater than 1, so the answer is NO.

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
Igor is in 11th grade. Tomorrow he will have to write an informatics test by the strictest teacher in the school, Pavel Denisovich.

Igor knows how the test will be conducted: first of all, the teacher will give each student two positive integers $$$a$$$ and $$$b$$$ ($$$a < b$$$). After that, the student can apply any of the following operations any number of times:

- $$$a := a + 1$$$ (increase $$$a$$$ by $$$1$$$),
- $$$b := b + 1$$$ (increase $$$b$$$ by $$$1$$$),
- $$$a := a \ | \ b$$$ (replace $$$a$$$ with the bitwise OR of $$$a$$$ and $$$b$$$).

To get full marks on the test, the student has to tell the teacher the minimum required number of operations to make $$$a$$$ and $$$b$$$ equal.

Igor already knows which numbers the teacher will give him. Help him figure out what is the minimum number of operations needed to make $$$a$$$ equal to $$$b$$$.

## 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 only line for each test case contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a < b \le 10^6$$$).

It is guaranteed that the sum of $$$b$$$ over all test cases does not exceed $$$10^6$$$.

## Output Format
For each test case print one integer — the minimum required number of operations to make $$$a$$$ and $$$b$$$ equal.

## Examples
```input
5
1 3
5 8
2 5
3 19
56678 164422
```
```output
1
3
2
1
23329
```

## Note
In the first test case, it is optimal to apply the third operation.

In the second test case, it is optimal to apply the first operation three times.

In the third test case, it is optimal to apply the second operation and then the third operation.

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

# Problem
New Year is just around the corner, which means that in School 179, preparations for the concert are in full swing.

There are $$$n$$$ classes in the school, numbered from $$$1$$$ to $$$n$$$, the $$$i$$$-th class has prepared a scene of length $$$a_i$$$ minutes.

As the main one responsible for holding the concert, Idnar knows that if a concert has $$$k$$$ scenes of lengths $$$b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_k$$$ minutes, then the audience will get bored if there exist two integers $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le k$$$ and $$$\gcd(b_l, b_{l + 1}, \ldots, b_{r - 1}, b_r) = r - l + 1$$$, where $$$\gcd(b_l, b_{l + 1}, \ldots, b_{r - 1}, b_r)$$$ is equal to the greatest common divisor (GCD) of the numbers $$$b_l$$$, $$$b_{l + 1}$$$, $$$\ldots$$$, $$$b_{r - 1}$$$, $$$b_r$$$.

To avoid boring the audience, Idnar can ask any number of times (possibly zero) for the $$$t$$$-th class ($$$1 \le t \le k$$$) to make a new scene $$$d$$$ minutes in length, where $$$d$$$ can be any positive integer. Thus, after this operation, $$$b_t$$$ is equal to $$$d$$$. Note that $$$t$$$ and $$$d$$$ can be different for each operation.

For a sequence of scene lengths $$$b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_{k}$$$, let $$$f(b)$$$ be the minimum number of classes Idnar has to ask to change their scene if he wants to avoid boring the audience.

Idnar hasn't decided which scenes will be allowed for the concert, so he wants to know the value of $$$f$$$ for each non-empty prefix of $$$a$$$. In other words, Idnar wants to know the values of $$$f(a_1)$$$, $$$f(a_1$$$,$$$a_2)$$$, $$$\ldots$$$, $$$f(a_1$$$,$$$a_2$$$,$$$\ldots$$$,$$$a_n)$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of classes in the school.

The second line contains $$$n$$$ positive integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the lengths of the class scenes.

## Output Format
Print a sequence of $$$n$$$ integers in a single line — $$$f(a_1)$$$, $$$f(a_1$$$,$$$a_2)$$$, $$$\ldots$$$, $$$f(a_1$$$,$$$a_2$$$,$$$\ldots$$$,$$$a_n)$$$.

## Examples
```input
1
1
```
```output
1
```
-----
```input
3
1 4 2
```
```output
1 1 2
```
-----
```input
7
2 12 4 8 18 3 6
```
```output
0 1 1 1 2 2 2
```

## Note
In the first test we can change $$$1$$$ to $$$2$$$, so the answer is $$$1$$$.

In the second test:

- $$$[1]$$$ can be changed into $$$[2]$$$,
- $$$[1, 4]$$$ can be changed into $$$[3, 4]$$$,
- $$$[1, 4, 2]$$$ can be changed into $$$[2, 3, 2]$$$.

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

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

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

Execution time limit: 5.0 seconds
Memory limit: 256.0 MB

# Problem
One remarkable day company "X" received k machines. And they were not simple machines, they were mechanical programmers! This was the last unsuccessful step before switching to android programmers, but that's another story.

The company has now n tasks, for each of them we know the start time of its execution si, the duration of its execution ti, and the company profit from its completion ci. Any machine can perform any task, exactly one at a time. If a machine has started to perform the task, it is busy at all moments of time from si to si + ti - 1, inclusive, and it cannot switch to another task.

You are required to select a set of tasks which can be done with these k machines, and which will bring the maximum total profit.

## Input Format
The first line contains two integer numbers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 50) — the numbers of tasks and machines, correspondingly.

The next n lines contain space-separated groups of three integers si, ti, ci (1 ≤ si, ti ≤ 109, 1 ≤ ci ≤ 106), si is the time where they start executing the i-th task, ti is the duration of the i-th task and ci is the profit of its execution.

## Output Format
Print n integers x1, x2, ..., xn. Number xi should equal 1, if task i should be completed and otherwise it should equal 0.

If there are several optimal solutions, print any of them.

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

## Note
In the first sample the tasks need to be executed at moments of time 2 ... 8, 1 ... 3 and 4 ... 4, correspondingly. The first task overlaps with the second and the third ones, so we can execute either task one (profit 5) or tasks two and three (profit 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Luis has a sequence of $$$n+1$$$ integers $$$a_1, a_2, \ldots, a_{n+1}$$$. For each $$$i = 1, 2, \ldots, n+1$$$ it is guaranteed that $$$0\leq a_i < n$$$, or $$$a_i=n^2$$$. He has calculated the sum of all the elements of the sequence, and called this value $$$s$$$.

Luis has lost his sequence, but he remembers the values of $$$n$$$ and $$$s$$$. Can you find the number of elements in the sequence that are equal to $$$n^2$$$?

We can show that the answer is unique under the given constraints.

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

The only line of each test case contains two integers $$$n$$$ and $$$s$$$ ($$$1\le n< 10^6$$$, $$$0\le s \le 10^{18}$$$). It is guaranteed that the value of $$$s$$$ is a valid sum for some sequence satisfying the above constraints.

## Output Format
For each test case, print one integer — the number of elements in the sequence which are equal to $$$n^2$$$.

## Examples
```input
4
7 0
1 1
2 12
3 12
```
```output
0
1
3
1
```

## Note
In the first test case, we have $$$s=0$$$ so all numbers are equal to $$$0$$$ and there isn't any number equal to $$$49$$$.

In the second test case, we have $$$s=1$$$. There are two possible sequences: $$$[0, 1]$$$ or $$$[1, 0]$$$. In both cases, the number $$$1$$$ appears just once.

In the third test case, we have $$$s=12$$$, which is the maximum possible value of $$$s$$$ for this case. Thus, the number $$$4$$$ appears $$$3$$$ times in the sequence.

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

# Problem
A number is called powerful if it is a power of two or a factorial. In other words, the number $$$m$$$ is powerful if there exists a non-negative integer $$$d$$$ such that $$$m=2^d$$$ or $$$m=d!$$$, where $$$d!=1\cdot 2\cdot \ldots \cdot d$$$ (in particular, $$$0! = 1$$$). For example $$$1$$$, $$$4$$$, and $$$6$$$ are powerful numbers, because $$$1=1!$$$, $$$4=2^2$$$, and $$$6=3!$$$ but $$$7$$$, $$$10$$$, or $$$18$$$ are not.

You are given a positive integer $$$n$$$. Find the minimum number $$$k$$$ such that $$$n$$$ can be represented as the sum of $$$k$$$ distinct powerful numbers, or say that there is no such $$$k$$$.

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

A test case consists of only one line, containing one integer $$$n$$$ ($$$1\le n\le 10^{12}$$$).

## Output Format
For each test case print the answer on a separate line.

If $$$n$$$ can not be represented as the sum of distinct powerful numbers, print $$$-1$$$.

Otherwise, print a single positive integer  — the minimum possible value of $$$k$$$.

## Examples
```input
4
7
11
240
17179869184
```
```output
2
3
4
1
```

## Note
In the first test case, $$$7$$$ can be represented as $$$7=1+6$$$, where $$$1$$$ and $$$6$$$ are powerful numbers. Because $$$7$$$ is not a powerful number, we know that the minimum possible value of $$$k$$$ in this case is $$$k=2$$$.

In the second test case, a possible way to represent $$$11$$$ as the sum of three powerful numbers is $$$11=1+4+6$$$. We can show that there is no way to represent $$$11$$$ as the sum of two or less powerful numbers.

In the third test case, $$$240$$$ can be represented as $$$240=24+32+64+120$$$. Observe that $$$240=120+120$$$ is not a valid representation, because the powerful numbers have to be distinct.

In the fourth test case, $$$17179869184=2^{34}$$$, so $$$17179869184$$$ is a powerful number and the minimum $$$k$$$ in this case is $$$k=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
You are given a tree of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. A tree is a connected undirected graph without cycles.

For each $$$i=1,2, \ldots, n$$$, let $$$w_i$$$ be the weight of the $$$i$$$-th vertex. A vertex is called good if its weight is equal to the sum of the weights of all its neighbors.

Initially, the weights of all nodes are unassigned. Assign positive integer weights to each vertex of the tree, such that the number of good vertices in the tree is maximized. If there are multiple ways to do it, you have to find one that minimizes the sum of weights of all vertices in the tree.

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

Then, $$$n−1$$$ lines follow. Each of them contains two integers $$$u$$$ and $$$v$$$ ($$$1\le u,v\le n$$$) denoting an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the edges form a tree.

## Output Format
In the first line print two integers  — the maximum number of good vertices and the minimum possible sum of weights for that maximum.

In the second line print $$$n$$$ integers $$$w_1, w_2, \ldots, w_n$$$ ($$$1\le w_i\le 10^9$$$)  — the corresponding weight assigned to each vertex. It can be proven that there exists an optimal solution satisfying these constraints.

If there are multiple optimal solutions, you may print any.

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

## Note
This is the tree for the first test case:

This is the tree for the second test case:

Now solve the problem and return the code.