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
Kid was gifted a tree of $$$n$$$ vertices with the root in the vertex $$$1$$$. Since he really like symmetrical objects, Kid wants to find out if this tree is symmetrical.

For example, the trees in the picture above are symmetrical.

And the trees in this picture are not symmetrical.

Formally, a tree is symmetrical if there exists an order of children such that:

- The subtree of the leftmost child of the root is a mirror image of the subtree of the rightmost child;
- the subtree of the second-left child of the root is a mirror image of the subtree of the second-right child of the root;
- ...
- if the number of children of the root is odd, then the subtree of the middle child should be symmetrical.

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

The first line of each case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

The following $$$n-1$$$ lines contain two integers each $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — indices of vertices connected by an edge.

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

## Output Format
Output $$$t$$$ strings, each of which is the answer to the corresponding test case. As an answer, output "YES" if this tree is symmetrical, and "NO" otherwise.

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

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

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: 512.0 MB

# Problem
You are given a checkerboard of size $$$201 \times 201$$$, i. e. it has $$$201$$$ rows and $$$201$$$ columns. The rows of this checkerboard are numbered from $$$-100$$$ to $$$100$$$ from bottom to top. The columns of this checkerboard are numbered from $$$-100$$$ to $$$100$$$ from left to right. The notation $$$(r, c)$$$ denotes the cell located in the $$$r$$$-th row and the $$$c$$$-th column.

There is a king piece at position $$$(0, 0)$$$ and it wants to get to position $$$(a, b)$$$ as soon as possible. In this problem our king is lame. Each second, the king makes exactly one of the following five moves.

- Skip move. King's position remains unchanged.
- Go up. If the current position of the king is $$$(r, c)$$$ he goes to position $$$(r + 1, c)$$$.
- Go down. Position changes from $$$(r, c)$$$ to $$$(r - 1, c)$$$.
- Go right. Position changes from $$$(r, c)$$$ to $$$(r, c + 1)$$$.
- Go left. Position changes from $$$(r, c)$$$ to $$$(r, c - 1)$$$.

What is the minimum number of seconds the lame king needs to reach position $$$(a, b)$$$?

## Input Format
The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then follow $$$t$$$ lines containing one test case description each.

Each test case consists of two integers $$$a$$$ and $$$b$$$ ($$$-100 \leq a, b \leq 100$$$) — the position of the cell that the king wants to reach. It is guaranteed that either $$$a \ne 0$$$ or $$$b \ne 0$$$.

## Output Format
Print $$$t$$$ integers. The $$$i$$$-th of these integers should be equal to the minimum number of seconds the lame king needs to get to the position he wants to reach in the $$$i$$$-th test case. The king always starts at position $$$(0, 0)$$$.

## Examples
```input
5
-4 1
4 4
0 -6
-5 -4
7 -8
```
```output
7
8
11
9
15
```

## Note
One of the possible solutions for the first example is: go down, go right, go down, go right, go down, go left, go down.

One of the possible solutions for the second example is to alternate "go right" and "go up" moves $$$4$$$ times each.

One of the possible solutions for the third example is to alternate "go left" and "skip" moves starting with "go left". Thus, "go left" will be used $$$6$$$ times, and "skip" will be used $$$5$$$ 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Timur loves codeforces. That's why he has a string $$$s$$$ having length $$$10$$$ made containing only lowercase Latin letters. Timur wants to know how many indices string $$$s$$$ differs from the string "codeforces".

For example string $$$s =$$$ "coolforsez" differs from "codeforces" in $$$4$$$ indices, shown in bold.

Help Timur by finding the number of indices where string $$$s$$$ differs from "codeforces".

Note that you can't reorder the characters in the string $$$s$$$.

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

Each test case is one line and contains the string $$$s$$$, consisting of exactly $$$10$$$ lowercase Latin characters.

## Output Format
For each test case, output a single integer — the number of indices where string $$$s$$$ differs.

## Examples
```input
5
coolforsez
cadafurcie
codeforces
paiuforces
forcescode
```
```output
4
5
0
4
9
```

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 binary array $$$a$$$ of $$$n$$$ elements, a binary array is an array consisting only of $$$0$$$s and $$$1$$$s.

A blank space is a segment of consecutive elements consisting of only $$$0$$$s.

Your task is to find the length of the longest blank space.

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

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

The second line of each test case contains $$$n$$$ space-separated integers $$$a_i$$$ ($$$0 \leq a_i \leq 1$$$) — the elements of the array.

## Output Format
For each test case, output a single integer — the length of the longest blank space.

## Examples
```input
5
5
1 0 0 1 0
4
0 1 1 1
1
0
3
1 1 1
9
1 0 0 0 1 0 0 0 1
```
```output
2
1
1
0
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
Victor wants to become "Mr. Perfectly Fine". For that, he needs to acquire a certain set of skills. More precisely, he has $$$2$$$ skills he needs to acquire.

Victor has $$$n$$$ books. Reading book $$$i$$$ takes him $$$m_i$$$ minutes and will give him some (possibly none) of the required two skills, represented by a binary string of length $$$2$$$.

What is the minimum amount of time required so that Victor acquires all of the two skills?

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of books available.

Then $$$n$$$ lines follow. Line $$$i$$$ contains a positive integer $$$m_i$$$ ($$$1 \leq m_i \leq 2 \cdot 10^5$$$) and a binary string of length $$$2$$$, where $$$s_{i1} = 1$$$ if reading book $$$i$$$ acquires Victor skill $$$1$$$, and $$$s_{i1} = 0$$$ otherwise, and $$$s_{i2} = 1$$$ if reading book $$$i$$$ acquires Victor skill $$$2$$$, and $$$s_{i2} = 0$$$ otherwise.

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

## Output Format
For each test case, output a single integer denoting the minimum amount of minutes required for Victor to obtain both needed skills and $$$-1$$$ in case it's impossible to obtain the two skills after reading any amount of books.

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

## Note
In the first test case, we can use books $$$2$$$ and $$$3$$$, with a total amount of minutes spent equal to $$$3 + 4 = 7$$$.

In the second test case, we can use the books $$$1$$$ and $$$4$$$, with a total amount of minutes spent equal to $$$3 + 2 = 5$$$.

In the third test case, we have only one option and that is reading book $$$1$$$ for a total amount of minutes spent equal to $$$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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Initially you have a single pile with $$$n$$$ gold nuggets. In an operation you can do the following:

- Take any pile and split it into two piles, so that one of the resulting piles has exactly twice as many gold nuggets as the other. (All piles should have an integer number of nuggets.)

One possible move is to take a pile of size $$$6$$$ and split it into piles of sizes $$$2$$$ and $$$4$$$, which is valid since $$$4$$$ is twice as large as $$$2$$$.

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

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^7$$$) — the starting and target pile sizes, respectively.

## Output Format
For each test case, output "YES" if you can make a pile of size exactly $$$m$$$, and "NO" otherwise.

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

## Examples
```input
11
6 4
9 4
4 2
18 27
27 4
27 2
27 10
1 1
3 1
5 1
746001 2984004
```
```output
YES
YES
NO
NO
YES
YES
NO
YES
YES
NO
NO
```

## Note
The first test case is pictured in the statement. We can make a pile of size $$$4$$$.

In the second test case, we can perform the following operations: $$$\{\color{red}{9}\} \to \{\color{red}{6},3\} \to \{4,2,3\}$$$. The pile that is split apart is colored red before each operation.

In the third test case, we can't perform a single operation.

In the fourth test case, we can't end up with a larger pile than we started with.

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
You are given an $$$n \times m$$$ grid $$$a$$$ of non-negative integers. The value $$$a_{i,j}$$$ represents the depth of water at the $$$i$$$-th row and $$$j$$$-th column.

A lake is a set of cells such that:

- each cell in the set has $$$a_{i,j} > 0$$$, and
- there exists a path between any pair of cells in the lake by going up, down, left, or right a number of times and without stepping on a cell with $$$a_{i,j} = 0$$$.

The volume of a lake is the sum of depths of all the cells in the lake.

Find the largest volume of a lake in the grid.

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

The first line of each test case contains two integers $$$n, m$$$ ($$$1 \leq n, m \leq 1000$$$) — the number of rows and columns of the grid, respectively.

Then $$$n$$$ lines follow each with $$$m$$$ integers $$$a_{i,j}$$$ ($$$0 \leq a_{i,j} \leq 1000$$$) — the depth of the water at each cell.

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

## Output Format
For each test case, output a single integer — the largest volume of a lake in the grid.

## Examples
```input
5
3 3
1 2 0
3 4 0
0 0 5
1 1
0
3 3
0 1 1
1 0 1
1 1 1
5 5
1 1 1 1 1
1 0 0 0 1
1 0 5 0 1
1 0 0 0 1
1 1 1 1 1
5 5
1 1 1 1 1
1 0 0 0 1
1 1 4 0 1
1 0 0 0 1
1 1 1 1 1
```
```output
10
0
7
16
21
```

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

# Problem
In a carnival game, there is a huge pyramid of cans with $$$2023$$$ rows, numbered in a regular pattern as shown.

If can $$$9^2$$$ is hit initially, then all cans colored red in the picture above would fall.

You throw a ball at the pyramid, and it hits a single can with number $$$n^2$$$. This causes all cans that are stacked on top of this can to fall (that is, can $$$n^2$$$ falls, then the cans directly above $$$n^2$$$ fall, then the cans directly above those cans, and so on). For example, the picture above shows the cans that would fall if can $$$9^2$$$ is hit.

What is the sum of the numbers on all cans that fall? Recall that $$$n^2 = n \times n$$$.

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

The only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — it means that the can you hit has label $$$n^2$$$.

## Output Format
For each test case, output a single integer — the sum of the numbers on all cans that fall.

Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++). For all valid inputs, the answer will always fit into 64-bit integer type.

## Examples
```input
10
9
1
2
3
4
5
6
10
1434
1000000
```
```output
156
1
5
10
21
39
46
146
63145186
58116199242129511
```

## Note
The first test case is pictured in the statement. The sum of the numbers that fall is $$$$$$1^2 + 2^2 + 3^2 + 5^2 + 6^2 + 9^2 = 1 + 4 + 9 + 25 + 36 + 81 = 156.$$$$$$

In the second test case, only the can labeled $$$1^2$$$ falls, so the answer is $$$1^2=1$$$.

In the third test case, the cans labeled $$$1^2$$$ and $$$2^2$$$ fall, so the answer is $$$1^2+2^2=1+4=5$$$.

In the fourth test case, the cans labeled $$$1^2$$$ and $$$3^2$$$ fall, so the answer is $$$1^2+3^2=1+9=10$$$.

In the fifth test case, the cans labeled $$$1^2$$$, $$$2^2$$$, and $$$4^2$$$ fall, so the answer is $$$1^2+2^2+4^2=1+4+16=21$$$.

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
Sadly, the problem setter couldn't think of an interesting story, thus he just asks you to solve the following problem.

Given an array $$$a$$$ consisting of $$$n$$$ positive integers, count the number of non-empty subsequences for which the bitwise $$$\mathsf{AND}$$$ of the elements in the subsequence has exactly $$$k$$$ set bits in its binary representation. The answer may be large, so output it modulo $$$10^9+7$$$.

Recall that the subsequence of an array $$$a$$$ is a sequence that can be obtained from $$$a$$$ by removing some (possibly, zero) elements. For example, $$$[1, 2, 3]$$$, $$$[3]$$$, $$$[1, 3]$$$ are subsequences of $$$[1, 2, 3]$$$, but $$$[3, 2]$$$ and $$$[4, 5, 6]$$$ are not.

Note that $$$\mathsf{AND}$$$ represents the bitwise AND operation.

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

The first line of each test case consists of two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \le k \le 6$$$) — the length of the array and the number of set bits that the bitwise $$$\mathsf{AND}$$$ the counted subsequences should have in their binary representation.

The second line of each test case consists of $$$n$$$ integers $$$a_i$$$ ($$$0 \leq a_i \leq 63$$$) — the array $$$a$$$.

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

## Output Format
For each test case, output a single integer — the number of subsequences that have exactly $$$k$$$ set bits in their bitwise $$$\mathsf{AND}$$$ value's binary representation. The answer may be large, so output it modulo $$$10^9+7$$$.

## Examples
```input
6
5 1
1 1 1 1 1
4 0
0 1 2 3
5 1
5 5 7 4 2
1 2
3
12 0
0 2 0 2 0 2 0 2 0 2 0 2
10 6
63 0 63 5 5 63 63 4 12 13
```
```output
31
10
10
1
4032
15
```

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$$$^\dagger$$$ $$$a$$$ of length $$$n$$$.

Find any permutation $$$b$$$ of length $$$n$$$ such that $$$a_1+b_1 \le a_2+b_2 \le a_3+b_3 \le \ldots \le a_n+b_n$$$.

It can be proven that a permutation $$$b$$$ that satisfies the condition above always exists.

$$$^\dagger$$$ A permutation of length $$$n$$$ 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 of input contains a single integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of test cases. The description of test cases follows.

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

The second line of each test case contains $$$n$$$ distinct integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of permutation $$$a$$$. All elements of $$$a$$$ are distinct.

Note that there is no bound on the sum of $$$n$$$ over all test cases.

## Output Format
For each test case, output any permutation $$$b$$$ which satisfies the constraints mentioned in the statement. It can be proven that a permutation $$$b$$$ that satisfies the condition above always exists.

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

## Note
In the first test case $$$a=[1, 2, 4, 5, 3]$$$. Then the permutation $$$b=[1, 2, 4, 3, 5]$$$ satisfies the condition because $$$1 + 1 \le 2 + 2 \le 4 + 4 \le 5 + 3 \le 3 + 5$$$.

Now solve the problem and return the code.