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
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
You are given a permutation $$$p_1, p_2, \ldots, p_n$$$ of length $$$n$$$. You have to choose two integers $$$l,r$$$ ($$$1 \le l \le r \le n$$$) and reverse the subsegment $$$[l,r]$$$ of the permutation. The permutation will become $$$p_1,p_2, \dots, p_{l-1},p_r,p_{r-1}, \dots, p_l,p_{r+1},p_{r+2}, \dots ,p_n$$$.

Find the lexicographically smallest permutation that can be obtained by performing exactly one reverse operation on the initial permutation.

Note that for two distinct permutations of equal length $$$a$$$ and $$$b$$$, $$$a$$$ is lexicographically smaller than $$$b$$$ if at the first position they differ, $$$a$$$ has the smaller element.

A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

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

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

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — the elements of the permutation.

## Output Format
For each test case print the lexicographically smallest permutation you can obtain.

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

## Note
In the first test case, the permutation has length $$$1$$$, so the only possible segment is $$$[1,1]$$$. The resulting permutation is $$$[1]$$$.

In the second test case, we can obtain the identity permutation by reversing the segment $$$[1,2]$$$. The resulting permutation is $$$[1,2,3]$$$.

In the third test case, the best possible segment is $$$[2,3]$$$. The resulting permutation is $$$[1,2,4,3]$$$.

In the fourth test case, there is no lexicographically smaller permutation, so we can leave it unchanged by choosing the segment $$$[1,1]$$$. The resulting permutation is $$$[1,2,3,4,5]$$$.

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
You are given an array $$$a_1, a_2, \dots, a_n$$$. You can perform operations on the array. In each operation you can choose an integer $$$i$$$ ($$$1 \le i < n$$$), and swap elements $$$a_i$$$ and $$$a_{i+1}$$$ of the array, if $$$a_i + a_{i+1}$$$ is odd.

Determine whether it can be sorted in non-decreasing order using this operation any number of times.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print "Yes" or "No" depending on whether you can or can not sort the given array.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

## Examples
```input
4
4
1 6 31 14
2
4 2
5
2 9 6 7 10
3
6 6 6
```
```output
Yes
No
No
Yes
```

## Note
In the first test case, we can simply swap $$$31$$$ and $$$14$$$ ($$$31 + 14 = 45$$$ which is odd) and obtain the non-decreasing array $$$[1,6,14,31]$$$.

In the second test case, the only way we could sort the array is by swapping $$$4$$$ and $$$2$$$, but this is impossible, since their sum $$$4 + 2 = 6$$$ is even.

In the third test case, there is no way to make the array non-decreasing.

In the fourth test case, the array is already non-decreasing.

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
You are given a permutation $$$p_1, p_2, \dots, p_n$$$. Then, an undirected graph is constructed in the following way: add an edge between vertices $$$i$$$, $$$j$$$ such that $$$i < j$$$ if and only if $$$p_i > p_j$$$. Your task is to count the number of connected components in this graph.

Two vertices $$$u$$$ and $$$v$$$ belong to the same connected component if and only if there is at least one path along edges connecting $$$u$$$ and $$$v$$$.

A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

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

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

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — the elements of the permutation.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print one integer $$$k$$$ — the number of connected components.

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

## Note
Each separate test case is depicted in the image below. The colored squares represent the elements of the permutation. For one permutation, each color represents some connected component. The number of distinct colors is the answer.

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

# Problem
You have an array $$$a_1,a_2, \dots, a_n$$$. Each element initially has value $$$0$$$ and color $$$1$$$. You are also given $$$q$$$ queries to perform:

- Color $$$l$$$ $$$r$$$ $$$c$$$: Change the color of elements $$$a_l,a_{l+1},\cdots,a_r$$$ to $$$c$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le c \le n$$$).
- Add $$$c$$$ $$$x$$$: Add $$$x$$$ to values of all elements $$$a_i$$$ ($$$1 \le i \le n$$$) of color $$$c$$$ ($$$1 \le c \le n$$$, $$$-10^9 \le x \le 10^9$$$).
- Query $$$i$$$: Print $$$a_i$$$ ($$$1 \le i \le n$$$).

## Input Format
The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 10^6$$$) — the length of array $$$a$$$ and the number of queries you have to perform.

Each of the next $$$q$$$ lines contains the query given in the form described in the problem statement.

## Output Format
Print the answers to the queries of the third type on separate lines.

## Examples
```input
5 8
Color 2 4 2
Add 2 2
Query 3
Color 4 5 3
Color 2 2 3
Add 3 3
Query 2
Query 5
```
```output
2
5
3
```
-----
```input
2 7
Add 1 7
Query 1
Add 2 4
Query 2
Color 1 1 1
Add 1 1
Query 2
```
```output
7
7
8
```

## Note
The first sample test is explained below. Blue, red and green represent colors $$$1$$$, $$$2$$$ and $$$3$$$ respectively.

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: 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 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
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 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
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 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 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.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

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

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

Execution time limit: 1.5 seconds
Memory limit: 256.0 MB

# Problem
You have a rectangular board of size $$$n\times m$$$ ($$$n$$$ rows, $$$m$$$ columns). The $$$n$$$ rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and the $$$m$$$ columns are numbered from $$$1$$$ to $$$m$$$ from left to right.

The cell at the intersection of row $$$i$$$ and column $$$j$$$ contains the number $$$i^j$$$ ($$$i$$$ raised to the power of $$$j$$$). For example, if $$$n=3$$$ and $$$m=3$$$ the board is as follows:

Find the number of distinct integers written on the board.

## Input Format
The only line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 10^6$$$) — the number of rows and columns of the board.

## Output Format
Print one integer, the number of distinct integers on the board.

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

## Note
The statement shows the board for the first test case. In this case there are $$$7$$$ distinct integers: $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$8$$$, $$$9$$$, and $$$27$$$.

In the second test case, the board is as follows:

There are $$$5$$$ distinct numbers: $$$1$$$, $$$2$$$, $$$4$$$, $$$8$$$ and $$$16$$$.

In the third test case, the board is as follows:

There are $$$6$$$ distinct numbers: $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$9$$$ and $$$16$$$.

Now solve the problem and return the code.