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
Let's call a sequence of integers $$$x_1, x_2, \dots, x_k$$$ MEX-correct if for all $$$i$$$ ($$$1 \le i \le k$$$) $$$|x_i - \operatorname{MEX}(x_1, x_2, \dots, x_i)| \le 1$$$ holds. Where $$$\operatorname{MEX}(x_1, \dots, x_k)$$$ is the minimum non-negative integer that doesn't belong to the set $$$x_1, \dots, x_k$$$. For example, $$$\operatorname{MEX}(1, 0, 1, 3) = 2$$$ and $$$\operatorname{MEX}(2, 1, 5) = 0$$$.

You are given an array $$$a$$$ consisting of $$$n$$$ non-negative integers. Calculate the number of non-empty MEX-correct subsequences of a given array. The number of subsequences can be very large, so print it modulo $$$998244353$$$.

Note: a subsequence of an array $$$a$$$ is a sequence $$$[a_{i_1}, a_{i_2}, \dots, a_{i_m}]$$$ meeting the constraints $$$1 \le i_1 < i_2 < \dots < i_m \le n$$$. If two different ways to choose the sequence of indices $$$[i_1, i_2, \dots, i_m]$$$ yield the same subsequence, the resulting subsequence should be counted twice (i. e. two subsequences are different if their sequences of indices $$$[i_1, i_2, \dots, i_m]$$$ are not the same).

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

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

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

The sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the number of non-empty MEX-correct subsequences of a given array, taken modulo $$$998244353$$$.

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

## Note
In the first example, the valid subsequences are $$$[0]$$$, $$$[1]$$$, $$$[0,1]$$$ and $$$[0,2]$$$.

In the second example, the valid subsequences are $$$[0]$$$ and $$$[1]$$$.

In the third example, any non-empty subsequence is valid.

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

# Problem
You are given a rooted tree consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. The root of the tree is the vertex $$$1$$$.

You have to color all vertices of the tree into $$$n$$$ colors (also numbered from $$$1$$$ to $$$n$$$) so that there is exactly one vertex for each color. Let $$$c_i$$$ be the color of vertex $$$i$$$, and $$$p_i$$$ be the parent of vertex $$$i$$$ in the rooted tree. The coloring is considered beautiful if there is no vertex $$$k$$$ ($$$k > 1$$$) such that $$$c_k = c_{p_k} - 1$$$, i. e. no vertex such that its color is less than the color of its parent by exactly $$$1$$$.

Calculate the number of beautiful colorings, and print it modulo $$$998244353$$$.

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

Then $$$n-1$$$ lines follow, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) denoting an edge between the vertex $$$x_i$$$ and the vertex $$$y_i$$$. These edges form a tree.

## Output Format
Print one integer — the number of beautiful colorings, taken modulo $$$998244353$$$.

## Examples
```input
5
1 2
3 2
4 2
2 5
```
```output
42
```
-----
```input
5
1 2
2 3
3 4
4 5
```
```output
53
```
-----
```input
20
20 19
20 4
12 4
5 8
1 2
20 7
3 10
7 18
11 8
9 10
17 10
1 15
11 16
14 11
18 10
10 1
14 2
13 17
20 6
```
```output
955085064
```

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
Today, Marin is at a cosplay exhibition and is preparing for a group photoshoot!

For the group picture, the cosplayers form a horizontal line. A group picture is considered beautiful if for every contiguous segment of at least $$$2$$$ cosplayers, the number of males does not exceed the number of females (obviously).

Currently, the line has $$$n$$$ cosplayers which can be described by a binary string $$$s$$$. The $$$i$$$-th cosplayer is male if $$$s_i = 0$$$ and female if $$$s_i = 1$$$. To ensure that the line is beautiful, you can invite some additional cosplayers (possibly zero) to join the line at any position. You can't remove any cosplayer from the line.

Marin wants to know the minimum number of cosplayers you need to invite so that the group picture of all the cosplayers is beautiful. She can't do this on her own, so she's asking you for help. Can you help her?

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

The first line of each test case contains a positive integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the number of cosplayers in the initial line.

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$ — describing the cosplayers already in line. Each character of the string is either 0 describing a male, or 1 describing a female.

Note that there is no limit on the sum of $$$n$$$.

## Output Format
For each test case, print the minimum number of cosplayers you need to invite so that the group picture of all the cosplayers is beautiful.

## Examples
```input
9
3
000
3
001
3
010
3
011
3
100
3
101
3
110
3
111
19
1010110000100000101
```
```output
4
2
1
0
2
0
0
0
17
```

## Note
In the first test case, for each pair of adjacent cosplayers, you can invite two female cosplayers to stand in between them. Then, $$$000 \rightarrow 0110110$$$.

In the third test case, you can invite one female cosplayer to stand next to the second cosplayer. Then, $$$010 \rightarrow 0110$$$.

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
Marin wants you to count number of permutations that are beautiful. A beautiful permutation of length $$$n$$$ is a permutation that has the following property: $$$$$$ \gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) > 1, $$$$$$ where $$$\gcd$$$ is the greatest common divisor.

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
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.

Each test case consists of one line containing one integer $$$n$$$ ($$$1 \le n \le 10^3$$$).

## Output Format
For each test case, print one integer — number of beautiful permutations. Because the answer can be very big, please print the answer modulo $$$998\,244\,353$$$.

## Examples
```input
7
1
2
3
4
5
6
1000
```
```output
0
1
0
4
0
36
665702330
```

## Note
In first test case, we only have one permutation which is $$$[1]$$$ but it is not beautiful because $$$\gcd(1 \cdot 1) = 1$$$.

In second test case, we only have one beautiful permutation which is $$$[2, 1]$$$ because $$$\gcd(1 \cdot 2, 2 \cdot 1) = 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
This is the easy version of the problem. The difference in the constraints between both versions is colored below in red. You can make hacks only if all versions of the problem are solved.

Marin and Gojou are playing hide-and-seek with an array.

Gojou initially performs the following steps:

- First, Gojou chooses $$$2$$$ integers $$$l$$$ and $$$r$$$ such that $$$l \leq r$$$.
- Then, Gojou makes an array $$$a$$$ of length $$$r-l+1$$$ which is a permutation of the array $$$[l,l+1,\ldots,r]$$$.
- Finally, Gojou chooses a secret integer $$$x$$$ and sets $$$a_i$$$ to $$$a_i \oplus x$$$ for all $$$i$$$ (where $$$\oplus$$$ denotes the bitwise XOR operation).

Marin is then given the values of $$$l,r$$$ and the final array $$$a$$$. She needs to find the secret integer $$$x$$$ to win. Can you help her?

Note that there may be multiple possible $$$x$$$ that Gojou could have chosen. Marin can find any possible $$$x$$$ that could have resulted in the final value of $$$a$$$.

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

In the first line of each test case contains two integers $$$l$$$ and $$$r$$$ ($$$ \color{red}{\boldsymbol{0} \boldsymbol{=} \boldsymbol{l}} \le r < 2^{17}$$$).

The second line contains $$$r - l + 1$$$ integers of $$$a_1,a_2,\ldots,a_{r-l+1}$$$ ($$$0 \le a_i < 2^{17}$$$). It is guaranteed that $$$a$$$ can be generated using the steps performed by Gojou.

It is guaranteed that the sum of $$$r - l + 1$$$ over all test cases does not exceed $$$2^{17}$$$.

## Output Format
For each test case print an integer $$$x$$$. If there are multiple answers, print any.

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

## Note
In the first test case, the original array is $$$[3, 2, 1, 0]$$$.

In the second test case, the original array is $$$[0, 3, 2, 1]$$$.

In the third test case, the original array is $$$[2, 1, 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
This is the hard version of the problem. The difference in the constraints between both versions are colored below in red. You can make hacks only if all versions of the problem are solved.

Marin and Gojou are playing hide-and-seek with an array.

Gojou initially perform the following steps:

- First, Gojou chooses $$$2$$$ integers $$$l$$$ and $$$r$$$ such that $$$l \leq r$$$.
- Then, Gojou will make an array $$$a$$$ of length $$$r-l+1$$$ which is a permutation of the array $$$[l,l+1,\ldots,r]$$$.
- Finally, Gojou chooses a secret integer $$$x$$$ and sets $$$a_i$$$ to $$$a_i \oplus x$$$ for all $$$i$$$ (where $$$\oplus$$$ denotes the bitwise XOR operation).

Marin is then given the values of $$$l,r$$$ and the final array $$$a$$$. She needs to find the secret integer $$$x$$$ to win. Can you help her?

Note that there may be multiple possible $$$x$$$ that Gojou could have chosen. Marin can find any possible $$$x$$$ that could have resulted in the final value of $$$a$$$.

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

In the first line of each test case contains two integers $$$l$$$ and $$$r$$$ ($$$\color{red}{\boldsymbol{0} \boldsymbol{\le} \boldsymbol{l}} \le r < 2^{17}$$$).

The second line contains $$$r - l + 1$$$ space-seperated integers of $$$a_1,a_2,\ldots,a_{r-l+1}$$$ ($$$0 \le a_i < 2^{17}$$$). It is guaranteed that array $$$a$$$ is valid.

It is guaranteed that the sum of $$$r - l + 1$$$ over all test cases does not exceed $$$2^{17}$$$.

## Output Format
For each test case print an integer $$$x$$$. If there are multiple answers, print any.

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

## Note
In the first test case, the original array is $$$[7, 6, 5, 4]$$$.

In the second test case, the original array is $$$[4, 7, 6, 5]$$$.

In the third test case, the original array is $$$[3, 1, 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 a positive integer $$$n$$$. You have to find $$$4$$$ positive integers $$$a, b, c, d$$$ such that

- $$$a + b + c + d = n$$$, and
- $$$\gcd(a, b) = \operatorname{lcm}(c, d)$$$.

If there are several possible answers you can output any of them. It is possible to show that the answer always exists.

In this problem $$$\gcd(a, b)$$$ denotes the greatest common divisor of $$$a$$$ and $$$b$$$, and $$$\operatorname{lcm}(c, d)$$$ denotes the least common multiple of $$$c$$$ and $$$d$$$.

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

Each test case contains a single line with integer $$$n$$$ ($$$4 \le n \le 10^9$$$) — the sum of $$$a$$$, $$$b$$$, $$$c$$$, and $$$d$$$.

## Output Format
For each test case output $$$4$$$ positive integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ such that $$$a + b + c + d = n$$$ and $$$\gcd(a, b) = \operatorname{lcm}(c, d)$$$.

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

## Note
In the first test case $$$\gcd(1, 1) = \operatorname{lcm}(1, 1) = 1$$$, $$$1 + 1 + 1 + 1 = 4$$$.

In the second test case $$$\gcd(2, 2) = \operatorname{lcm}(2, 1) = 2$$$, $$$2 + 2 + 2 + 1 = 7$$$.

In the third test case $$$\gcd(2, 2) = \operatorname{lcm}(2, 2) = 2$$$, $$$2 + 2 + 2 + 2 = 8$$$.

In the fourth test case $$$\gcd(2, 4) = \operatorname{lcm}(2, 1) = 2$$$, $$$2 + 4 + 2 + 1 = 9$$$.

In the fifth test case $$$\gcd(3, 5) = \operatorname{lcm}(1, 1) = 1$$$, $$$3 + 5 + 1 + 1 = 10$$$.

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$$$ of $$$n$$$ integers. Initially there is only one copy of the given array.

You can do operations of two types:

1. Choose any array and clone it. After that there is one more copy of the chosen array.
2. Swap two elements from any two copies (maybe in the same copy) on any positions.

You need to find the minimal number of operations needed to obtain a copy where all elements are equal.

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \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 a single integer — the minimal number of operations needed to create at least one copy where all elements are equal.

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

## Note
In the first test case all elements in the array are already equal, that's why the answer is $$$0$$$.

In the second test case it is possible to create a copy of the given array. After that there will be two identical arrays:

$$$[ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]$$$ and $$$[ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]$$$

After that we can swap elements in a way so all zeroes are in one array:

$$$[ \ 0 \ \underline{0} \ \underline{0} \ 3 \ 7 \ 0 \ ]$$$ and $$$[ \ \underline{1} \ 1 \ 3 \ 3 \ 7 \ \underline{3} \ ]$$$

Now let's create a copy of the first array:

$$$[ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]$$$, $$$[ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]$$$ and $$$[ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]$$$

Let's swap elements in the first two copies:

$$$[ \ 0 \ 0 \ 0 \ \underline{0} \ \underline{0} \ 0 \ ]$$$, $$$[ \ \underline{3} \ \underline{7} \ 0 \ 3 \ 7 \ 0 \ ]$$$ and $$$[ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]$$$.

Finally, we made a copy where all elements are equal and made $$$6$$$ operations.

It can be proven that no fewer operations are enough.

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
A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. The parent of a vertex $$$v$$$ (different from root) is the previous to $$$v$$$ vertex on the shortest path from the root to the vertex $$$v$$$. Children of the vertex $$$v$$$ are all vertices for which $$$v$$$ is the parent.

You are given a rooted tree with $$$n$$$ vertices. The vertex $$$1$$$ is the root. Initially, all vertices are healthy.

Each second you do two operations, the spreading operation and, after that, the injection operation:

1. Spreading: for each vertex $$$v$$$, if at least one child of $$$v$$$ is infected, you can spread the disease by infecting at most one other child of $$$v$$$ of your choice.
2. Injection: you can choose any healthy vertex and infect it.

This process repeats each second until the whole tree is infected. You need to find the minimal number of seconds needed to infect the whole tree.

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

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

The second line of each test case contains $$$n - 1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ is the ancestor of the $$$i$$$-th vertex in the tree.

It is guaranteed that the given graph is a tree.

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 you should output a single integer — the minimal number of seconds needed to infect the whole tree.

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

## Note
The image depicts the tree from the first test case during each second.

A vertex is black if it is not infected. A vertex is blue if it is infected by injection during the previous second. A vertex is green if it is infected by spreading during the previous second. A vertex is red if it is infected earlier than the previous second.

Note that you are able to choose which vertices are infected by spreading and by injections.

Now solve the problem and return the code.