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
The statement of this problem is the same as the statement of problem C2. The only difference is that, in problem C1, $$$n$$$ is always even, and in C2, $$$n$$$ is always odd.

You are given a regular polygon with $$$2 \cdot n$$$ vertices (it's convex and has equal sides and equal angles) and all its sides have length $$$1$$$. Let's name it as $$$2n$$$-gon.

Your task is to find the square of the minimum size such that you can embed $$$2n$$$-gon in the square. Embedding $$$2n$$$-gon in the square means that you need to place $$$2n$$$-gon in the square in such way that each point which lies inside or on a border of $$$2n$$$-gon should also lie inside or on a border of the square.

You can rotate $$$2n$$$-gon and/or the square.

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

Next $$$T$$$ lines contain descriptions of test cases — one per line. Each line contains single even integer $$$n$$$ ($$$2 \le n \le 200$$$). Don't forget you need to embed $$$2n$$$-gon, not an $$$n$$$-gon.

## Output Format
Print $$$T$$$ real numbers — one per test case. For each test case, print the minimum length of a side of the square $$$2n$$$-gon can be embedded in. Your answer will be considered correct if its absolute or relative error doesn't exceed $$$10^{-6}$$$.

## Examples
```input
3
2
4
200
```
```output
1.000000000
2.414213562
127.321336469
```

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
The statement of this problem is the same as the statement of problem C1. The only difference is that, in problem C1, $$$n$$$ is always even, and in C2, $$$n$$$ is always odd.

You are given a regular polygon with $$$2 \cdot n$$$ vertices (it's convex and has equal sides and equal angles) and all its sides have length $$$1$$$. Let's name it as $$$2n$$$-gon.

Your task is to find the square of the minimum size such that you can embed $$$2n$$$-gon in the square. Embedding $$$2n$$$-gon in the square means that you need to place $$$2n$$$-gon in the square in such way that each point which lies inside or on a border of $$$2n$$$-gon should also lie inside or on a border of the square.

You can rotate $$$2n$$$-gon and/or the square.

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

Next $$$T$$$ lines contain descriptions of test cases — one per line. Each line contains single odd integer $$$n$$$ ($$$3 \le n \le 199$$$). Don't forget you need to embed $$$2n$$$-gon, not an $$$n$$$-gon.

## Output Format
Print $$$T$$$ real numbers — one per test case. For each test case, print the minimum length of a side of the square $$$2n$$$-gon can be embedded in. Your answer will be considered correct if its absolute or relative error doesn't exceed $$$10^{-6}$$$.

## Examples
```input
3
3
5
199
```
```output
1.931851653
3.196226611
126.687663595
```

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 undirected graph without self-loops or multiple edges which consists of $$$n$$$ vertices and $$$m$$$ edges. Also you are given three integers $$$n_1$$$, $$$n_2$$$ and $$$n_3$$$.

Can you label each vertex with one of three numbers 1, 2 or 3 in such way, that:

1. Each vertex should be labeled by exactly one number 1, 2 or 3;
2. The total number of vertices with label 1 should be equal to $$$n_1$$$;
3. The total number of vertices with label 2 should be equal to $$$n_2$$$;
4. The total number of vertices with label 3 should be equal to $$$n_3$$$;
5. $$$|col_u - col_v| = 1$$$ for each edge $$$(u, v)$$$, where $$$col_x$$$ is the label of vertex $$$x$$$.

If there are multiple valid labelings, print any of them.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5000$$$; $$$0 \le m \le 10^5$$$) — the number of vertices and edges in the graph.

The second line contains three integers $$$n_1$$$, $$$n_2$$$ and $$$n_3$$$ ($$$0 \le n_1, n_2, n_3 \le n$$$) — the number of labels 1, 2 and 3, respectively. It's guaranteed that $$$n_1 + n_2 + n_3 = n$$$.

Next $$$m$$$ lines contan description of edges: the $$$i$$$-th line contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$) — the vertices the $$$i$$$-th edge connects. It's guaranteed that the graph doesn't contain self-loops or multiple edges.

## Output Format
If valid labeling exists then print "YES" (without quotes) in the first line. In the second line print string of length $$$n$$$ consisting of 1, 2 and 3. The $$$i$$$-th letter should be equal to the label of the $$$i$$$-th vertex.

If there is no valid labeling, print "NO" (without quotes).

## Examples
```input
6 3
2 2 2
3 1
5 4
2 5
```
```output
YES
112323
```
-----
```input
5 9
0 2 3
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
```
```output
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Ashish and Vivek play a game on a matrix consisting of $$$n$$$ rows and $$$m$$$ columns, where they take turns claiming cells. Unclaimed cells are represented by $$$0$$$, while claimed cells are represented by $$$1$$$. The initial state of the matrix is given. There can be some claimed cells in the initial state.

In each turn, a player must claim a cell. A cell may be claimed if it is unclaimed and does not share a row or column with any other already claimed cells. When a player is unable to make a move, he loses and the game ends.

If Ashish and Vivek take turns to move and Ashish goes first, determine the winner of the game if both of them are playing optimally.

Optimal play between two players means that both players choose the best possible strategy to achieve the best possible outcome for themselves.

## Input Format
The first line consists of a single integer $$$t$$$ $$$(1 \le t \le 50)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case consists of two space-separated integers $$$n$$$, $$$m$$$ $$$(1 \le n, m \le 50)$$$ — the number of rows and columns in the matrix.

The following $$$n$$$ lines consist of $$$m$$$ integers each, the $$$j$$$-th integer on the $$$i$$$-th line denoting $$$a_{i,j}$$$ $$$(a_{i,j} \in \{0, 1\})$$$.

## Output Format
For each test case if Ashish wins the game print "Ashish" otherwise print "Vivek" (without quotes).

## Examples
```input
4
2 2
0 0
0 0
2 2
0 0
0 1
2 3
1 0 1
1 1 0
3 3
1 0 0
0 0 0
1 0 0
```
```output
Vivek
Ashish
Vivek
Ashish
```

## Note
For the first case: One possible scenario could be: Ashish claims cell $$$(1, 1)$$$, Vivek then claims cell $$$(2, 2)$$$. Ashish can neither claim cell $$$(1, 2)$$$, nor cell $$$(2, 1)$$$ as cells $$$(1, 1)$$$ and $$$(2, 2)$$$ are already claimed. Thus Ashish loses. It can be shown that no matter what Ashish plays in this case, Vivek will win.

For the second case: Ashish claims cell $$$(1, 1)$$$, the only cell that can be claimed in the first move. After that Vivek has no moves left.

For the third case: Ashish cannot make a move, so Vivek wins.

For the fourth case: If Ashish claims cell $$$(2, 3)$$$, Vivek will have no moves left.

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
Ashish has $$$n$$$ elements arranged in a line.

These elements are represented by two integers $$$a_i$$$ — the value of the element and $$$b_i$$$ — the type of the element (there are only two possible types: $$$0$$$ and $$$1$$$). He wants to sort the elements in non-decreasing values of $$$a_i$$$.

He can perform the following operation any number of times:

- Select any two elements $$$i$$$ and $$$j$$$ such that $$$b_i \ne b_j$$$ and swap them. That is, he can only swap two elements of different types in one move.

Tell him if he can sort the elements in non-decreasing values of $$$a_i$$$ after performing any number of operations.

## Input Format
The first line contains one 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 one integer $$$n$$$ $$$(1 \le n \le 500)$$$ — the size of the arrays.

The second line contains $$$n$$$ integers $$$a_i$$$ $$$(1 \le a_i \le 10^5)$$$  — the value of the $$$i$$$-th element.

The third line containts $$$n$$$ integers $$$b_i$$$ $$$(b_i \in \{0, 1\})$$$  — the type of the $$$i$$$-th element.

## Output Format
For each test case, print "Yes" or "No" (without quotes) depending on whether it is possible to sort elements in non-decreasing order of their value.

You may print each letter in any case (upper or lower).

## Examples
```input
5
4
10 20 20 30
0 1 0 1
3
3 1 2
0 1 1
4
2 2 4 8
1 1 1 1
3
5 15 4
0 0 0
4
20 10 100 50
1 0 0 1
```
```output
Yes
Yes
Yes
No
Yes
```

## Note
For the first case: The elements are already in sorted order.

For the second case: Ashish may first swap elements at positions $$$1$$$ and $$$2$$$, then swap elements at positions $$$2$$$ and $$$3$$$.

For the third case: The elements are already in sorted order.

For the fourth case: No swap operations may be performed as there is no pair of elements $$$i$$$ and $$$j$$$ such that $$$b_i \ne b_j$$$. The elements cannot be sorted.

For the fifth case: Ashish may swap elements at positions $$$3$$$ and $$$4$$$, then elements at positions $$$1$$$ and $$$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
Vivek has encountered a problem. He has a maze that can be represented as an $$$n \times m$$$ grid. Each of the grid cells may represent the following:

- Empty — '.'
- Wall — '#'
- Good person  — 'G'
- Bad person — 'B'

The only escape from the maze is at cell $$$(n, m)$$$.

A person can move to a cell only if it shares a side with their current cell and does not contain a wall. Vivek wants to block some of the empty cells by replacing them with walls in such a way, that all the good people are able to escape, while none of the bad people are able to. A cell that initially contains 'G' or 'B' cannot be blocked and can be travelled through.

Help him determine if there exists a way to replace some (zero or more) empty cells with walls to satisfy the above conditions.

It is guaranteed that the cell $$$(n,m)$$$ is empty. Vivek can also block this cell.

## Input Format
The first line contains one 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$$$, $$$m$$$ $$$(1 \le n, m \le 50)$$$ — the number of rows and columns in the maze.

Each of the next $$$n$$$ lines contain $$$m$$$ characters. They describe the layout of the maze. If a character on a line equals '.', the corresponding cell is empty. If it equals '#', the cell has a wall. 'G' corresponds to a good person and 'B' corresponds to a bad person.

## Output Format
For each test case, print "Yes" if there exists a way to replace some empty cells with walls to satisfy the given conditions. Otherwise print "No"

You may print every letter in any case (upper or lower).

## Examples
```input
6
1 1
.
1 2
G.
2 2
#B
G.
2 3
G.#
B#.
3 3
#B.
#..
GG.
2 2
#B
B.
```
```output
Yes
Yes
No
No
Yes
Yes
```

## Note
For the first and second test cases, all conditions are already satisfied.

For the third test case, there is only one empty cell $$$(2,2)$$$, and if it is replaced with a wall then the good person at $$$(1,2)$$$ will not be able to escape.

For the fourth test case, the good person at $$$(1,1)$$$ cannot escape.

For the fifth test case, Vivek can block the cells $$$(2,3)$$$ and $$$(2,2)$$$.

For the last test case, Vivek can block the destination cell $$$(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 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
Ridhiman challenged Ashish to find the maximum valued subsequence of an array $$$a$$$ of size $$$n$$$ consisting of positive integers.

The value of a non-empty subsequence of $$$k$$$ elements of $$$a$$$ is defined as $$$\sum 2^i$$$ over all integers $$$i \ge 0$$$ such that at least $$$\max(1, k - 2)$$$ elements of the subsequence have the $$$i$$$-th bit set in their binary representation (value $$$x$$$ has the $$$i$$$-th bit set in its binary representation if $$$\lfloor \frac{x}{2^i} \rfloor \mod 2$$$ is equal to $$$1$$$).

Recall that $$$b$$$ is a subsequence of $$$a$$$, if $$$b$$$ can be obtained by deleting some(possibly zero) elements from $$$a$$$.

Help Ashish find the maximum value he can get by choosing some subsequence of $$$a$$$.

## Input Format
The first line of the input consists of a single integer $$$n$$$ $$$(1 \le n \le 500)$$$ — the size of $$$a$$$.

The next line consists of $$$n$$$ space-separated integers — the elements of the array $$$(1 \le a_i \le 10^{18})$$$.

## Output Format
Print a single integer — the maximum value Ashish can get by choosing some subsequence of $$$a$$$.

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

## Note
For the first test case, Ashish can pick the subsequence $$$\{{2, 3}\}$$$ of size $$$2$$$. The binary representation of $$$2$$$ is 10 and that of $$$3$$$ is 11. Since $$$\max(k - 2, 1)$$$ is equal to $$$1$$$, the value of the subsequence is $$$2^0 + 2^1$$$ (both $$$2$$$ and $$$3$$$ have $$$1$$$-st bit set in their binary representation and $$$3$$$ has $$$0$$$-th bit set in its binary representation). Note that he could also pick the subsequence $$$\{{3\}}$$$ or $$$\{{2, 1, 3\}}$$$.

For the second test case, Ashish can pick the subsequence $$$\{{3, 4\}}$$$ with value $$$7$$$.

For the third test case, Ashish can pick the subsequence $$$\{{1\}}$$$ with value $$$1$$$.

For the fourth test case, Ashish can pick the subsequence $$$\{{7, 7\}}$$$ with value $$$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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Ayush, Ashish and Vivek are busy preparing a new problem for the next Codeforces round and need help checking if their test cases are valid.

Each test case consists of an integer $$$n$$$ and two arrays $$$a$$$ and $$$b$$$, of size $$$n$$$. If after some (possibly zero) operations described below, array $$$a$$$ can be transformed into array $$$b$$$, the input is said to be valid. Otherwise, it is invalid.

An operation on array $$$a$$$ is:

- select an integer $$$k$$$ $$$(1 \le k \le \lfloor\frac{n}{2}\rfloor)$$$
- swap the prefix of length $$$k$$$ with the suffix of length $$$k$$$

For example, if array $$$a$$$ initially is $$$\{1, 2, 3, 4, 5, 6\}$$$, after performing an operation with $$$k = 2$$$, it is transformed into $$$\{5, 6, 3, 4, 1, 2\}$$$.

Given the set of test cases, help them determine if each one is valid or invalid.

## Input Format
The first line contains one integer $$$t$$$ $$$(1 \le t \le 500)$$$ — the number of test cases. The description of each test case is as follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 500)$$$ — the size of the arrays.

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

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

## Output Format
For each test case, print "Yes" if the given input is valid. Otherwise print "No".

You may print the answer in any case.

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

## Note
For the first test case, we can swap prefix $$$a[1:1]$$$ with suffix $$$a[2:2]$$$ to get $$$a=[2, 1]$$$.

For the second test case, $$$a$$$ is already equal to $$$b$$$.

For the third test case, it is impossible since we cannot obtain $$$3$$$ in $$$a$$$.

For the fourth test case, we can first swap prefix $$$a[1:1]$$$ with suffix $$$a[4:4]$$$ to obtain $$$a=[2, 2, 3, 1]$$$. Now we can swap prefix $$$a[1:2]$$$ with suffix $$$a[3:4]$$$ to obtain $$$a=[3, 1, 2, 2]$$$.

For the fifth test case, it is impossible to convert $$$a$$$ to $$$b$$$.

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 two arrays of integers $$$a_1,\ldots,a_n$$$ and $$$b_1,\ldots,b_m$$$.

Your task is to find a non-empty array $$$c_1,\ldots,c_k$$$ that is a subsequence of $$$a_1,\ldots,a_n$$$, and also a subsequence of $$$b_1,\ldots,b_m$$$. If there are multiple answers, find one of the smallest possible length. If there are still multiple of the smallest possible length, find any. If there are no such arrays, you should report about it.

A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero) elements. For example, $$$[3,1]$$$ is a subsequence of $$$[3,2,1]$$$ and $$$[4,3,1]$$$, but not a subsequence of $$$[1,3,3,7]$$$ and $$$[3,10,4]$$$.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1\le t\le 1000$$$)  — the number of test cases. Next $$$3t$$$ lines contain descriptions of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 1000$$$)  — the lengths of the two arrays.

The second line of each test case contains $$$n$$$ integers $$$a_1,\ldots,a_n$$$ ($$$1\le a_i\le 1000$$$)  — the elements of the first array.

The third line of each test case contains $$$m$$$ integers $$$b_1,\ldots,b_m$$$ ($$$1\le b_i\le 1000$$$)  — the elements of the second array.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ across all test cases does not exceed $$$1000$$$ ($$$\sum\limits_{i=1}^t n_i, \sum\limits_{i=1}^t m_i\le 1000$$$).

## Output Format
For each test case, output "YES" if a solution exists, or "NO" otherwise.

If the answer is "YES", on the next line output an integer $$$k$$$ ($$$1\le k\le 1000$$$)  — the length of the array, followed by $$$k$$$ integers $$$c_1,\ldots,c_k$$$ ($$$1\le c_i\le 1000$$$)  — the elements of the array.

If there are multiple solutions with the smallest possible $$$k$$$, output any.

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

## Note
In the first test case, $$$[4]$$$ is a subsequence of $$$[10, 8, 6, 4]$$$ and $$$[1, 2, 3, 4, 5]$$$. This array has length $$$1$$$, it is the smallest possible length of a subsequence of both $$$a$$$ and $$$b$$$.

In the third test case, no non-empty subsequences of both $$$[3]$$$ and $$$[2]$$$ exist, so the answer is "NO".

Now solve the problem and return the code.