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

# Problem
You are given an array of positive integers $$$a$$$ of length $$$n$$$.

Let's call an array of positive integers $$$b$$$ of length $$$n$$$ good if:

1. $$$a_i \neq b_i$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$,
2. $$$a_1 + a_2 +\ldots + a_n = b_1 + b_2 + \ldots + b_n$$$.

Does a good array exist?

## Input Format
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 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$$$ ($$$1 \le n \le 10^5$$$) — the length of the array $$$a$$$.

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 $$$a$$$.

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

## Output Format
For each test case, output "YES" (without quotes) if there exists a good array, and "NO" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs","yes", "Yes", and "YES" will be recognized as positive responses.

## Examples
```input
6
3
6 1 2
2
1 1
4
3 1 2 4
1
17
5
1 2 1 1 1
3
618343152 819343431 1000000000
```
```output
YES
NO
YES
NO
NO
YES
```

## Note
In the first test case, a possible good array is $$$[3, 3, 3]$$$. Some examples of not good arrays are:

- $$$[8, 0, 1]$$$ — the array does not consist of only positive integers,
- $$$[5, 2, 4]$$$ — the array does not have the same sum as the given array,
- $$$[5, 2, 2]$$$ — the third element is equal to the third element of the given array.

In the second test case, $$$[1, 1]$$$ is the only array of positive integers of length $$$2$$$ that has the sum of it's elements equal to $$$2$$$. Since $$$[1, 1]$$$ is not a good array, 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 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 an array of integers $$$a$$$ of length $$$n$$$.

In one operation you:

- Choose an index $$$i$$$ such that $$$1 \le i \le n - 1$$$ and $$$a_i \le a_{i + 1}$$$.
- Increase $$$a_i$$$ by $$$1$$$.

Find the maximum possible value of $$$\max(a_1, a_2, \ldots a_n)$$$ that you can get after performing this operation at most $$$k$$$ times.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 1000$$$, $$$1 \le k \le 10^{8}$$$) — the length of the array $$$a$$$ and the maximum number of operations that can be performed.

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

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

## Output Format
For each test case output a single integer — the maximum possible maximum of the array after performing at most $$$k$$$ operations.

## Examples
```input
6
3 4
1 3 3
5 6
1 3 4 5 1
4 13
1 1 3 179
5 3
4 3 2 2 2
5 6
6 5 4 1 5
2 17
3 5
```
```output
4
7
179
5
7
6
```

## Note
In the first test case, one possible optimal sequence of operations is: $$$[\color{red}{1}, 3, 3] \rightarrow [2, \color{red}{3}, 3] \rightarrow [\color{red}{2}, 4, 3] \rightarrow [\color{red}{3}, 4, 3] \rightarrow [4, 4, 3]$$$.

In the second test case, one possible optimal sequence of operations is: $$$[1, \color{red}{3}, 4, 5, 1] \rightarrow [1, \color{red}{4}, 4, 5, 1] \rightarrow [1, 5, \color{red}{4}, 5, 1] \rightarrow [1, 5, \color{red}{5}, 5, 1] \rightarrow [1, \color{red}{5}, 6, 5, 1] \rightarrow [1, \color{red}{6}, 6, 5, 1] \rightarrow [1, 7, 6, 5, 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: 512.0 MB

# Problem
This is the easy version of the problem. The differences between the two versions are the constraint on $$$n$$$ and the time limit. You can make hacks only if both versions of the problem are solved.

You are given a tree with $$$n$$$ vertices rooted at vertex $$$1$$$.

For some permutation$$$^\dagger$$$ $$$a$$$ of length $$$n$$$, let $$$f(a)$$$ be the number of pairs of vertices $$$(u, v)$$$ such that $$$a_u < a_{\operatorname{lca}(u, v)} < a_v$$$. Here, $$$\operatorname{lca}(u,v)$$$ denotes the lowest common ancestor of vertices $$$u$$$ and $$$v$$$.

Find the maximum possible value of $$$f(a)$$$ over all permutations $$$a$$$ of length $$$n$$$.

$$$^\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
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 5000$$$).

The second line contains $$$n - 1$$$ integers $$$p_2,p_3,\ldots,p_n$$$ ($$$1 \le p_i < i$$$) indicating that there is an edge between vertices $$$i$$$ and $$$p_i$$$.

## Output Format
Output the maximum value of $$$f(a)$$$.

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

## Note
The tree in the first test:

One possible optimal permutation $$$a$$$ is $$$[2, 1, 4, 5, 3]$$$ with $$$4$$$ suitable pairs of vertices:

- $$$(2, 3)$$$, since $$$\operatorname{lca}(2, 3) = 1$$$ and $$$1 < 2 < 4$$$,
- $$$(2, 4)$$$, since $$$\operatorname{lca}(2, 4) = 1$$$ and $$$1 < 2 < 5$$$,
- $$$(2, 5)$$$, since $$$\operatorname{lca}(2, 5) = 1$$$ and $$$1 < 2 < 3$$$,
- $$$(5, 4)$$$, since $$$\operatorname{lca}(5, 4) = 3$$$ and $$$3 < 4 < 5$$$.

The tree in the third test:

The tree in the fourth test:

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
There is an $$$n\times m$$$ board divided into cells. There are also some dominoes on this board. Each domino covers two adjacent cells (that is, two cells that share a side), and no two dominoes overlap.

Piet thinks that this board is too boring and it needs to be painted. He will paint the cells of the dominoes black and white. He calls the painting beautiful if all of the following conditions hold:

- for each domino, one of its cells is painted white and the other is painted black;
- for each row, the number of black cells in this row equals the number of white cells in this row;
- for each column, the number of black cells in this column equals the number of white cells in this column.

Note that the cells that are not covered by dominoes are not painted at all, they are counted as neither black nor white.

Help Piet produce a beautiful painting or tell that it is impossible.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2\le n, m\le 500$$$).

The next $$$n$$$ lines describe the tiling of the board, row by row from top to bottom. Each of these lines contains $$$m$$$ characters, describing the cells in the corresponding row from left to right. Each character is one of U, D, L, R, or ., meaning that the cell is covered with a top, bottom, left, right half of a domino or nothing, respectively. The tiling is guaranteed to be valid.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$250\,000$$$.

## Output Format
For each test case, output a single integer $$$-1$$$ if a beautiful painting does not exist. Otherwise, print $$$n$$$ lines, each containing $$$m$$$ characters, describing the colors in the corresponding row of a beautiful painting. Every character corresponding to a cell not covered by a domino must be . (a dot), and all other characters must be B if the corresponding cell is black or W if it is white.

If there are multiple solutions, print any of them.

## Examples
```input
3
4 6
..LR..
ULRU..
DLRDUU
..LRDD
5 4
.LR.
.UU.
UDDU
D..D
LR..
2 2
..
..
```
```output
..WB..
WWBB..
BBWWWB
..BWBW
-1
..
..
```

## Note
In the first test case, the answer is illustrated below:

In the second test case, it is impossible to paint all cells the right way.

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 an array of integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$). You can perform the following operation several (possibly, zero) times:

- pick an arbitrary $$$i$$$ and perform swap$$$(a_i, a_{a_i})$$$.

How many distinct arrays is it possible to attain? Output the answer modulo $$$(10^9 + 7)$$$.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1\le a_i\le n$$$).

## Output Format
Output the number of attainable arrays modulo $$$(10^9 + 7)$$$.

## Examples
```input
3
1 1 2
```
```output
2
```
-----
```input
4
2 1 4 3
```
```output
4
```
-----
```input
6
2 3 1 1 1 2
```
```output
18
```

## Note
In the first example, the initial array is $$$[1, 1, 2]$$$. If we perform the operation with $$$i = 3$$$, we swap $$$a_3$$$ and $$$a_2$$$, obtaining $$$[1, 2, 1]$$$. One can show that there are no other attainable arrays.

In the second example, the four attainable arrays are $$$[2, 1, 4, 3]$$$, $$$[1, 2, 4, 3]$$$, $$$[1, 2, 3, 4]$$$, $$$[2, 1, 3, 4]$$$. One can show that there are no other attainable arrays.

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

# Problem
You are given a tree with $$$n$$$ vertices labeled $$$1, 2, \ldots, n$$$. The length of a simple path in the tree is the number of vertices in it.

You are to select a set of simple paths of length at least $$$2$$$ each, but you cannot simultaneously select two distinct paths contained one in another. Find the largest possible size of such a set.

Formally, a set $$$S$$$ of vertices is called a route if it contains at least two vertices and coincides with the set of vertices of a simple path in the tree. A collection of distinct routes is called a timetable. A route $$$S$$$ in a timetable $$$T$$$ is called redundant if there is a different route $$$S' \in T$$$ such that $$$S \subset S'$$$. A timetable is called efficient if it contains no redundant routes. Find the largest possible number of routes in an efficient timetable.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 3000$$$).

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$$$) — the numbers of vertices connected by the $$$i$$$-th edge.

It is guaranteed that the given edges form a tree.

## Output Format
Print a single integer — the answer to the problem.

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

## Note
In the first example, possible efficient timetables are $$$\{\{1, 2\}, \{1, 3\}, \{1, 4\}\}$$$ and $$$\{\{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}\}$$$.

In the second example, we can choose $$$\{ \{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 6\}, \{2, 3, 5\}, \{3, 4, 5\}, \{3, 4, 7\}, \{4, 6, 7\}\}$$$.

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
green_gold_dog has an array $$$a$$$ of length $$$n$$$, and he wants to find a permutation $$$b$$$ of length $$$n$$$ such that the number of distinct numbers in the element-wise difference between array $$$a$$$ and permutation $$$b$$$ is maximized.

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

The element-wise difference between two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$ is an array $$$c$$$ of length $$$n$$$, where $$$c_i$$$ = $$$a_i - b_i$$$ ($$$1 \leq i \leq n$$$).

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 4 \cdot 10^4$$$).

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

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

## Output Format
For each test case, output $$$n$$$ numbers - a suitable permutation $$$b$$$. If there are multiple solutions, print any of them.

## Examples
```input
3
1
100000
2
1 1
3
10 3 3
```
```output
1 
2 1 
1 3 2
```

## Note
In the first set of input data, the element-wise difference of the arrays is [99999]. Here, there is one distinct number, and it is obvious that in an array of length one, there cannot be more than one different element.

In the second set of input data, the element-wise difference of the arrays is [-1, 0]. Here, there are two distinct numbers, and it is obvious that in an array of length two, there cannot be more than two different elements.

In the third set of input data, the element-wise difference of the arrays is [9, 0, 1]. Here, there are three distinct numbers, and it is obvious that in an array of length three, there cannot be more than three different elements.

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 binary string $$$s$$$ of length $$$n$$$ (a string that consists only of $$$0$$$ and $$$1$$$). A number $$$x$$$ is good if there exists a binary string $$$l$$$ of length $$$n$$$, containing $$$x$$$ ones, such that if each symbol $$$s_i$$$ is replaced by $$$s_i \oplus l_i$$$ (where $$$\oplus$$$ denotes the bitwise XOR operation), then the string $$$s$$$ becomes a palindrome.

You need to output a binary string $$$t$$$ of length $$$n+1$$$, where $$$t_i$$$ ($$$0 \leq i \leq n$$$) is equal to $$$1$$$ if number $$$i$$$ is good, and $$$0$$$ otherwise.

A palindrome is a string that reads the same from left to right as from right to left. For example, 01010, 1111, 0110 are palindromes.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The 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 second line of each test case contains a binary string $$$s$$$ of length $$$n$$$.

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

## Output Format
For each test case, output a single line containing a binary string $$$t$$$ of length $$$n+1$$$ - the answer to the problem.

## Examples
```input
5
6
101011
5
00000
9
100100011
3
100
1
1
```
```output
0010100
111111
0011111100
0110
11
```

## Note
Consider the first example.

- $$$t_2 = 1$$$ because we can choose $$$l = $$$ 010100, then the string $$$s$$$ becomes 111111, which is a palindrome.
- $$$t_4 = 1$$$ because we can choose $$$l = $$$ 101011.
- It can be shown that for all other $$$i$$$, there is no answer, so the remaining symbols are $$$0$$$.

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
Egor has an array $$$a$$$ of length $$$n$$$, initially consisting of zeros. However, he wanted to turn it into another array $$$b$$$ of length $$$n$$$.

Since Egor doesn't take easy paths, only the following operation can be used (possibly zero or several times):

- choose an array $$$l$$$ of length $$$k$$$ ($$$1 \leq l_i \leq n$$$, all $$$l_i$$$ are distinct) and change each element $$$a_{l_i}$$$ to $$$l_{(i\%k)+1}$$$ ($$$1 \leq i \leq k$$$).

He became interested in whether it is possible to get the array $$$b$$$ using only these operations. Since Egor is still a beginner programmer, he asked you to help him solve this problem.

The operation $$$\%$$$ means taking the remainder, that is, $$$a\%b$$$ is equal to the remainder of dividing the number $$$a$$$ by the number $$$b$$$.

## Input Format
The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) - the number of test cases.

Each test case consists of two lines. The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 10^5$$$).

The second line contains the array $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq n$$$).

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, output "YES" (without quotes) if there is a way to get the array $$$b$$$ using only the given operation. Otherwise, output "NO" (without quotes). You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes" and "YES" will be accepted as a positive answer.

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

## Note
Let's consider the first example:

- Apply the operation with $$$l$$$ = $$$[1,2,3]$$$. Now $$$a$$$ = $$$[2,3,1,0,0]$$$.
- Apply the operation with $$$l$$$ = $$$[3,5,4]$$$. Now $$$a$$$ = $$$[2,3,5,3,4]$$$ = $$$b$$$.

In the second example, it can be proven that the array $$$b$$$ cannot be obtained, therefore the answer is NO.

Now solve the problem and return the code.