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

# Problem
You are given a string $$$s$$$ with length $$$n-1$$$ whose characters are either $$$\texttt{<}$$$ or $$$\texttt{>}$$$.

Count the permutations $$$p_1, \, p_2, \, \dots, \, p_n$$$ of $$$1, \, 2, \, \dots, \, n$$$ such that, for all $$$i = 1, \, 2, \, \dots, \, n - 1$$$, if $$$s_i$$$ is $$$\texttt{<}$$$ then $$$p_i < p_{i+1}$$$ and if $$$s_i$$$ is $$$\texttt{>}$$$ then $$$p_i > p_{i+1}$$$.

Since this number can be very large, compute its logarithm in base $$$2$$$.

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

The second line contains a string $$$s$$$ of length $$$n-1$$$; each character of $$$s$$$ is either $$$\texttt{<}$$$ or $$$\texttt{>}$$$.

## Output Format
Print the logarithm in base $$$2$$$ of the number of permutations satisfying the constraints described in the statement.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, let your answer be $$$x$$$ and let the correct answer be $$$y$$$. Your answer is accepted if and only if $$$\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$$$.

## Examples
```input
2
<
```
```output
0.0000000000
```
-----
```input
3
<>
```
```output
1.0000000000
```
-----
```input
5
><<<
```
```output
2.0000000000
```
-----
```input
10
<><<<<<>>
```
```output
9.8281364842
```

## Note
In the first sample, there is only one valid permutation, that is $$$[2, 1]$$$. Since $$$\log_2(1)=0$$$, the correct output is $$$0$$$.

In the second sample, there are $$$2$$$ valid permutations, that are $$$[3, 1, 2]$$$ and $$$[2, 1, 3]$$$. Since $$$\log_2(2)=1$$$, the correct output is $$$1$$$.

In the third sample, there are $$$4$$$ valid permutations, that are $$$[1, 5, 4, 3, 2]$$$, $$$[2, 5, 4, 3, 1]$$$, $$$[3, 5, 4, 2, 1]$$$, $$$[4, 5, 3, 2, 1]$$$. Since $$$\log_2(4)=2$$$, the correct output is $$$2$$$.

In the fourth sample, there are $$$909$$$ valid permutations. Notice that $$$\log_2(909)=9.828136484194\ldots$$$

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 an integer $$$n$$$.

Find any pair of integers $$$(x,y)$$$ ($$$1\leq x,y\leq n$$$) such that $$$x^y\cdot y+y^x\cdot x = n$$$.

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

Each test case contains one line with a single integer $$$n$$$ ($$$1\leq n\leq 10^9$$$).

## Output Format
For each test case, if possible, print two integers $$$x$$$ and $$$y$$$ ($$$1\leq x,y\leq n$$$). If there are multiple answers, print any.

Otherwise, print $$$-1$$$.

## Examples
```input
5
3
7
42
31250
20732790
```
```output
-1
-1
2 3
5 5
3 13
```

## Note
In the third test case, $$$2^3 \cdot 3+3^2 \cdot 2 = 42$$$, so $$$(2,3),(3,2)$$$ will be considered as legal solutions.

In the fourth test case, $$$5^5 \cdot 5+5^5 \cdot 5 = 31250$$$, so $$$(5,5)$$$ is a legal solution.

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
Given an integer $$$n$$$.

Consider all pairs of integer arrays $$$a$$$ and $$$p$$$ of the same length such that $$$n = \prod a_i^{p_i}$$$ (i.e. $$$a_1^{p_1}\cdot a_2^{p_2}\cdot\ldots$$$) ($$$a_i>1;p_i>0$$$) and $$$a_i$$$ is the product of some (possibly one) distinct prime numbers.

For example, for $$$n = 28 = 2^2\cdot 7^1 = 4^1 \cdot 7^1$$$ the array pair $$$a = [2, 7]$$$, $$$p = [2, 1]$$$ is correct, but the pair of arrays $$$a = [4, 7]$$$, $$$p = [1, 1]$$$ is not, because $$$4=2^2$$$ is a product of non-distinct prime numbers.

Your task is to find the maximum value of $$$\sum a_i \cdot p_i$$$ (i.e. $$$a_1\cdot p_1 + a_2\cdot p_2 + \ldots$$$) over all possible pairs of arrays $$$a$$$ and $$$p$$$. Note that you do not need to minimize or maximize the length of the arrays.

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

Each test case contains only one integer $$$n$$$ ($$$2 \le n \le 10^9$$$).

## Output Format
For each test case, print the maximum value of $$$\sum a_i \cdot p_i$$$.

## Examples
```input
7
100
10
864
130056192
1000000000
2
999999018
```
```output
20
10
22
118
90
2
333333009
```

## Note
In the first test case, $$$100 = 10^2$$$ so that $$$a = [10]$$$, $$$p = [2]$$$ when $$$\sum a_i \cdot p_i$$$ hits the maximum value $$$10\cdot 2 = 20$$$. Also, $$$a = [100]$$$, $$$p = [1]$$$ does not work since $$$100$$$ is not made of distinct prime factors.

In the second test case, we can consider $$$10$$$ as $$$10^1$$$, so $$$a = [10]$$$, $$$p = [1]$$$. Notice that when $$$10 = 2^1\cdot 5^1$$$, $$$\sum a_i \cdot p_i = 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
RSJ has a sequence $$$a$$$ of $$$n$$$ integers $$$a_1,a_2, \ldots, a_n$$$ and an integer $$$s$$$. For each of $$$a_2,a_3, \ldots, a_{n-1}$$$, he chose a pair of non-negative integers $$$x_i$$$ and $$$y_i$$$ such that $$$x_i+y_i=a_i$$$ and $$$(x_i-s) \cdot (y_i-s) \geq 0$$$.

Now he is interested in the value $$$$$$F = a_1 \cdot x_2+y_2 \cdot x_3+y_3 \cdot x_4 + \ldots + y_{n - 2} \cdot x_{n-1}+y_{n-1} \cdot a_n.$$$$$$

Please help him find the minimum possible value $$$F$$$ he can get by choosing $$$x_i$$$ and $$$y_i$$$ optimally. It can be shown that there is always at least one valid way to choose them.

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

The first line of each test case contains two integers $$$n$$$, $$$s$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$0 \le s \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$).

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

## Output Format
For each test case, print the minimum possible value of $$$F$$$.

## Examples
```input
10
5 0
2 0 1 3 4
5 1
5 3 4 3 5
7 2
7 6 5 4 3 2 1
5 1
1 2 3 4 5
5 2
1 2 3 4 5
4 0
0 1 1 1
5 5
4 3 5 6 4
4 1
0 2 1 0
3 99999
200000 200000 200000
6 8139
7976 129785 12984 78561 173685 15480
```
```output
0
18
32
11
14
0
16
0
40000000000
2700826806
```

## Note
In the first test case, $$$2\cdot 0+0\cdot 1+0\cdot 3+0\cdot 4 = 0$$$.

In the second test case, $$$5\cdot 1+2\cdot 2+2\cdot 2+1\cdot 5 = 18$$$.

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 are $$$n$$$ points $$$1,2,\ldots,n$$$, each point $$$i$$$ has a number $$$a_i$$$ on it. You're playing a game on them. Initially, you are at point $$$1$$$. When you are at point $$$i$$$, take following steps:

- If $$$1\le i\le n$$$, go to $$$i+a_i$$$,
- Otherwise, the game ends.

Before the game begins, you can choose two integers $$$x$$$ and $$$y$$$ satisfying $$$1\le x\le n$$$, $$$-n \le y \le n$$$ and replace $$$a_x$$$ with $$$y$$$ (set $$$a_x := y$$$). Find the number of distinct pairs $$$(x,y)$$$ such that the game that you start after making the change ends in a finite number of steps.

Notice that you do not have to satisfy $$$a_x\not=y$$$.

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

The first line of each test case contains one integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the number of points.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-n \le a_i \le n$$$) — the numbers on the axis.

It's guaranteed that the sum of $$$n$$$ does not exceed $$$2\cdot 10^5$$$.

## Output Format
For each test case, print a line containing a single integer — the number of distinct pairs $$$(x,y)$$$ with which the game ends.

## Examples
```input
9
1
0
2
-1 0
2
1 -1
2
1 1
3
-1 -2 -1
3
1 -2 -1
4
-1 4 -2 1
5
1 1 1 1 -4
5
1 1 1 1 1
```
```output
2
8
6
7
20
17
34
30
40
```

## Note
In the first test case, the pairs $$$(x,y)$$$ with which the game ends are $$$(1,-1)$$$ and $$$(1,1)$$$, corresponding to the routes $$$1\rightarrow 0$$$ and $$$1\rightarrow 2$$$. Note that $$$(1,2)$$$ is invalid since when $$$n=1$$$, $$$y=2$$$ violates $$$-n\le y\le n$$$. $$$(1,0)$$$ is also invalid since you will go from $$$1$$$ to $$$1$$$ forever.

In the second test case, the pairs are $$$(1,-2),(1,-1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)$$$.

In the fourth test case, the pairs are $$$(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,1),(2,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 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: 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 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: 10.0 seconds
Memory limit: 1024.0 MB

# Problem
On a permutation $$$p$$$ of length $$$n$$$, we define a bully swap as follows:

- Let $$$i$$$ be the index of the largest element $$$p_i$$$ such that $$$p_i \neq i$$$.
- Let $$$j$$$ be the index of the smallest element $$$p_j$$$ such that $$$i < j$$$.
- Swap $$$p_i$$$ and $$$p_j$$$.

We define $$$f(p)$$$ as the number of bully swaps we need to perform until $$$p$$$ becomes sorted. Note that if $$$p$$$ is the identity permutation, $$$f(p)=0$$$.

You are given $$$n$$$ and a permutation $$$p$$$ of length $$$n$$$. You need to process the following $$$q$$$ updates.

In each update, you are given two integers $$$x$$$ and $$$y$$$. You will swap $$$p_x$$$ and $$$p_y$$$ and then find the value of $$$f(p)$$$.

Note that the updates are persistent. Changes made to the permutation $$$p$$$ will apply when processing future updates.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 5 \cdot 10^5$$$, $$$1 \le q \le 5 \cdot 10^4$$$) — the length of the permutation and the number of updates.

The second line of input contains $$$n$$$ integer $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \leq p_i \leq n$$$) — the permutation $$$p$$$. All elements of $$$p$$$ are distinct.

The $$$i$$$-th of the next $$$q$$$ lines of input contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i < y_i \le n$$$) — describing the $$$i$$$-th update.

## Output Format
After each update, output $$$f(p)$$$.

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

## Note
After the first update, we have $$$f(p)=5$$$. The $$$5$$$ bully swaps are illustrated below.

- $$$[\mathbf{1}, 2, \mathbf{8}, 5, 3, 4, 7, 6]$$$,
- $$$[1, 2, \mathbf{3}, 5, \mathbf{8}, 4, 7, 6]$$$,
- $$$[1, 2, 3, 5, \mathbf{4}, \mathbf{8}, 7, 6]$$$,
- $$$[1, 2, 3, 5, 4, \mathbf{6}, 7, \mathbf{8}]$$$,
- $$$[1, 2, 3, \mathbf{4}, \mathbf{5}, 6, 7, 8]$$$.

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 an array consisting of $$$n$$$ integers. Your task is to determine whether it is possible to color all its elements in two colors in such a way that the sums of the elements of both colors have the same parity and each color has at least one element colored.

For example, if the array is [$$$1,2,4,3,2,3,5,4$$$], we can color it as follows: [$$$\color{blue}{1},\color{blue}{2},\color{red}{4},\color{blue}{3},\color{red}{2},\color{red}{3},\color{red}{5},\color{red}{4}$$$], where the sum of the blue elements is $$$6$$$ and the sum of the red elements is $$$18$$$.

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

Each test case begins with a line containing an integer $$$n$$$ ($$$2 \le n \le 50$$$) — the length of the array $$$a$$$.

The next line contains $$$n$$$ integers $$$a_1,a_2, \dots, a_n$$$ ($$$1 \le a_i \le 50$$$) — the elements of the array $$$a$$$.

## Output Format
For each test case, output "YES" (without quotes) if it is possible to color the array in two colors in such a way that the sums of the elements of both colors have the same parity and each color has at least one element colored, and "NO" otherwise.

You can output "Yes" and "No" in any case (for example, the strings "yES", "yes", and "Yes" will be recognized as correct answers).

## Examples
```input
7
8
1 2 4 3 2 3 5 4
2
4 7
3
3 9 8
2
1 7
5
5 4 3 2 1
4
4 3 4 5
2
50 48
```
```output
YES
NO
YES
YES
NO
YES
YES
```

## Note
The first sample is described in the statement.

In the second sample, there are only two colorings $$$[\color{blue}{4},\color{red}{7}]$$$ and $$$[\color{red}{4},\color{blue}{7}]$$$ , but in both cases the parity of sums is different.

In the third sample, you can color $$$[\color{blue}{3},\color{blue}{9},\color{red}{8}]$$$ and $$$12$$$ and $$$8$$$ are both even.

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
Sasha has an array $$$a$$$ of $$$n$$$ integers. He got bored and for all $$$i$$$, $$$j$$$ ($$$i < j$$$), he wrote down the minimum value of $$$a_i$$$ and $$$a_j$$$. He obtained a new array $$$b$$$ of size $$$\frac{n\cdot (n-1)}{2}$$$.

For example, if $$$a=$$$ [$$$2,3,5,1$$$], he would write [$$$\min(2, 3), \min(2, 5), \min(2, 1), \min(3, 5), \min(3, 1), min(5, 1)$$$] $$$=$$$ [$$$2, 2, 1, 3, 1, 1$$$].

Then, he randomly shuffled all the elements of the array $$$b$$$.

Unfortunately, he forgot the array $$$a$$$, and your task is to restore any possible array $$$a$$$ from which the array $$$b$$$ could have been obtained.

The elements of array $$$a$$$ should be in the range $$$[-10^9,10^9]$$$.

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

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

The second line of each test case contains $$$\frac{n\cdot (n-1)}{2}$$$ integers $$$b_1,b_2,\dots,b_{\frac{n\cdot (n-1)}{2}}$$$ ($$$−10^9\le b_i\le 10^9$$$) — the elements of array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all tests does not exceed $$$10^3$$$ and for each array $$$b$$$ in the test, there exists an original array.

## Output Format
For each test case, output any possible array $$$a$$$ of length $$$n$$$.

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

## Note
In the first sample, Sasha chose the array $$$[1,3,3]$$$, then the array $$$b$$$ will look like $$$[\min(a_1,a_2)=1, \min(a_1,a_3)=1, \min(a_2,a_3)=3]$$$, after shuffling its elements, the array can look like $$$[1,3,1]$$$.

In the second sample, there is only one pair, so the array $$$[10,10]$$$ is suitable. Another suitable array could be $$$[15,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 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
Given two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$. Elements of both arrays indexed from $$$1$$$ to $$$n$$$. You are constructing a directed graph, where edge from $$$u$$$ to $$$v$$$ ($$$u\neq v$$$) exists if $$$a_u-a_v \ge b_u-b_v$$$.

A vertex $$$V$$$ is called strong if there exists a path from $$$V$$$ to all other vertices.

A path in a directed graph is a chain of several vertices, connected by edges, such that moving from the vertex $$$u$$$, along the directions of the edges, the vertex $$$v$$$ can be reached.

Your task is to find all strong vertices.

For example, if $$$a=[3,1,2,4]$$$ and $$$b=[4,3,2,1]$$$, the graph will look like this:

The graph has only one strong vertex with number $$$4$$$

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

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 2\cdot 10^5$$$) — the length of $$$a$$$ and $$$b$$$.

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

The third line of each test case contains $$$n$$$ integers $$$b_1,b_2 \dots b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$) — the array $$$b$$$.

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

## Output Format
For each test case, output two lines: in the first line, output the number of strong vertices, and in the second line, output all strong vertices in ascending order.

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

## Note
The first sample is covered in the problem statement.

For the second sample, the graph looks like this:

The graph has two strong vertices with numbers $$$3$$$ and $$$5$$$. Note that there is a bidirectional edge between vertices $$$3$$$ and $$$5$$$.

In the third sample, the vertices are connected by a single directed edge from vertex $$$2$$$ to vertex $$$1$$$, so the only strong vertex is $$$2$$$.

In the fourth sample, all vertices are connected to each other by bidirectional edges, so there is a path from every vertex to any other vertex.

Now solve the problem and return the code.