vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given two positive integers $n$ ($1 \le n \le 10^9$) and $k$ ($1 \le k \le 100$). Represent the number $n$ as the sum of $k$ positive integers of the same parity (have the same remainder when divided by $2$).

In other words, find $a_1, a_2, \ldots, a_k$ such that all $a_i>0$, $n = a_1 + a_2 + \ldots + a_k$ and either all $a_i$ are even or all $a_i$ are odd at the same time.

If such a representation does not exist, then report it.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases in the input. Next, $t$ test cases are given, one per line.

Each test case is two positive integers $n$ ($1 \le n \le 10^9$) and $k$ ($1 \le k \le 100$).


-----Output-----

For each test case print:

  YES and the required values $a_i$, if the answer exists (if there are several answers, print any of them);  NO if the answer does not exist. 

The letters in the words YES and NO can be printed in any case.


-----Example-----
Input
8
10 3
100 4
8 7
97 2
8 8
3 10
5 3
1000000000 9

Output
YES
4 2 4
YES
55 5 5 35
NO
NO
YES
1 1 1 1 1 1 1 1
NO
YES
3 1 1
YES
111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111120

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This problem is actually a subproblem of problem G from the same contest.

There are $n$ candies in a candy box. The type of the $i$-th candy is $a_i$ ($1 \le a_i \le n$).

You have to prepare a gift using some of these candies with the following restriction: the numbers of candies of each type presented in a gift should be all distinct (i. e. for example, a gift having two candies of type $1$ and two candies of type $2$ is bad). 

It is possible that multiple types of candies are completely absent from the gift. It is also possible that not all candies of some types will be taken to a gift.

Your task is to find out the maximum possible size of the single gift you can prepare using the candies you have.

You have to answer $q$ independent queries.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries. Each query is represented by two lines.

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

The second line of each query contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the type of the $i$-th candy in the box.

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


-----Output-----

For each query print one integer — the maximum possible size of the single gift you can compose using candies you got in this query with the restriction described in the problem statement.


-----Example-----
Input
3
8
1 4 8 4 5 6 3 8
16
2 1 3 3 4 3 4 4 1 3 2 2 2 4 1 1
9
2 2 4 4 4 7 7 7 7

Output
3
10
9



-----Note-----

In the first query, you can prepare a gift with two candies of type $8$ and one candy of type $5$, totalling to $3$ candies.

Note that this is not the only possible solution — taking two candies of type $4$ and one candy of type $6$ is also valid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array A of size N. Let us denote S as the sum of all integers present in the array. Among all integers present in the array, find the minimum integer X such that S ≤ N*X.
Example 1:
Input:
N = 3,
A = { 1, 3, 2}
Output:
2
Explanation:
Sum of integers in the array is 6.
since 6 ≤ 3*2, therefore 2 is the answer.
Example 2:
Input:
N = 1,
A = { 3 }
Output:
3
Explanation:
3 is the only possible answer
Your Task:
The task is to complete the function minimumInteger() which takes an integer N and an integer array A as input parameters and returns the minimum integer which satisfies the condition.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤  N ≤ 10^{5}
1 ≤  A_{i} ≤ 10^{9}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fourth Great and Bountiful Human Empire is developing a transconduit tunnel network connecting all it’s planets. The Empire consists of $N$ planets, represented as points in the 3D space. The cost of forming a transconduit tunnel between planets $A$ and $B$ is:\[ \operatorname {TunnelCost}(A,B) = \min \{ |x_ A - x_ B |, |y_ A -y_ B |, |z_ A -z_ B | \} \]

where $(x_ A, y_ A, z_ A)$ are the 3D coordinates of planet $A$, and $(x_ B, y_ B, z_ B)$ are coordinates of planet $B$. The Empire needs to build exactly $N - 1$ tunnels in order to fully connect all planets, either by direct links or by chain of links. You need to come up with the lowest possible cost of successfully completing this project.

-----Input-----
The first line of input contains one integer $N$ ($1 \le N \le 100000$), the number of planets.

The next $N$ lines contain exactly $3$ integers each. All integers are between $-10^9$ and $10^9$ inclusive. Each line contains the $x$, $y$, and $z$ coordinate of one planet (in order).

No two planets will occupy the exact same point in space.

-----Output-----
The first and only line of output should contain the minimal cost of forming the network of tunnels.

-----Examples-----
Sample Input 1:
2
1 5 10
7 8 2
Sample Output 1:
3

Sample Input 2:
3
-1 -1 -1
5 5 5
10 10 10
Sample Output 2:
11

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A number, ${x}$, is called irresponsible when adding ${x}$ to $x+1$ requires a carry operation. For example, $5$, $17$, and ${91}$ are irresponsible numbers because adding them to ${6}$, ${18}$, and $92$ (respectively) requires a carry operation:

In $5+(5+1)=5+6=11$, a ${1}$ is carried over into the $10$'s place. 
In $17+(17+1)=17+18=35$, a $2$ is carried over into the $10$'s place.
In $91+(91+1)=91+92=183$, a ${1}$ is carried over into the $\left(\begin{array}{c c}{{1}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ \end{array}\right).$'s place.

You have two integers, ${x}$ and $n$. Construct a new number, ${s}$, by repeating ${x}$ a total of $n$ times. For example, if $x=3121$ and $n=4$, then $s=3121312131213121$.

Given ${x}$ and $n$, construct ${s}$ and find all the irreponsible numbers between ${1}$ and ${s}$. Then print the number of irresponsible numbers in the aforementioned range; as this number can be quite large, your answer must be modulo $10^9+7$.

Input Format

A single line with two space-separated integers denoting the respective values of ${x}$ and $n$.

Constraints

$1\leq x\leq10^{1,000,000}$
$1\leq n\leq10^{18}$

Subtasks

For $15\%$ of the maximum score: 

$1\leq x\leq10^{6}$
$n=1$

For ${40\%}$ of the maximum score: 

$1\leq x\leq10^{1,000,000}$
$n=1$

Output Format

Print a single integer denoting the number of irresponsible numbers between ${1}$ and ${s}$, modulo $10^9+7$.

Sample Input
1 2

Sample Output
4

Explanation

When we repeat $x=1$ a total of $n=2$ times we get ${11}$. The irresponsible numbers between ${1}$ and ${11}$ are $5$, ${6}$, $7$, and $8$. Because there are four irresponsible numbers, we print $4\times(10^9+7)=4$ on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are two persons, numbered 0 and 1, and a variable x whose initial value is 0. The two persons now play a game. The game is played in N rounds. The following should be done in the i-th round (1 \leq i \leq N):

* Person S_i does one of the following:
* Replace x with x \oplus A_i, where \oplus represents bitwise XOR.
* Do nothing.



Person 0 aims to have x=0 at the end of the game, while Person 1 aims to have x \neq 0 at the end of the game.

Determine whether x becomes 0 at the end of the game when the two persons play optimally.

Solve T test cases for each input file.

Constraints

* 1 \leq T \leq 100
* 1 \leq N \leq 200
* 1 \leq A_i \leq 10^{18}
* S is a string of length N consisting of `0` and `1`.
* All numbers in input are integers.

Input

Input is given from Standard Input in the following format. The first line is as follows:


T


Then, T test cases follow. Each test case is given in the following format:


N
A_1 A_2 \cdots A_N
S


Output

For each test case, print a line containing `0` if x becomes 0 at the end of the game, and `1` otherwise.

Example

Input

3
2
1 2
10
2
1 1
10
6
2 3 4 5 6 7
111000


Output

1
0
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n bags with candies, initially the i-th bag contains i candies. You want all the bags to contain an equal amount of candies in the end. 

To achieve this, you will:

  * Choose m such that 1 ≤ m ≤ 1000

  * Perform m operations. In the j-th operation, you will pick one bag and add j candies to all bags apart from the chosen one.




Your goal is to find a valid sequence of operations after which all the bags will contain an equal amount of candies. 

  * It can be proved that for the given constraints such a sequence always exists.

  * You don't have to minimize m.

  * If there are several valid sequences, you can output any.

Input

Each test contains multiple test cases.

The first line contains the number of test cases t (1 ≤ t ≤ 100). Description of the test cases follows.

The first and only line of each test case contains one integer n (2 ≤ n≤ 100). 

Output

For each testcase, print two lines with your answer. 

In the first line print m (1≤ m ≤ 1000) — the number of operations you want to take. 

In the second line print m positive integers a_1, a_2, ..., a_m (1 ≤ a_i ≤ n), where a_j is the number of bag you chose on the j-th operation.

Example

Input


2
2
3


Output


1
2
5
3 3 3 1 2

Note

In the first case, adding 1 candy to all bags except of the second one leads to the arrangement with [2, 2] candies.

In the second case, firstly you use first three operations to add 1+2+3=6 candies in total to each bag except of the third one, which gives you [7, 8, 3]. Later, you add 4 candies to second and third bag, so you have [7, 12, 7], and 5 candies to first and third bag — and the result is [12, 12, 12].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're given a list of n strings a1, a2, ..., an. You'd like to concatenate them together in some order such that the resulting string would be lexicographically smallest.

Given the list of strings, output the lexicographically smallest concatenation.

Input

The first line contains integer n — the number of strings (1 ≤ n ≤ 5·104).

Each of the next n lines contains one string ai (1 ≤ |ai| ≤ 50) consisting of only lowercase English letters. The sum of string lengths will not exceed 5·104.

Output

Print the only string a — the lexicographically smallest string concatenation.

Examples

Input

4
abba
abacaba
bcd
er


Output

abacabaabbabcder


Input

5
x
xx
xxa
xxaa
xxaaa


Output

xxaaaxxaaxxaxxx


Input

3
c
cb
cba


Output

cbacbc

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vanya got bored and he painted n distinct points on the plane. After that he connected all the points pairwise and saw that as a result many triangles were formed with vertices in the painted points. He asks you to count the number of the formed triangles with the non-zero area.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 2000) — the number of the points painted on the plane. 

Next n lines contain two integers each x_{i}, y_{i} ( - 100 ≤ x_{i}, y_{i} ≤ 100) — the coordinates of the i-th point. It is guaranteed that no two given points coincide.


-----Output-----

In the first line print an integer — the number of triangles with the non-zero area among the painted points.


-----Examples-----
Input
4
0 0
1 1
2 0
2 2

Output
3

Input
3
0 0
1 1
2 0

Output
1

Input
1
1 1

Output
0



-----Note-----

Note to the first sample test. There are 3 triangles formed: (0, 0) - (1, 1) - (2, 0); (0, 0) - (2, 2) - (2, 0); (1, 1) - (2, 2) - (2, 0).

Note to the second sample test. There is 1 triangle formed: (0, 0) - (1, 1) - (2, 0).

Note to the third sample test. A single point doesn't form a single triangle.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today Chef wants to evaluate the dishes of his $N$ students. He asks each one to cook a dish and present it to him.
Chef loves his secret ingredient, and only likes dishes with at least $X$ grams of it.
Given $N$, $X$ and the amount of secret ingredient used by each student $A_i$, find out whether Chef will like at least one dish. 

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- The first line of each testcase contains two integers $N$ 
(number of students) and $X$ (minimum amount of secret ingredient that a dish must contain for Chef to like it).
- The next line contains $N$ space separated integers, $A_i$ denoting the amount of secret ingredient used by the students in their dishes.

-----Output:-----
For each testcase, print a single string "YES" if Chef likes at least one dish. Otherwise, print "NO". (Without quotes).

-----Constraints:-----
- $1 \leq T \leq 100$
- $1 \leq N \leq 1000$
- $1 \leq X \leq 1000000$
- $1 \leq A_i \leq 1000000$

-----Sample Input:-----
3
5 100
11 22 33 44 55
5 50
10 20 30 40 50
5 45
12 24 36 48 60

-----Sample Output:-----
NO
YES
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a building with n rooms, numbered 1 to n.
We can move from any room to any other room in the building.
Let us call the following event a move: a person in some room i goes to another room j~ (i \neq j).
Initially, there was one person in each room in the building.
After that, we know that there were exactly k moves happened up to now.
We are interested in the number of people in each of the n rooms now. How many combinations of numbers of people in the n rooms are possible?
Find the count modulo (10^9 + 7).

-----Constraints-----
 - All values in input are integers.
 - 3 \leq n \leq 2 \times 10^5
 - 2 \leq k \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
n k

-----Output-----
Print the number of possible combinations of numbers of people in the n rooms now, modulo (10^9 + 7).

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

-----Sample Output-----
10

Let c_1, c_2, and c_3 be the number of people in Room 1, 2, and 3 now, respectively. There are 10 possible combination of (c_1, c_2, c_3):
 - (0, 0, 3)
 - (0, 1, 2)
 - (0, 2, 1)
 - (0, 3, 0)
 - (1, 0, 2)
 - (1, 1, 1)
 - (1, 2, 0)
 - (2, 0, 1)
 - (2, 1, 0)
 - (3, 0, 0)
For example, (c_1, c_2, c_3) will be (0, 1, 2) if the person in Room 1 goes to Room 2 and then one of the persons in Room 2 goes to Room 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is 14^th of Feb, Chotu has worked really hard for the past seven days to impress his crush. Now it's time to take her on a perfect date. He has planned to take his girl to LoveLand. LoveLand is a mystical place built  only for new lovers. LoveLand is a one dimensional world of N blocks numbered from 1 to N, the i^th block has a fare Ai  that the couple has to pay for visiting the block.

Chotu being a student has limited pocket-money left for the date.  In this hard time he is asking for your help. Don't worry, you don't have to lend him money instead he will ask you certain question to verify if he has enough money for the date. Each query comprises of two integers L  and R, denoting two block numbers in the LoveLand. You have to tell Chotu what is the total cost of visiting the blocks [L, L + 1, L+2,....R] (both inclusive).

Chotu is pretty impatient for the date, so you have to be really quick in answering all his queries.
Input
 
First line contains integer N and Q denoting number of blocks and the number of queries respectively. 
Next line contains N integers denoting the fare of visiting each block.
Q lines follow each with two integers  L and R.
Ouptut

For each query print the required answer.
Constraints

1 ≤ N ≤ 10^5

0 ≤ Ai ≤ 10^4

1 ≤ Q ≤ 10^5

1 ≤ L ≤ R ≤ N

SAMPLE INPUT
7 4
1 2 3 4 5 6 7
1 1 
2 5
1 7
4 6

SAMPLE OUTPUT
1
14
28
15

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given $n$ distinct points on a plane. The coordinates of the $i$-th point are $(x_i, y_i)$.

For each point $i$, find the nearest (in terms of Manhattan distance) point with integer coordinates that is not among the given $n$ points. If there are multiple such points — you can choose any of them.

The Manhattan distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$.


-----Input-----

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

The next $n$ lines describe points. The $i$-th of them contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le 2 \cdot 10^5$) — coordinates of the $i$-th point.

It is guaranteed that all points in the input are distinct.


-----Output-----

Print $n$ lines. In the $i$-th line, print the point with integer coordinates that is not among the given $n$ points and is the nearest (in terms of Manhattan distance) to the $i$-th point from the input.

Output coordinates should be in range $[-10^6; 10^6]$. It can be shown that any optimal answer meets these constraints.

If there are several answers, you can print any of them.


-----Examples-----

Input
6
2 2
1 2
2 1
3 2
2 3
5 5
Output
1 1
1 1
2 0
3 1
2 4
5 4
Input
8
4 4
2 4
2 2
2 3
1 4
4 2
1 3
3 3
Output
4 3
2 5
2 1
2 5
1 5
4 1
1 2
3 2


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two integers `a` and `x`, return the minimum non-negative number to **add to** / **subtract from** `a` to make it a multiple of `x`.

```python
minimum(10, 6)  #= 2

10+2 = 12 which is a multiple of 6
```

## Note
- 0 is always a multiple of `x`

## Constraints

**1 <= a <= 10^(6)**

**1 <= x <= 10^(5)**

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
At one of the many climate protests, Skylar fell in love with a fellow environmental activist. Unfortunately, the two young lovers live on opposite sides of the planet and long distance travel is only practical by (gasp) air. Skylar had scolded friends and family for flying, heavily handing out the recent Swedish export flygskam (verbatim translation: flight shame). But alas, the things we do for love! Now they want your help to calculate the minimum amount of flygskam Skylar will accumulate on a one-way trip across the globe. 

To calculate the best route you models the planet as a perfect sphere and assumes that all flights fly at the distance $6381$ km from the center of the earth. The amount of shame for a single point-to-point flight is calculated as the distance between the airports in km, plus a take-off and landing penalty of $100$, that is, two airports with the flight distance $1000$ km will result in $1100$ shame.

-----Latitude and longitude-----
The positions of the airports are given as the latitude and longitude in (decimal) degrees. The latitude of a point $P$ on the earths surface is the angle between the equatorial plane and a line passing through $P$ and the center of the earth. The equator has latitude $0^\circ $, points north of the equator has positive values and points south of the equator has negative values, the North Pole has latitude $90^\circ $ and the South Pole latitude $-90 ^\circ $. Half circles that run from the North to the South pole are called meridians. The zero meridian runs through Greenwich. The longitude of a point $Q$ is the angle between the zero meridian plane and the line that run through $Q$ and the center of the earth, with values from $- 180^\circ $ to $+180^\circ $, with positive values east of Greenwich.

-----Input-----
Input starts with one line with two integers $1 \leq N \leq 10000$, the number of airports and $1 \leq M \leq 100000$, the number of two-way flight routes. The second line has two strings $S$ and $T$, Skylar’s start position and Skylar’s target position. Then follows $N$ lines, each starts with a three letter (uppercase) airport code, followed by two real values numbers, the latitude and longitude in degrees. Then follows $M$ lines, each with two strings $a$ and $b$, the airports with a two-way flight connection.

All flight airports have unique names and all connections are between existing airports.

-----Output-----
Output a real value with the minimum amount of flygskam Skylar will obtain on a one-way trip. If the target is unreachable and Skylar will be forever alone, output -1. Answers within a relative or absolute error of $10^{-6}$ will be accepted.

-----Examples-----
Sample Input 1:
4 4
ARN SCR
ARN 59.6467921 17.9370443
SCR 61.156603 12.837360
CPH 55.618023 12.650763
OSL 60.197646 11.100008
ARN OSL
ARN CPH
SCR OSL
OSL CPH
Sample Output 1:
729.09706162045

Sample Input 2:
2 1
LAX AKL
AKL -37.006131 174.783781
LAX 33.941589 -118.408531
LAX AKL
Sample Output 2:
10603.3297338597

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Math Show

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarp takes part in a math show. He is given *n* tasks, each consists of *k* subtasks, numbered 1 through *k*. It takes him *t**j* minutes to solve the *j*-th subtask of any task. Thus, time required to solve a subtask depends only on its index, but not on the task itself. Polycarp can solve subtasks in any order.

By solving subtask of arbitrary problem he earns one point. Thus, the number of points for task is equal to the number of solved subtasks in it. Moreover, if Polycarp completely solves the task (solves all *k* of its subtasks), he recieves one extra point. Thus, total number of points he recieves for the complete solution of the task is *k*<=+<=1.

Polycarp has *M* minutes of time. What is the maximum number of points he can earn?

Input Specification:
The first line contains three integer numbers *n*, *k* and *M* (1<=≤<=*n*<=≤<=45, 1<=≤<=*k*<=≤<=45, 0<=≤<=*M*<=≤<=2·109).

The second line contains *k* integer numbers, values *t**j* (1<=≤<=*t**j*<=≤<=1000000), where *t**j* is the time in minutes required to solve *j*-th subtask of any task.

Output Specification:
Print the maximum amount of points Polycarp can earn in *M* minutes.

Demo Input:
['3 4 11\n1 2 3 4\n', '5 5 10\n1 2 4 8 16\n']

Demo Output:
['6\n', '7\n']

Note:
In the first example Polycarp can complete the first task and spend 1 + 2 + 3 + 4 = 10 minutes. He also has the time to solve one subtask of the second task in one minute.

In the second example Polycarp can solve the first subtask of all five tasks and spend 5·1 = 5 minutes. Also he can solve the second subtasks of two tasks and spend 2·2 = 4 minutes. Thus, he earns 5 + 2 = 7 points in total.

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