vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Ivan wants to make a necklace as a present to his beloved girl. A necklace is a cyclic sequence of beads of different colors. Ivan says that necklace is beautiful relative to the cut point between two adjacent beads, if the chain of beads remaining after this cut is a palindrome (reads the same forward and backward).

 [Image] 

Ivan has beads of n colors. He wants to make a necklace, such that it's beautiful relative to as many cuts as possible. He certainly wants to use all the beads. Help him to make the most beautiful necklace.


-----Input-----

The first line of the input contains a single number n (1 ≤ n ≤ 26) — the number of colors of beads. The second line contains after n positive integers a_{i}   — the quantity of beads of i-th color. It is guaranteed that the sum of a_{i} is at least 2 and does not exceed 100 000.


-----Output-----

In the first line print a single number — the maximum number of beautiful cuts that a necklace composed from given beads may have. In the second line print any example of such necklace.

Each color of the beads should be represented by the corresponding lowercase English letter (starting with a). As the necklace is cyclic, print it starting from any point.


-----Examples-----
Input
3
4 2 1

Output
1
abacaba
Input
1
4

Output
4
aaaa

Input
2
1 1

Output
0
ab



-----Note-----

In the first sample a necklace can have at most one beautiful cut. The example of such a necklace is shown on the picture.

In the second sample there is only one way to compose a necklace.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a table a of size 2 × n (i.e. two rows and n columns) consisting of integers from 1 to n.

In one move, you can choose some column j (1 ≤ j ≤ n) and swap values a_{1, j} and a_{2, j} in it. Each column can be chosen no more than once.

Your task is to find the minimum number of moves required to obtain permutations of size n in both first and second rows of the table or determine if it is impossible to do that.

You have to answer t independent test cases.

Recall that the permutation of size n is such an array of size n that contains each integer from 1 to n exactly once (the order of elements doesn't matter).

Input

The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of columns in the table. The second line of the test case contains n integers a_{1, 1}, a_{1, 2}, ..., a_{1, n} (1 ≤ a_{1, i} ≤ n), where a_{1, i} is the i-th element of the first row of the table. The third line of the test case contains n integers a_{2, 1}, a_{2, 2}, ..., a_{2, n} (1 ≤ a_{2, i} ≤ n), where a_{2, i} is the i-th element of the second row of the table.

It is guaranteed that the sum of n does not exceed 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5).

Output

For each test case print the answer: -1 if it is impossible to obtain permutation of size n in both first and the second rows of the table, or one integer k in the first line, where k is the minimum number of moves required to obtain permutations in both rows, and k distinct integers pos_1, pos_2, ..., pos_k in the second line (1 ≤ pos_i ≤ n) in any order — indices of columns in which you need to swap values to obtain permutations in both rows. If there are several answers, you can print any.

Example

Input


6
4
1 2 3 4
2 3 1 4
5
5 3 5 1 4
1 2 3 2 4
3
1 2 1
3 3 2
4
1 2 2 1
3 4 3 4
4
4 3 1 4
3 2 2 1
3
1 1 2
3 2 2


Output


0

2
2 3 
1
1 
2
3 4 
2
3 4 
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A beautiful sequence is a strictly increasing sequence, in which the term A_{i} divides all A_{j}, where j>i. Given N find a beautiful sequence whose last term is N and the length of the sequence is the maximum possible. If there are multiple solutions return any.
 
Example 1:
Input: N = 10
Output: 1 5 10
Explanation: 10 is divisible by
1 and 5, 5 is divisible by 1.
Example 2:
Input: N = 3
Output: 1 3
Explanation: 3 is divisible by 1.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function FindSequenece() which takes N as an input parameter and returns a list of beautiful sequences. The driver will print two space-separated integers the length of the sequence and an integer x where x = 1 if your sequence is beautiful otherwise x = 0.
 
Expected Time Complexity: O(sqrt(N))
Expected Space Complexity: O(sqrt(N))
 
Constraints:
1 < N < 10^{9}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're given a row with $n$ chairs. We call a seating of people "maximal" if the two following conditions hold:  There are no neighbors adjacent to anyone seated.  It's impossible to seat one more person without violating the first rule. 

The seating is given as a string consisting of zeros and ones ($0$ means that the corresponding seat is empty, $1$ — occupied). The goal is to determine whether this seating is "maximal".

Note that the first and last seats are not adjacent (if $n \ne 2$).


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 1000$) — the number of chairs.

The next line contains a string of $n$ characters, each of them is either zero or one, describing the seating.


-----Output-----

Output "Yes" (without quotation marks) if the seating is "maximal". Otherwise print "No".

You are allowed to print letters in whatever case you'd like (uppercase or lowercase).


-----Examples-----
Input
3
101

Output
Yes

Input
4
1011

Output
No

Input
5
10001

Output
No



-----Note-----

In sample case one the given seating is maximal.

In sample case two the person at chair three has a neighbour to the right.

In sample case three it is possible to seat yet another person into chair three.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n.
The bus goes along both directions i.e. clockwise and counterclockwise.
Return the shortest distance between the given start and destination stops.
 
Example 1:

Input: distance = [1,2,3,4], start = 0, destination = 1
Output: 1
Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.
 
Example 2:

Input: distance = [1,2,3,4], start = 0, destination = 2
Output: 3
Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.

 
Example 3:

Input: distance = [1,2,3,4], start = 0, destination = 3
Output: 4
Explanation: Distance between 0 and 3 is 6 or 4, minimum is 4.

 
Constraints:

1 <= n <= 10^4
distance.length == n
0 <= start, destination < n
0 <= distance[i] <= 10^4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions is the maximum value of $n$.

You are given a positive integer number $n$. You really love good numbers so you want to find the smallest good number greater than or equal to $n$.

The positive integer is called good if it can be represented as a sum of distinct powers of $3$ (i.e. no duplicates of powers of $3$ are allowed).

For example:

  $30$ is a good number: $30 = 3^3 + 3^1$,  $1$ is a good number: $1 = 3^0$,  $12$ is a good number: $12 = 3^2 + 3^1$,  but $2$ is not a good number: you can't represent it as a sum of distinct powers of $3$ ($2 = 3^0 + 3^0$),  $19$ is not a good number: you can't represent it as a sum of distinct powers of $3$ (for example, the representations $19 = 3^2 + 3^2 + 3^0 = 3^2 + 3^1 + 3^1 + 3^1 + 3^0$ are invalid),  $20$ is also not a good number: you can't represent it as a sum of distinct powers of $3$ (for example, the representation $20 = 3^2 + 3^2 + 3^0 + 3^0$ is invalid). 

Note, that there exist other representations of $19$ and $20$ as sums of powers of $3$ but none of them consists of distinct powers of $3$.

For the given positive integer $n$ find such smallest $m$ ($n \le m$) that $m$ is a good number.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 500$) — the number of queries. Then $q$ queries follow.

The only line of the query contains one integer $n$ ($1 \le n \le 10^{18}$).


-----Output-----

For each query, print such smallest integer $m$ (where $n \le m$) that $m$ is a good number.


-----Example-----
Input
8
1
2
6
13
14
3620
10000
1000000000000000000

Output
1
3
9
13
27
6561
19683
1350851717672992089

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

A tuple $(a, b, c)$ is considered good if it consists of three prime numbers $a$, $b$ and $c$ such that $a < b < c ≤ N$ and $a + b = c$.

Two tuples are considered different if they differ in at least one position. Given $N$, find the number of good tuples that can be formed by integers from $1$ to $N$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The following $T$ lines contain a single integer $N$.

------  Output ------
For each test case, print a single line containing one integer — the number of good tuples which can be formed using integers from $1$ to $N$.

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{6}$

----- Sample Input 1 ------ 
2

3

6
----- Sample Output 1 ------ 
0

1
----- explanation 1 ------ 
Example case 1: There are no good tuples. $(1, 2, 3)$ is not a good tuple since $1$ is not prime.

Example case 2: $(2, 3, 5)$ is a good tuple since $2$, $3$ and $5$ are prime and $2 + 3 = 5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has an array A of length N.

In one operation, Chef can choose any two distinct indices i, j (1 ≤ i, j ≤ N, i \neq j) and either change A_{i} to A_{j} or change A_{j} to A_{i}.

Find the minimum number of operations required to make all the elements of the array equal.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- First line of each test case consists of an integer N - denoting the size of array A.
- Second line of each test case consists of N space-separated integers A_{1}, A_{2}, \dots, A_{N} - denoting the array A.

------ Output Format ------ 

For each test case, output the minimum number of operations required to make all the elements equal.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 1000$
$1 ≤ A_{i} ≤ 1000$

----- Sample Input 1 ------ 
4
3
1 2 3
4
5 5 5 5
4
2 2 1 1
3
1 1 2

----- Sample Output 1 ------ 
2
0
2
1

----- explanation 1 ------ 
Test Case $1$: You can make all the elements equal in $2$ operations. In the first operation, you can choose indices $1, 2$ and convert $A_{1}$ to $A_{2}$. So the array becomes $[2, 2, 3]$. Now you can choose indices $1, 3$ and convert $A_{3}$ to $A_{1}$, so the final array becomes $[2, 2, 2]$.

Test Case $2$: Since all the elements are already equal there is no need to perform any operation.

Test Case $3$: You can make all the elements equal in $2$ operations. In the first operation, you can choose indices $1, 3$ and convert $A_{1}$ to $A_{3}$. So the array becomes $[1, 2, 1, 1]$. Now you can choose indices $1, 2$ and convert $A_{2}$ to $A_{1}$, so the final array becomes $[1, 1, 1, 1]$.

Test Case $4$: You can make all the elements equal in $1$ operation. You can pick indices $2, 3$ and convert $A_{3}$ to $A_{2}$ after which the array becomes $[1, 1, 1]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Now that Heidi has made sure her Zombie Contamination level checker works, it's time to strike! This time, the zombie lair is a strictly convex polygon on the lattice. Each vertex of the polygon occupies a point on the lattice. For each cell of the lattice, Heidi knows the level of Zombie Contamination – the number of corners of the cell that are inside or on the border of the lair.

Given this information, Heidi wants to know the exact shape of the lair to rain destruction on the zombies. Help her!

[Image]


-----Input-----

The input contains multiple test cases.

The first line of each test case contains one integer N, the size of the lattice grid (5 ≤ N ≤ 500). The next N lines each contain N characters, describing the level of Zombie Contamination of each cell in the lattice. Every character of every line is a digit between 0 and 4. 

Cells are given in the same order as they are shown in the picture above: rows go in the decreasing value of y coordinate, and in one row cells go in the order of increasing x coordinate. This means that the first row corresponds to cells with coordinates (1, N), ..., (N, N) and the last row corresponds to cells with coordinates (1, 1), ..., (N, 1).

The last line of the file contains a zero. This line should not be treated as a test case. The sum of the N values for all tests in one file will not exceed 5000.


-----Output-----

For each test case, give the following output:

The first line of the output should contain one integer V, the number of vertices of the polygon that is the secret lair. The next V lines each should contain two integers, denoting the vertices of the polygon in the clockwise order, starting from the lexicographically smallest vertex.


-----Examples-----
Input
8
00000000
00000110
00012210
01234200
02444200
01223200
00001100
00000000
5
00000
01210
02420
01210
00000
7
0000000
0122100
0134200
0013200
0002200
0001100
0000000
0

Output
4
2 3
2 4
6 6
5 2
4
2 2
2 3
3 3
3 2
3
2 5
4 5
4 2



-----Note-----

It is guaranteed that the solution always exists and is unique. It is guaranteed that in the correct solution the coordinates of the polygon vertices are between 2 and N - 2. A vertex (x_1, y_1) is lexicographically smaller than vertex (x_2, y_2) if x_1 < x_2 or $x_{1} = x_{2} \wedge y_{1} < y_{2}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently, Petya learned about a new game "Slay the Dragon". As the name suggests, the player will have to fight with dragons. To defeat a dragon, you have to kill it and defend your castle. To do this, the player has a squad of $n$ heroes, the strength of the $i$-th hero is equal to $a_i$.

According to the rules of the game, exactly one hero should go kill the dragon, all the others will defend the castle. If the dragon's defense is equal to $x$, then you have to send a hero with a strength of at least $x$ to kill it. If the dragon's attack power is $y$, then the total strength of the heroes defending the castle should be at least $y$.

The player can increase the strength of any hero by $1$ for one gold coin. This operation can be done any number of times.

There are $m$ dragons in the game, the $i$-th of them has defense equal to $x_i$ and attack power equal to $y_i$. Petya was wondering what is the minimum number of coins he needs to spend to defeat the $i$-th dragon.

Note that the task is solved independently for each dragon (improvements are not saved).


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — number of heroes.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{12}$), where $a_i$ is the strength of the $i$-th hero.

The third line contains a single integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of dragons.

The next $m$ lines contain two integers each, $x_i$ and $y_i$ ($1 \le x_i \le 10^{12}; 1 \le y_i \le 10^{18}$) — defense and attack power of the $i$-th dragon.


-----Output-----

Print $m$ lines, $i$-th of which contains a single integer — the minimum number of coins that should be spent to defeat the $i$-th dragon.


-----Examples-----

Input
4
3 6 2 3
5
3 12
7 9
4 14
1 10
8 7
Output
1
2
4
0
2


-----Note-----

To defeat the first dragon, you can increase the strength of the third hero by $1$, then the strength of the heroes will be equal to $[3, 6, 3, 3]$. To kill the dragon, you can choose the first hero.

To defeat the second dragon, you can increase the forces of the second and third heroes by $1$, then the strength of the heroes will be equal to $[3, 7, 3, 3]$. To kill the dragon, you can choose a second hero.

To defeat the third dragon, you can increase the strength of all the heroes by $1$, then the strength of the heroes will be equal to $[4, 7, 3, 4]$. To kill the dragon, you can choose a fourth hero.

To defeat the fourth dragon, you don't need to improve the heroes and choose a third hero to kill the dragon.

To defeat the fifth dragon, you can increase the strength of the second hero by $2$, then the strength of the heroes will be equal to $[3, 8, 2, 3]$. To kill the dragon, you can choose a second hero.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A team of furry rescue rangers was sitting idle in their hollow tree when suddenly they received a signal of distress. In a few moments they were ready, and the dirigible of the rescue chipmunks hit the road.

We assume that the action takes place on a Cartesian plane. The headquarters of the rescuers is located at point (x1, y1), and the distress signal came from the point (x2, y2).

Due to Gadget's engineering talent, the rescuers' dirigible can instantly change its current velocity and direction of movement at any moment and as many times as needed. The only limitation is: the speed of the aircraft relative to the air can not exceed <image> meters per second.

Of course, Gadget is a true rescuer and wants to reach the destination as soon as possible. The matter is complicated by the fact that the wind is blowing in the air and it affects the movement of the dirigible. According to the weather forecast, the wind will be defined by the vector (vx, vy) for the nearest t seconds, and then will change to (wx, wy). These vectors give both the direction and velocity of the wind. Formally, if a dirigible is located at the point (x, y), while its own velocity relative to the air is equal to zero and the wind (ux, uy) is blowing, then after <image> seconds the new position of the dirigible will be <image>.

Gadget is busy piloting the aircraft, so she asked Chip to calculate how long will it take them to reach the destination if they fly optimally. He coped with the task easily, but Dale is convinced that Chip has given the random value, aiming only not to lose the face in front of Gadget. Dale has asked you to find the right answer.

It is guaranteed that the speed of the wind at any moment of time is strictly less than the maximum possible speed of the airship relative to the air.

Input

The first line of the input contains four integers x1, y1, x2, y2 (|x1|, |y1|, |x2|, |y2| ≤ 10 000) — the coordinates of the rescuers' headquarters and the point, where signal of the distress came from, respectively. 

The second line contains two integers <image> and t (0 < v, t ≤ 1000), which are denoting the maximum speed of the chipmunk dirigible relative to the air and the moment of time when the wind changes according to the weather forecast, respectively. 

Next follow one per line two pairs of integer (vx, vy) and (wx, wy), describing the wind for the first t seconds and the wind that will blow at all the remaining time, respectively. It is guaranteed that <image> and <image>.

Output

Print a single real value — the minimum time the rescuers need to get to point (x2, y2). You answer will be considered correct if its absolute or relative error does not exceed 10 - 6. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if <image>.

Examples

Input

0 0 5 5
3 2
-1 -1
-1 0


Output

3.729935587093555327


Input

0 0 0 1000
100 1000
-50 0
50 0


Output

11.547005383792516398

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp doesn't like integers that are divisible by $3$ or end with the digit $3$ in their decimal representation. Integers that meet both conditions are disliked by Polycarp, too.

Polycarp starts to write out the positive (greater than $0$) integers which he likes: $1, 2, 4, 5, 7, 8, 10, 11, 14, 16, \dots$. Output the $k$-th element of this sequence (the elements are numbered from $1$).


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases. Then $t$ test cases follow.

Each test case consists of one line containing one integer $k$ ($1 \le k \le 1000$).


-----Output-----

For each test case, output in a separate line one integer $x$ — the $k$-th element of the sequence that was written out by Polycarp.


-----Examples-----

Input
10
1
2
3
4
5
6
7
8
9
1000
Output
1
2
4
5
7
8
10
11
14
1666


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Harry Potter and the History of Magic

Time Limit: 1 seconds

Memory Limit: 256 megabytes

Problem Description:
The History of Magic is perhaps the most boring subject in the Hogwarts school of Witchcraft and Wizardry. Harry Potter is usually asleep during history lessons, and his magical quill writes the lectures for him. Professor Binns, the history of magic teacher, lectures in such a boring and monotonous voice, that he has a soporific effect even on the quill. That's why the quill often makes mistakes, especially in dates.

So, at the end of the semester Professor Binns decided to collect the students' parchments with notes and check them. Ron Weasley is in a panic: Harry's notes may contain errors, but at least he has some notes, whereas Ron does not have any. Ronald also has been sleeping during the lectures and his quill had been eaten by his rat Scabbers. Hermione Granger refused to give Ron her notes, because, in her opinion, everyone should learn on their own. Therefore, Ron has no choice but to copy Harry's notes.

Due to the quill's errors Harry's dates are absolutely confused: the years of goblin rebellions and other important events for the wizarding world do not follow in order, and sometimes even dates from the future occur. Now Ron wants to change some of the digits while he copies the notes so that the dates were in the chronological (i.e. non-decreasing) order and so that the notes did not have any dates strictly later than 2011, or strictly before than 1000. To make the resulting sequence as close as possible to the one dictated by Professor Binns, Ron will change no more than one digit in each date into other digit. Help him do it.

Input Specification:
The first input line contains an integer *n* (1<=≤<=*n*<=≤<=1000). It represents the number of dates in Harry's notes. Next *n* lines contain the actual dates *y*1, *y*2, ..., *y**n*, each line contains a date. Each date is a four-digit integer (1000<=≤<=*y**i*<=≤<=9999).

Output Specification:
Print *n* numbers *z*1, *z*2, ..., *z**n* (1000<=≤<=*z**i*<=≤<=2011). They are Ron's resulting dates. Print each number on a single line. Numbers *z**i* must form the non-decreasing sequence. Each number *z**i* should differ from the corresponding date *y**i* in no more than one digit. It is not allowed to change the first digit of a number into 0. If there are several possible solutions, print any of them. If there's no solution, print "No solution" (without the quotes).

Demo Input:
['3\n1875\n1936\n1721\n', '4\n9999\n2000\n3000\n3011\n', '3\n1999\n5055\n2000\n']

Demo Output:
['1835\n1836\n1921\n', '1999\n2000\n2000\n2011\n', 'No solution\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.