vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Santa Claus has received letters from $n$ different kids throughout this year. Of course, each kid wants to get some presents from Santa: in particular, the $i$-th kid asked Santa to give them one of $k_i$ different items as a present. Some items could have been asked by multiple kids.

Santa is really busy, so he wants the New Year Bot to choose the presents for all children. Unfortunately, the Bot's algorithm of choosing presents is bugged. To choose a present for some kid, the Bot does the following:

  choose one kid $x$ equiprobably among all $n$ kids;  choose some item $y$ equiprobably among all $k_x$ items kid $x$ wants;  choose a kid $z$ who will receive the present equipropably among all $n$ kids (this choice is independent of choosing $x$ and $y$); the resulting triple $(x, y, z)$ is called the decision of the Bot. 

If kid $z$ listed item $y$ as an item they want to receive, then the decision valid. Otherwise, the Bot's choice is invalid.

Santa is aware of the bug, but he can't estimate if this bug is really severe. To do so, he wants to know the probability that one decision generated according to the aforementioned algorithm is valid. Can you help him?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 10^6$) — the number of kids who wrote their letters to Santa.

Then $n$ lines follow, the $i$-th of them contains a list of items wanted by the $i$-th kid in the following format: $k_i$ $a_{i, 1}$ $a_{i, 2}$ ... $a_{i, k_i}$ ($1 \le k_i, a_{i, j} \le 10^6$), where $k_i$ is the number of items wanted by the $i$-th kid, and $a_{i, j}$ are the items themselves. No item is contained in the same list more than once.

It is guaranteed that $\sum \limits_{i = 1}^{n} k_i \le 10^6$.


-----Output-----

Print the probatility that the Bot produces a valid decision as follows:

Let this probability be represented as an irreducible fraction $\frac{x}{y}$. You have to print $x \cdot y^{-1} \mod 998244353$, where $y^{-1}$ is the inverse element of $y$ modulo $998244353$ (such integer that $y \cdot y^{-1}$ has remainder $1$ modulo $998244353$). 


-----Examples-----
Input
2
2 2 1
1 1

Output
124780545

Input
5
2 1 2
2 3 1
3 2 4 3
2 1 4
3 4 3 2

Output
798595483

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers $l$ and $r$, where $l < r$. We will add $1$ to $l$ until the result is equal to $r$. Thus, there will be exactly $r-l$ additions performed. For each such addition, let's look at the number of digits that will be changed after it.

For example:

if $l=909$, then adding one will result in $910$ and $2$ digits will be changed;

if you add one to $l=9$, the result will be $10$ and $2$ digits will also be changed;

if you add one to $l=489999$, the result will be $490000$ and $5$ digits will be changed.

Changed digits always form a suffix of the result written in the decimal system.

Output the total number of changed digits, if you want to get $r$ from $l$, adding $1$ each time.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 10^4$). Then $t$ test cases follow.

Each test case is characterized by two integers $l$ and $r$ ($1 \le l < r \le 10^9$).


-----Output-----

For each test case, calculate the total number of changed digits if you want to get $r$ from $l$, adding one each time.


-----Examples-----

Input
4
1 9
9 10
10 20
1 1000000000
Output
8
2
11
1111111110


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Janusz is a businessman. He owns a company "Januszex", which produces games for teenagers. Last hit of Januszex was a cool one-person game "Make it one". The player is given a sequence of $n$ integers $a_i$.

It is allowed to select any subset of them, and the score is equal to the greatest common divisor of selected elements. The goal is to take as little elements as it is possible, getting the score $1$. Now Janusz wonders, for given sequence, how much elements should the player choose?


-----Input-----

The first line contains an only integer $n$ ($1 \le n \le 300\,000$) — the number of integers in the sequence.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 300\,000$).


-----Output-----

If there is no subset of the given sequence with gcd equal to $1$, output -1.

Otherwise, output exactly one integer — the size of the smallest subset with gcd equal to $1$.


-----Examples-----
Input
3
10 6 15

Output
3

Input
3
2 4 6

Output
-1

Input
7
30 60 21 42 70 15 30

Output
3



-----Note-----

In the first example, selecting a subset of all numbers gives a gcd of $1$ and for all smaller subsets the gcd is greater than $1$.

In the second example, for all subsets of numbers the gcd is at least $2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Mahmoud and Ehab and the message

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mahmoud wants to send a message to his friend Ehab. Their language consists of *n* words numbered from 1 to *n*. Some words have the same meaning so there are *k* groups of words such that all the words in some group have the same meaning.

Mahmoud knows that the *i*-th word can be sent with cost *a**i*. For each word in his message, Mahmoud can either replace it with another word of the same meaning or leave it as it is. Can you help Mahmoud determine the minimum cost of sending the message?

The cost of sending the message is the sum of the costs of sending every word in it.

Input Specification:
The first line of input contains integers *n*, *k* and *m* (1<=≤<=*k*<=≤<=*n*<=≤<=105,<=1<=≤<=*m*<=≤<=105) — the number of words in their language, the number of groups of words, and the number of words in Mahmoud's message respectively.

The second line contains *n* strings consisting of lowercase English letters of length not exceeding 20 which represent the words. It's guaranteed that the words are distinct.

The third line contains *n* integers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=109) where *a**i* is the cost of sending the *i*-th word.

The next *k* lines describe the groups of words of same meaning. The next *k* lines each start with an integer *x* (1<=≤<=*x*<=≤<=*n*) which means that there are *x* words in this group, followed by *x* integers which represent the indices of words in this group. It's guaranteed that each word appears in exactly one group.

The next line contains *m* space-separated words which represent Mahmoud's message. Each of these words appears in the list of language's words.

Output Specification:
The only line should contain the minimum cost to send the message after replacing some words (maybe none) with some words of the same meaning.

Demo Input:
['5 4 4\ni loser am the second\n100 1 1 5 10\n1 1\n1 3\n2 2 5\n1 4\ni am the second\n', '5 4 4\ni loser am the second\n100 20 1 5 10\n1 1\n1 3\n2 2 5\n1 4\ni am the second\n']

Demo Output:
['107', '116']

Note:
In the first sample, Mahmoud should replace the word "second" with the word "loser" because it has less cost so the cost will be 100+1+5+1=107.

In the second sample, Mahmoud shouldn't do any replacement so the cost will be 100+1+5+10=116.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call a permutation $p$ of length $n$ anti-Fibonacci if the condition $p_{i-2} + p_{i-1} \ne p_i$ holds for all $i$ ($3 \le i \le n$). Recall that the permutation is the array of length $n$ which contains each integer from $1$ to $n$ exactly once.

Your task is for a given number $n$ print $n$ distinct anti-Fibonacci permutations of length $n$.


-----Input-----

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

The single line of each test case contains a single integer $n$ ($3 \le n \le 50$).


-----Output-----

For each test case, print $n$ lines. Each line should contain an anti-Fibonacci permutation of length $n$. In each test case, you cannot print any permutation more than once.

If there are multiple answers, print any of them. It can be shown that it is always possible to find $n$ different anti-Fibonacci permutations of size $n$ under the constraints of the problem.


-----Examples-----

Input
2
4
3
Output
4 1 3 2
1 2 4 3
3 4 1 2
2 4 1 3
3 2 1
1 3 2
3 1 2


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Currently, XXOC's rap is a string consisting of zeroes, ones, and question marks. Unfortunately, haters gonna hate. They will write $x$ angry comments for every occurrence of subsequence 01 and $y$ angry comments for every occurrence of subsequence 10. You should replace all the question marks with 0 or 1 in such a way that the number of angry comments would be as small as possible.

String $b$ is a subsequence of string $a$, if it can be obtained by removing some characters from $a$. Two occurrences of a subsequence are considered distinct if sets of positions of remaining characters are distinct.


-----Input-----

The first line contains string $s$ — XXOC's rap ($1 \le |s| \leq 10^5$). The second line contains two integers $x$ and $y$ — the number of angry comments XXOC will recieve for every occurrence of 01 and 10 accordingly ($0 \leq x, y \leq 10^6$).


-----Output-----

Output a single integer — the minimum number of angry comments.


-----Examples-----

Input
0?1
2 3
Output
4
Input
?????
13 37
Output
0
Input
?10?
239 7
Output
28
Input
01101001
5 7
Output
96


-----Note-----

In the first example one of the optimum ways to replace is 001. Then there will be $2$ subsequences 01 and $0$ subsequences 10. Total number of angry comments will be equal to $2 \cdot 2 + 0 \cdot 3 = 4$.

In the second example one of the optimum ways to replace is 11111. Then there will be $0$ subsequences 01 and $0$ subsequences 10. Total number of angry comments will be equal to $0 \cdot 13 + 0 \cdot 37 = 0$.

In the third example one of the optimum ways to replace is 1100. Then there will be $0$ subsequences 01 and $4$ subsequences 10. Total number of angry comments will be equal to $0 \cdot 239 + 4 \cdot 7 = 28$.

In the fourth example one of the optimum ways to replace is 01101001. Then there will be $8$ subsequences 01 and $8$ subsequences 10. Total number of angry comments will be equal to $8 \cdot 5 + 8 \cdot 7 = 96$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Guard Duty (easy)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The Rebel fleet is afraid that the Empire might want to strike back again. Princess Heidi needs to know if it is possible to assign *R* Rebel spaceships to guard *B* bases so that every base has exactly one guardian and each spaceship has exactly one assigned base (in other words, the assignment is a perfect matching). Since she knows how reckless her pilots are, she wants to be sure that any two (straight) paths – from a base to its assigned spaceship – do not intersect in the galaxy plane (that is, in 2D), and so there is no risk of collision.

Input Specification:
The first line contains two space-separated integers *R*,<=*B*(1<=≤<=*R*,<=*B*<=≤<=10). For 1<=≤<=*i*<=≤<=*R*, the *i*<=+<=1-th line contains two space-separated integers *x**i* and *y**i* (|*x**i*|,<=|*y**i*|<=≤<=10000) denoting the coordinates of the *i*-th Rebel spaceship. The following *B* lines have the same format, denoting the position of bases. It is guaranteed that no two points coincide and that no three points are on the same line.

Output Specification:
If it is possible to connect Rebel spaceships and bases so as satisfy the constraint, output Yes, otherwise output No (without quote).

Demo Input:
['3 3\n0 0\n2 0\n3 1\n-2 1\n0 3\n2 2\n', '2 1\n1 0\n2 2\n3 1\n']

Demo Output:
['Yes\n', 'No\n']

Note:
For the first example, one possible way is to connect the Rebels and bases in order.

For the second example, there is no perfect matching between Rebels and bases.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ehab is interested in the bitwise-xor operation and the special graphs. Mahmoud gave him a problem that combines both. He has a complete graph consisting of n vertices numbered from 0 to n - 1. For all 0 ≤ u < v < n, vertex u and vertex v are connected with an undirected edge that has weight $u \oplus v$ (where $\oplus$ is the bitwise-xor operation). Can you find the weight of the minimum spanning tree of that graph?

You can read about complete graphs in https://en.wikipedia.org/wiki/Complete_graph

You can read about the minimum spanning tree in https://en.wikipedia.org/wiki/Minimum_spanning_tree

The weight of the minimum spanning tree is the sum of the weights on the edges included in it.


-----Input-----

The only line contains an integer n (2 ≤ n ≤ 10^12), the number of vertices in the graph.


-----Output-----

The only line contains an integer x, the weight of the graph's minimum spanning tree.


-----Example-----
Input
4

Output
4


-----Note-----

In the first sample: [Image] The weight of the minimum spanning tree is 1+2+1=4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are fishing with polar bears Alice and Bob. While waiting for the fish to bite, the polar bears get bored. They come up with a game. First Alice and Bob each writes a 01-string (strings that only contain character "0" and "1") a and b. Then you try to turn a into b using two types of operations:  Write parity(a) to the end of a. For example, $1010 \rightarrow 10100$.  Remove the first character of a. For example, $1001 \rightarrow 001$. You cannot perform this operation if a is empty. 

You can use as many operations as you want. The problem is, is it possible to turn a into b?

The parity of a 01-string is 1 if there is an odd number of "1"s in the string, and 0 otherwise.


-----Input-----

The first line contains the string a and the second line contains the string b (1 ≤ |a|, |b| ≤ 1000). Both strings contain only the characters "0" and "1". Here |x| denotes the length of the string x.


-----Output-----

Print "YES" (without quotes) if it is possible to turn a into b, and "NO" (without quotes) otherwise.


-----Examples-----
Input
01011
0110

Output
YES

Input
0011
1110

Output
NO



-----Note-----

In the first sample, the steps are as follows: 01011 → 1011 → 011 → 0110

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array a of 2n distinct integers. You want to arrange the elements of the array in a circle such that no element is equal to the the arithmetic mean of its 2 neighbours.

More formally, find an array b, such that: 

  * b is a permutation of a.

  * For every i from 1 to 2n, b_i ≠ \frac{b_{i-1}+b_{i+1}}{2}, where b_0 = b_{2n} and b_{2n+1} = b_1.




It can be proved that under the constraints of this problem, such array b always exists.

Input

The first line of input contains a single integer t (1 ≤ t ≤ 1000) — the number of testcases. The description of testcases follows.

The first line of each testcase contains a single integer n (1 ≤ n ≤ 25).

The second line of each testcase contains 2n integers a_1, a_2, …, a_{2n} (1 ≤ a_i ≤ 10^9) — elements of the array.

Note that there is no limit to the sum of n over all testcases.

Output

For each testcase, you should output 2n integers, b_1, b_2, … b_{2n}, for which the conditions from the statement are satisfied.

Example

Input


3
3
1 2 3 4 5 6
2
123 456 789 10
1
6 9


Output


3 1 4 2 5 6
123 10 456 789
9 6

Note

In the first testcase, array [3, 1, 4, 2, 5, 6] works, as it's a permutation of [1, 2, 3, 4, 5, 6], and (3+4)/(2)≠ 1, (1+2)/(2)≠ 4, (4+5)/(2)≠ 2, (2+6)/(2)≠ 5, (5+3)/(2)≠ 6, (6+1)/(2)≠ 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Young Mirko has been buying voodoo dolls lately. Considering that he is very interested in the cheapest purchase possible, he has been tracking the prices of voodoo dolls each day. His price list consists of doll prices in the last $N$ days, where doll price $a_ i$ represents the price of a doll $i$ days ago.

Mirko thinks he has noticed a connection between the average doll price in a sequence of consecutive days and the price on the following day. He wants to test his hunch and is puzzled by a very interesting question: “For a given $P$, how many different consecutive subsequences in the last $N$ days are there, when the average doll price was greater than or equal to $P$?”

Two consecutive subsequences are considered different if their beginnings or ends are different.

-----Input-----
The first line of input contains the integer $N$, the sequence length ($1 \leq N \leq 1000000$). The second line of input contains $N$ prices $a_ i$ ($0 \leq a_ i \leq 1000000000$). The third line of input contains an integer $P$. ($0 \leq P \leq 1000000000$).

-----Output-----
The first and only line of output must contain the answer to Mirko’s question for a given $P$.

-----Examples-----
Sample Input 1:
3
1 2 3
3
Sample Output 1:
1

Sample Input 2:
3
1 3 2
2
Sample Output 2:
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a binary representation in the form of string(S) of a number n, the task is to find a binary representation of n-1.
Note: n is greater than zero. 
Example 1:
Input: S = "11"
Output: 10
Explanation: "11" is the binary 
representation of 3 and binary 
representation of 2 is "10"
Example 1:
Input: S = "1000"
Output: 111
Explanation: "1000" is the binary 
representation of 8 and binary 
representation of 7 is "111"
Your Task:  
You don't need to read input or print anything. Complete the function binaryPreviousNumber() which takes S as input parameter and returns the string.
Expected Time Complexity:O(N)
Expected Auxiliary Space: O(N) to store resultant string  
Constraints:
1 <= N <= 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gena loves sequences of numbers. Recently, he has discovered a new type of sequences which he called an almost arithmetical progression. A sequence is an almost arithmetical progression, if its elements can be represented as:  a_1 = p, where p is some integer;  a_{i} = a_{i} - 1 + ( - 1)^{i} + 1·q (i > 1), where q is some integer. 

Right now Gena has a piece of paper with sequence b, consisting of n integers. Help Gena, find there the longest subsequence of integers that is an almost arithmetical progression.

Sequence s_1,  s_2,  ...,  s_{k} is a subsequence of sequence b_1,  b_2,  ...,  b_{n}, if there is such increasing sequence of indexes i_1, i_2, ..., i_{k} (1  ≤  i_1  <  i_2  < ...   <  i_{k}  ≤  n), that b_{i}_{j}  =  s_{j}. In other words, sequence s can be obtained from b by crossing out some elements.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 4000). The next line contains n integers b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 10^6).


-----Output-----

Print a single integer — the length of the required longest subsequence.


-----Examples-----
Input
2
3 5

Output
2

Input
4
10 20 10 30

Output
3



-----Note-----

In the first test the sequence actually is the suitable subsequence. 

In the second test the following subsequence fits: 10, 20, 10.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nick had received an awesome array of integers $a=[a_1, a_2, \dots, a_n]$ as a gift for his $5$ birthday from his mother. He was already going to explore its various properties but after unpacking he was disappointed a lot because the product $a_1 \cdot a_2 \cdot \dots a_n$ of its elements seemed to him not large enough.

He was ready to throw out the array, but his mother reassured him. She told him, that array would not be spoiled after the following operation: choose any index $i$ ($1 \le i \le n$) and do $a_i := -a_i - 1$.

For example, he can change array $[3, -1, -4, 1]$ to an array $[-4, -1, 3, 1]$ after applying this operation to elements with indices $i=1$ and $i=3$. 

Kolya had immediately understood that sometimes it's possible to increase the product of integers of the array a lot. Now he has decided that he wants to get an array with the maximal possible product of integers using only this operation with its elements (possibly zero, one or more times, as many as he wants), it is not forbidden to do this operation several times for the same index. 

Help Kolya and print the array with the maximal possible product of elements $a_1 \cdot a_2 \cdot \dots a_n$ which can be received using only this operation in some order.

If there are multiple answers, print any of them.


-----Input-----

The first line contains integer $n$ ($1 \leq n \leq 10^{5}$) — number of integers in the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^{6} \leq a_i \leq 10^{6}$) — elements of the array


-----Output-----

Print $n$ numbers — elements of the array with the maximal possible product of elements which can be received using only this operation in some order from the given array.

If there are multiple answers, print any of them.


-----Examples-----
Input
4
2 2 2 2

Output
-3 -3 -3 -3 
Input
1
0

Output
0 
Input
3
-3 -3 2

Output
-3 -3 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hector the hacker has stolen some information, but it is encrypted. In order to decrypt it, he needs to write a function that will generate a decryption key from the encryption key which he stole (it is in hexadecimal). To do this, he has to determine the two prime factors `P` and `Q` of the encyption key, and return the product `(P-1) * (Q-1)`.

**Note:** the primes used are < 10^(5)

## Examples

For example if the encryption key is `"47b"`, it is 1147 in decimal. This factors to 31\*37, so the key Hector needs is 1080 (= 30\*36).


More examples:
* input: `"2533"`, result: 9328 (primes: 89, 107)
* input: `"1ba9"`, result: 6912 (primes: 73, 97)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:


       All numbers (including target) will be positive integers.
       The solution set must not contain duplicate combinations.


Example 1:


Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]


Example 2:


Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

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