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

# Problem
There are $$$n$$$ uniform random real variables between 0 and 1, inclusive, which are denoted as $$$x_1, x_2, \ldots, x_n$$$.

Tenzing has $$$m$$$ conditions. Each condition has the form of $$$x_i+x_j\le 1$$$ or $$$x_i+x_j\ge 1$$$.

Tenzing wants to know the probability that all the conditions are satisfied, modulo $$$998~244~353$$$.

Formally, let $$$M = 998~244~353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output the integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le 20$$$, $$$0\le m\le n^2+n$$$).

Then following $$$m$$$ lines of input contains three integers $$$t$$$, $$$i$$$ and $$$j$$$ ($$$t \in \{0,1\}$$$, $$$1\le i\le j\le n$$$).

- If $$$t=0$$$, the condition is $$$x_i+x_j\le 1$$$.
- If $$$t=1$$$, the condition is $$$x_i+x_j\ge 1$$$.

It is guaranteed that all conditions are pairwise distinct.

## Output Format
Output the probability that all the conditions are satisfied, modulo $$$M = 998~244~353$$$.

## Examples
```input
3 2
0 1 2
1 3 3
```
```output
748683265
```
-----
```input
3 3
0 1 2
0 1 3
0 2 3
```
```output
748683265
```
-----
```input
3 4
0 1 2
0 1 3
1 2 3
1 2 2
```
```output
935854081
```
-----
```input
4 4
0 1 2
0 3 4
1 1 3
1 2 4
```
```output
0
```
-----
```input
8 12
0 1 2
0 2 3
1 3 4
0 1 4
0 5 6
0 6 7
1 7 8
0 5 8
1 3 7
1 3 8
1 4 7
1 4 8
```
```output
997687297
```

## Note
In the first test case, the conditions are $$$x_1+x_2 \le 1$$$ and $$$x_3+x_3\ge 1$$$, and the probability that each condition is satisfied is $$$\frac 12$$$, so the probability that they are both satisfied is $$$\frac 12\cdot \frac 12=\frac 14$$$, modulo $$$998~244~353$$$ is equal to $$$748683265$$$.

In the second test case, the answer is $$$\frac 14$$$.

In the third test case, the answer is $$$\frac 1{16}$$$.

In the fourth test case, the sum of all variables must equal $$$2$$$, so the probability is $$$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 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: 1024.0 MB

# Problem
Tenzing has a beautiful necklace. The necklace consists of $$$n$$$ pearls numbered from $$$1$$$ to $$$n$$$ with a string connecting pearls $$$i$$$ and $$$(i \text{ mod } n)+1$$$ for all $$$1 \leq i \leq n$$$.

One day Tenzing wants to cut the necklace into several parts by cutting some strings. But for each connected part of the necklace, there should not be more than $$$k$$$ pearls. The time needed to cut each string may not be the same. Tenzing needs to spend $$$a_i$$$ minutes cutting the string between pearls $$$i$$$ and $$$(i \text{ mod } n)+1$$$.

Tenzing wants to know the minimum time in minutes to cut the necklace such that each connected part will not have more than $$$k$$$ pearls.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2\leq n\leq 5\cdot 10^5$$$, $$$1\leq k <n$$$).

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

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

## Output Format
For each test case, output the minimum total time in minutes required.

## Examples
```input
4
5 2
1 1 1 1 1
5 2
1 2 3 4 5
6 3
4 2 5 1 3 3
10 3
2 5 6 5 2 1 7 9 7 2
```
```output
3
7
5
15
```

## Note
In the first test case, the necklace will be cut into $$$3$$$ parts: $$$[1,2][3,4][5]$$$, so the total time is $$$3$$$.

In the second test case, the necklace will be cut into $$$3$$$ parts: $$$[5,1][2][3,4]$$$, Tenzing will cut the strings connecting $$$(1,2), (2,3)$$$ and $$$(4,5)$$$, so the total time is $$$a_1+a_2+a_4=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 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
Alphen has an array of positive integers $$$a$$$ of length $$$n$$$.

Alphen can perform the following operation:

- For all $$$i$$$ from $$$1$$$ to $$$n$$$, replace $$$a_i$$$ with $$$\max(0, a_i - 1)$$$.

Alphen will perform the above operation until $$$a$$$ is sorted, that is $$$a$$$ satisfies $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$. How many operations will Alphen perform? Under the constraints of the problem, it can be proven that Alphen will perform a finite number of operations.

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

## Output Format
For each test case, output a single integer — the number of operations that Alphen will perform.

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

## Note
In the first test case, we have $$$a=[1,2,3]$$$. Since $$$a$$$ is already sorted, Alphen will not need to perform any operations. So, the answer is $$$0$$$.

In the second test case, we have $$$a=[2,1,2,1,2]$$$. Since $$$a$$$ is not initially sorted, Alphen will perform one operation to make $$$a=[1,0,1,0,1]$$$. After performing one operation, $$$a$$$ is still not sorted, so Alphen will perform another operation to make $$$a=[0,0,0,0,0]$$$. Since $$$a$$$ is sorted, Alphen will not perform any other operations. Since Alphen has performed two operations in total, the answer is $$$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 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 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 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 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 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: 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 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
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 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 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 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
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.