vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Learning Languages

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The "BerCorp" company has got *n* employees. These employees can use *m* approved official languages for the formal correspondence. The languages are numbered with integers from 1 to *m*. For each employee we have the list of languages, which he knows. This list could be empty, i. e. an employee may know no official languages. But the employees are willing to learn any number of official languages, as long as the company pays their lessons. A study course in one language for one employee costs 1 berdollar.

Find the minimum sum of money the company needs to spend so as any employee could correspond to any other one (their correspondence can be indirect, i. e. other employees can help out translating).

Input Specification:
The first line contains two integers *n* and *m* (2<=≤<=*n*,<=*m*<=≤<=100) — the number of employees and the number of languages.

Then *n* lines follow — each employee's language list. At the beginning of the *i*-th line is integer *k**i* (0<=≤<=*k**i*<=≤<=*m*) — the number of languages the *i*-th employee knows. Next, the *i*-th line contains *k**i* integers — *a**ij* (1<=≤<=*a**ij*<=≤<=*m*) — the identifiers of languages the *i*-th employee knows. It is guaranteed that all the identifiers in one list are distinct. Note that an employee may know zero languages.

The numbers in the lines are separated by single spaces.

Output Specification:
Print a single integer — the minimum amount of money to pay so that in the end every employee could write a letter to every other one (other employees can help out translating).

Demo Input:
['5 5\n1 2\n2 2 3\n2 3 4\n2 4 5\n1 5\n', '8 7\n0\n3 1 2 3\n1 1\n2 5 4\n2 6 7\n1 3\n2 7 4\n1 1\n', '2 2\n1 2\n0\n']

Demo Output:
['0\n', '2\n', '1\n']

Note:
In the second sample the employee 1 can learn language 2, and employee 8 can learn language 4.

In the third sample employee 2 must learn language 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob are playing chess on a huge chessboard with dimensions $n \times n$. Alice has a single piece left — a queen, located at $(a_x, a_y)$, while Bob has only the king standing at $(b_x, b_y)$. Alice thinks that as her queen is dominating the chessboard, victory is hers. 

But Bob has made a devious plan to seize the victory for himself — he needs to march his king to $(c_x, c_y)$ in order to claim the victory for himself. As Alice is distracted by her sense of superiority, she no longer moves any pieces around, and it is only Bob who makes any turns.

Bob will win if he can move his king from $(b_x, b_y)$ to $(c_x, c_y)$ without ever getting in check. Remember that a king can move to any of the $8$ adjacent squares. A king is in check if it is on the same rank (i.e. row), file (i.e. column), or diagonal as the enemy queen. 

Find whether Bob can win or not.


-----Input-----

The first line contains a single integer $n$ ($3 \leq n \leq 1000$) — the dimensions of the chessboard.

The second line contains two integers $a_x$ and $a_y$ ($1 \leq a_x, a_y \leq n$) — the coordinates of Alice's queen.

The third line contains two integers $b_x$ and $b_y$ ($1 \leq b_x, b_y \leq n$) — the coordinates of Bob's king.

The fourth line contains two integers $c_x$ and $c_y$ ($1 \leq c_x, c_y \leq n$) — the coordinates of the location that Bob wants to get to.

It is guaranteed that Bob's king is currently not in check and the target location is not in check either.

Furthermore, the king is not located on the same square as the queen (i.e. $a_x \neq b_x$ or $a_y \neq b_y$), and the target does coincide neither with the queen's position (i.e. $c_x \neq a_x$ or $c_y \neq a_y$) nor with the king's position (i.e. $c_x \neq b_x$ or $c_y \neq b_y$).


-----Output-----

Print "YES" (without quotes) if Bob can get from $(b_x, b_y)$ to $(c_x, c_y)$ without ever getting in check, otherwise print "NO".

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


-----Examples-----
Input
8
4 4
1 3
3 1

Output
YES

Input
8
4 4
2 3
1 6

Output
NO

Input
8
3 5
1 2
6 1

Output
NO



-----Note-----

In the diagrams below, the squares controlled by the black queen are marked red, and the target square is marked blue.

In the first case, the king can move, for instance, via the squares $(2, 3)$ and $(3, 2)$. Note that the direct route through $(2, 2)$ goes through check.

 [Image] 

In the second case, the queen watches the fourth rank, and the king has no means of crossing it.

 [Image] 

In the third case, the queen watches the third file.

 [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chloe, the same as Vladik, is a competitive programmer. She didn't have any problems to get to the olympiad like Vladik, but she was confused by the task proposed on the olympiad.

Let's consider the following algorithm of generating a sequence of integers. Initially we have a sequence consisting of a single element equal to 1. Then we perform (n - 1) steps. On each step we take the sequence we've got on the previous step, append it to the end of itself and insert in the middle the minimum positive integer we haven't used before. For example, we get the sequence [1, 2, 1] after the first step, the sequence [1, 2, 1, 3, 1, 2, 1] after the second step.

The task is to find the value of the element with index k (the elements are numbered from 1) in the obtained sequence, i. e. after (n - 1) steps.

Please help Chloe to solve the problem!


-----Input-----

The only line contains two integers n and k (1 ≤ n ≤ 50, 1 ≤ k ≤ 2^{n} - 1).


-----Output-----

Print single integer — the integer at the k-th position in the obtained sequence.


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

Output
2
Input
4 8

Output
4


-----Note-----

In the first sample the obtained sequence is [1, 2, 1, 3, 1, 2, 1]. The number on the second position is 2.

In the second sample the obtained sequence is [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]. The number on the eighth position is 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $A$, consisting of $n$ positive integers $a_1, a_2, \dots, a_n$, and an array $B$, consisting of $m$ positive integers $b_1, b_2, \dots, b_m$. 

Choose some element $a$ of $A$ and some element $b$ of $B$ such that $a+b$ doesn't belong to $A$ and doesn't belong to $B$. 

For example, if $A = [2, 1, 7]$ and $B = [1, 3, 4]$, we can choose $1$ from $A$ and $4$ from $B$, as number $5 = 1 + 4$ doesn't belong to $A$ and doesn't belong to $B$. However, we can't choose $2$ from $A$ and $1$ from $B$, as $3 = 2 + 1$ belongs to $B$.

It can be shown that such a pair exists. If there are multiple answers, print any.

Choose and print any such two numbers.


-----Input-----

The first line contains one integer $n$ ($1\le n \le 100$) — the number of elements of $A$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 200$) — the elements of $A$.

The third line contains one integer $m$ ($1\le m \le 100$) — the number of elements of $B$.

The fourth line contains $m$ different integers $b_1, b_2, \dots, b_m$ ($1 \le b_i \le 200$) — the elements of $B$.

It can be shown that the answer always exists.


-----Output-----

Output two numbers $a$ and $b$ such that $a$ belongs to $A$, $b$ belongs to $B$, but $a+b$ doesn't belong to nor $A$ neither $B$.

If there are multiple answers, print any.


-----Examples-----
Input
1
20
2
10 20

Output
20 20
Input
3
3 2 2
5
1 5 7 7 9

Output
3 1

Input
4
1 3 5 7
4
7 5 3 1

Output
1 1



-----Note-----

In the first example, we can choose $20$ from array $[20]$ and $20$ from array $[10, 20]$. Number $40 = 20 + 20$ doesn't belong to any of those arrays. However, it is possible to choose $10$ from the second array too.

In the second example, we can choose $3$ from array $[3, 2, 2]$ and $1$ from array $[1, 5, 7, 7, 9]$. Number $4 = 3 + 1$ doesn't belong to any of those arrays.

In the third example, we can choose $1$ from array $[1, 3, 5, 7]$ and $1$ from array $[7, 5, 3, 1]$. Number $2 = 1 + 1$ doesn't belong to any of those arrays.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A PIN code is a string that consists of exactly $4$ digits. Examples of possible PIN codes: 7013, 0000 and 0990. Please note that the PIN code can begin with any digit, even with 0.

Polycarp has $n$ ($2 \le n \le 10$) bank cards, the PIN code of the $i$-th card is $p_i$.

Polycarp has recently read a recommendation that it is better to set different PIN codes on different cards. Thus he wants to change the minimal number of digits in the PIN codes of his cards so that all $n$ codes would become different.

Formally, in one step, Polycarp picks $i$-th card ($1 \le i \le n$), then in its PIN code $p_i$ selects one position (from $1$ to $4$), and changes the digit in this position to any other. He needs to change the minimum number of digits so that all PIN codes become different.

Polycarp quickly solved this problem. Can you solve it?


-----Input-----

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

The first line of each of $t$ test sets contains a single integer $n$ ($2 \le n \le 10$) — the number of Polycarp's bank cards. The next $n$ lines contain the PIN codes $p_1, p_2, \dots, p_n$ — one per line. The length of each of them is $4$. All PIN codes consist of digits only.


-----Output-----

Print the answers to $t$ test sets. The answer to each set should consist of a $n + 1$ lines

In the first line print $k$ — the least number of changes to make all PIN codes different. In the next $n$ lines output the changed PIN codes in the order corresponding to their appearance in the input. If there are several optimal answers, print any of them.


-----Example-----
Input
3
2
1234
0600
2
1337
1337
4
3139
3139
3139
3139

Output
0
1234
0600
1
1337
1237
3
3139
3138
3939
6139

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Return 0 if the array contains less than 2 elements.

Example 1:


Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.

Example 2:


Input: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Note:


       You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
       Try to solve it in linear time/space.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have three piles of candies: red, green and blue candies:  the first pile contains only red candies and there are $r$ candies in it,  the second pile contains only green candies and there are $g$ candies in it,  the third pile contains only blue candies and there are $b$ candies in it. 

Each day Tanya eats exactly two candies of different colors. She is free to choose the colors of eaten candies: the only restriction that she can't eat two candies of the same color in a day.

Find the maximal number of days Tanya can eat candies? Each day she needs to eat exactly two candies.


-----Input-----

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

Each test case is given as a separate line of the input. It contains three integers $r$, $g$ and $b$ ($1 \le r, g, b \le 10^8$) — the number of red, green and blue candies, respectively.


-----Output-----

Print $t$ integers: the $i$-th printed integer is the answer on the $i$-th test case in the input.


-----Example-----
Input
6
1 1 1
1 2 1
4 1 1
7 4 10
8 1 4
8 2 8

Output
1
2
2
10
5
9



-----Note-----

In the first example, Tanya can eat candies for one day only. She can eat any pair of candies this day because all of them have different colors.

In the second example, Tanya can eat candies for two days. For example, she can eat red and green candies on the first day, and green and blue candies on the second day.

In the third example, Tanya can eat candies for two days. For example, she can eat red and green candies on the first day, and red and blue candies on the second day. Note, that two red candies will remain uneaten.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
When you look at photographs of watches and clocks, you'll find that they almost always show the time 10:10. There are lots of theories and even urban legends about this. For example, when showing 10:10, the hands look like a smile, and so you are more inclined to buy the watch or clock :D (a form of subliminal advertising).

Now, you are given $N$ and ${M}$. You are to find the number of sequences $A_{1},A_{2},\ldots,A_{N}$ such that:

${A_1}$ is a number of the form ${1010}^K$ for some $1\leq K\leq M$,
If $P=A_2\cdot A_3\cdots A_N$, then ${A_1}$ is divisible by ${P}$, and $\mbox{P}$ is divisible by ${1010}$, and
$A_2,A_3,\ldots,A_N$ are squarefree.

Since the number can be very large, only give the number modulo ${2000003}$.

Input Format 

The first line of input contains a single integer ${T}$, which is the number of test cases. The following lines contain the test cases.

Each test case consists of one line containing two integers, $N$ and ${M}$.

Constraints 

$1\leq T\leq10^5$ 

$2\leq N\leq M\leq10^{12}$  

Output Format 

For each test case, output a single line containing the answer.

Sample Input  

2
2 3
3 3

Sample Output  

3
62

Explanation 

For the first test case, the possible sequences are: 

$\{1010,1010\}$, 

$\{1020100,1010\}$, 

${103031000},{1010}$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A spoonerism is a spoken phrase in which the first letters of two of the words are swapped around, often with amusing results.

In its most basic form a spoonerism is a two word phrase in which only the first letters of each word are swapped:

```"not picking" --> "pot nicking"```

Your task is to create a function that takes a string of two words, separated by a space: ```words``` and returns a spoonerism of those words in a string, as in the above example.

NOTE: All input strings will contain only two words.  Spoonerisms can be more complex.  For example, three-word phrases in which the first letters of the first and last words are swapped: ```"pack of lies" --> "lack of pies"``` or more than one letter from a word is swapped: ```"flat battery --> "bat flattery"```
You are NOT expected to account for these, or any other nuances involved in spoonerisms.

Once you have completed this kata, a slightly more challenging take on the idea can be found here: http://www.codewars.com/kata/56dbed3a13c2f61ae3000bcd

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You generate real numbers s1, s2, ..., sn as follows: 

  * s0 = 0; 
  * si = si - 1 + ti, where ti is a real number chosen independently uniformly at random between 0 and 1, inclusive. 



You are given real numbers x1, x2, ..., xn. You are interested in the probability that si ≤ xi is true for all i simultaneously.

It can be shown that this can be represented as <image>, where P and Q are coprime integers, and <image>. Print the value of P·Q - 1 modulo 998244353.

Input

The first line contains integer n (1 ≤ n ≤ 30).

The next n lines contain real numbers x1, x2, ..., xn, given with at most six digits after the decimal point (0 < xi ≤ n).

Output

Print a single integer, the answer to the problem.

Examples

Input

4
1.00
2
3.000000
4.0


Output

1


Input

1
0.50216


Output

342677322


Input

2
0.5
1.0


Output

623902721


Input

6
0.77
1.234567
2.1
1.890
2.9999
3.77


Output

859831967

Note

In the first example, the sought probability is 1 since the sum of i real numbers which don't exceed 1 doesn't exceed i.

In the second example, the probability is x1 itself.

In the third example, the sought probability is 3 / 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have been blessed as a child of Omkar. To express your gratitude, please solve this problem for Omkar!

An array a of length n is called complete if all elements are positive and don't exceed 1000, and for all indices x,y,z (1 ≤ x,y,z ≤ n), a_{x}+a_{y} ≠ a_{z} (not necessarily distinct).

You are given one integer n. Please find any complete array of length n. It is guaranteed that under given constraints such array exists.

Input

Each test contains multiple test cases. The first line contains t (1 ≤ t ≤ 1000) — the number of test cases. Description of the test cases follows.

The only line of each test case contains one integer n (1 ≤ n ≤ 1000).

It is guaranteed that the sum of n over all test cases does not exceed 1000.

Output

For each test case, print a complete array on a single line. All elements have to be integers between 1 and 1000 and for all indices x,y,z (1 ≤ x,y,z ≤ n) (not necessarily distinct), a_{x}+a_{y} ≠ a_{z} must hold.

If multiple solutions exist, you may print any.

Example

Input


2
5
4


Output


1 5 3 77 12
384 384 44 44

Note

It can be shown that the outputs above are valid for each test case. For example, 44+44 ≠ 384.

Below are some examples of arrays that are NOT complete for the 1st test case:

[1,2,3,4,5] 

Notice that a_{1}+a_{2} = a_{3}.

[1,3000,1,300,1] 

Notice that a_{2} = 3000 > 1000.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In order to win over and get noticed by his favorite streamer Daenerys, Jon decides to donate a significant amount of money . Every donation made to Daenerys is of $at$ $least$ $1$ $beastcoin$ and is displayed on Daenerys's stream alongside any message written and is visible to every viewer.
After spotting that Daenerys had set out a target for the streaming day at minimum $X$   beastcoins, all her viewers would only donate amounts less than $X$ beastcoins. Jon decided to better all of them by straight out donating more than or equal to $X$ beastcoins. Further, he decides to write a message along with his special donation to leave her in awe. His message would be : "Crossing my donation with any other donation will only increase the value of my donation". By Crossing, he means to take the $XOR$ . 
But even for all his intellectual brilliance, money doesn't grow on trees for Jon. After all he is an underpaid employee in his fancy big name MNC. Unlike Daenerys's daily cash cow who makes videos of how she donated carelessly to other people, Jon has a budget and in this case too, he is looking for the minimum donation he needs to make.
Can you tell Jon the minimum amount he needs to donate to Daenerys so that he is able to credibly put out the above comment alongside the donation in order to HOPEFULLY win her over.

-----Input Format-----
- First line contain an interger $T$, which denotes number of testcases. Next $T$ lines contain single interger $X$.    

-----Output Format-----
- For every testcase print one integer, i.e. minimum donation Jon needs to make.

-----Constriants-----
- $ 1 \leq T \leq 100000 $ 
- $ 2 \leq X \leq 10^{18} $ 

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

3

7 

-----Sample Output-----
4

8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A tourist is visiting Byteland. The tourist knows English very well. The language of Byteland is rather different from English. To be exact it differs in following points:

- Bytelandian alphabet has the same letters as English one, but possibly different in meaning. Like 'A' in Bytelandian may be 'M' in English. However this does not mean that 'M' in Bytelandian must be 'A' in English. More formally, Bytelindian alphabet is a permutation of English alphabet. It will be given to you and could be any possible permutation. Don't assume any other condition.
- People of Byteland don't like to use invisible character for separating words. Hence instead of space (' ') they use underscore ('_'). Other punctuation symbols, like '?', '!' remain the same as in English.

The tourist is carrying "The dummies guide to Bytelandian", for translation. The book is serving his purpose nicely. But he is addicted to sharing on BaceFook, and shares his numerous conversations in Byteland on it. The conversations are rather long, and it is quite tedious to translate for his English friends, so he asks you to help him by writing a program to do the same.

-----Input-----
The first line of the input contains an integer T, denoting the length of the conversation, and the string M, denoting the English translation of Bytelandian string "abcdefghijklmnopqrstuvwxyz". T and M are separated by exactly one space. Then T lines follow, each containing a Bytelandian sentence S which you should translate into English. See constraints for details.

-----Output-----
For each of the sentence in the input, output its English translation on a separate line. Replace each underscores ('_') with a space (' ') in the output. Each punctuation symbol (see below) should remain the same. Note that the uppercase letters in Bytelandian remain uppercase in English, and lowercase letters remain lowercase. See the example and its explanation for clarity.

-----Constraints-----

- 1 ≤ T ≤ 100
- M is a permutation of "abcdefghijklmnopqrstuvwxyz"
- Each sentence is non-empty and contains at most 100 characters
- Each sentence may contain only lowercase letters ('a'-'z'), uppercase letters ('A'-'Z'), underscores ('_') and punctuation symbols: dot ('.'), comma (','), exclamation ('!'), question-mark('?')

-----Example-----
Input:
5 qwertyuiopasdfghjklzxcvbnm
Ph
Pcssi
Bpke_kdc_epclc_jcijsc_mihyo?
Epcf_kdc_liswhyo_EIED_hy_Vimcvpcn_Zkdvp_siyo_viyecle.
Ipp!

Output:
Hi
Hello
What are these people doing?
They are solving TOTR in Codechef March long contest.
Ohh!

-----Explanation-----
The string "qwertyuiopasdfghjklzxcvbnm" means that 'a' in Bytelandian is 'q' in English, 'b' in Bytelandian is 'w' in English, 'c' in Bytelandian is 'e' in English and so on.
Thus to translate "Ph" (first sentence in example) to English:
1) We find that 'p' in Bytelandian means 'h' in English. So we replace 'P' with 'H'.
2) Then we see that 'h' in Bytelandian means 'i' in English. So we replace 'h' with 'i'.
3) Therefore, the translation is "Hi".

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