vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Girl Lena likes it when everything is in order, and looks for order everywhere. Once she was getting ready for the University and noticed that the room was in a mess — all the objects from her handbag were thrown about the room. Of course, she wanted to put them back into her handbag. The problem is that the girl cannot carry more than two objects at a time, and cannot move the handbag. Also, if he has taken an object, she cannot put it anywhere except her handbag — her inherent sense of order does not let her do so.

You are given the coordinates of the handbag and the coordinates of the objects in some Сartesian coordinate system. It is known that the girl covers the distance between any two objects in the time equal to the squared length of the segment between the points of the objects. It is also known that initially the coordinates of the girl and the handbag are the same. You are asked to find such an order of actions, that the girl can put all the objects back into her handbag in a minimum time period.

Input

The first line of the input file contains the handbag's coordinates xs, ys. The second line contains number n (1 ≤ n ≤ 24) — the amount of objects the girl has. The following n lines contain the objects' coordinates. All the coordinates do not exceed 100 in absolute value. All the given positions are different. All the numbers are integer.

Output

In the first line output the only number — the minimum time the girl needs to put the objects into her handbag. 

In the second line output the possible optimum way for Lena. Each object in the input is described by its index number (from 1 to n), the handbag's point is described by number 0. The path should start and end in the handbag's point. If there are several optimal paths, print any of them. 

Examples

Input

0 0
2
1 1
-1 1


Output

8
0 1 2 0 


Input

1 1
3
4 3
3 4
0 0


Output

32
0 1 2 0 3 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: The Great Game

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Two teams meet in The Game World Championship. Some scientists consider this game to be the most intellectually challenging game in the world. You are given two strings describing the teams' actions in the final battle. Figure out who became the champion.

Input Specification:
The input contains two strings of equal length (between 2 and 20 characters, inclusive). Each line describes the actions of one team.

Output Specification:
Output "TEAM 1 WINS" if the first team won, "TEAM 2 WINS" if the second team won, and "TIE" if there was a tie.

Demo Input:
['[]()[]8&lt;\n8&lt;[]()8&lt;\n', '8&lt;8&lt;()\n[]8&lt;[]\n']

Demo Output:
['TEAM 2 WINS\n', 'TIE\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We are given hours, a list of the number of hours worked per day for a given employee.
A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8.
A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.
Return the length of the longest well-performing interval.
 
Example 1:
Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

 
Constraints:

1 <= hours.length <= 10000
0 <= hours[i] <= 16

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Paul is an excellent coder and sits high on the CW leaderboard. He solves kata like a banshee but would also like to lead a normal life, with other activities. But he just can't stop solving all the kata!!

Given an array (x) you need to calculate the Paul Misery Score. The values are worth the following points:

kata = 5
Petes kata = 10
life = 0
eating = 1

The Misery Score is the total points gained from the array. Once you have the total, return as follows:

<40        = 'Super happy!'<70   >=40 = 'Happy!'<100  >=70 = 'Sad!'\>=100       = 'Miserable!'

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Phoenix loves beautiful arrays. An array is beautiful if all its subarrays of length k have the same sum. A subarray of an array is any sequence of consecutive elements.

Phoenix currently has an array a of length n. He wants to insert some number of integers, possibly zero, into his array such that it becomes beautiful. The inserted integers must be between 1 and n inclusive. Integers may be inserted anywhere (even before the first or after the last element), and he is not trying to minimize the number of inserted integers.

Input

The input consists of multiple test cases. The first line contains an integer t (1 ≤ t ≤ 50) — the number of test cases.

The first line of each test case contains two integers n and k (1 ≤ k ≤ n ≤ 100).

The second line of each test case contains n space-separated integers (1 ≤ a_i ≤ n) — the array that Phoenix currently has. This array may or may not be already beautiful.

Output

For each test case, if it is impossible to create a beautiful array, print -1. Otherwise, print two lines.

The first line should contain the length of the beautiful array m (n ≤ m ≤ 10^4). You don't need to minimize m.

The second line should contain m space-separated integers (1 ≤ b_i ≤ n) — a beautiful array that Phoenix can obtain after inserting some, possibly zero, integers into his array a. You may print integers that weren't originally in array a.

If there are multiple solutions, print any. It's guaranteed that if we can make array a beautiful, we can always make it with resulting length no more than 10^4.

Example

Input


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


Output


5
1 2 1 2 1
4
1 2 2 1
-1
7
4 3 2 1 4 3 2

Note

In the first test case, we can make array a beautiful by inserting the integer 1 at index 3 (in between the two existing 2s). Now, all subarrays of length k=2 have the same sum 3. There exists many other possible solutions, for example: 

  * 2, 1, 2, 1, 2, 1 
  * 1, 2, 1, 2, 1, 2 



In the second test case, the array is already beautiful: all subarrays of length k=3 have the same sum 5.

In the third test case, it can be shown that we cannot insert numbers to make array a beautiful.

In the fourth test case, the array b shown is beautiful and all subarrays of length k=4 have the same sum 10. There exist other solutions also.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp plays a computer game. In this game, the players summon armies of magical minions, which then fight each other.

Polycarp can summon n different minions. The initial power level of the i-th minion is a_i, and when it is summoned, all previously summoned minions' power levels are increased by b_i. The minions can be summoned in any order.

Unfortunately, Polycarp cannot have more than k minions under his control. To get rid of unwanted minions after summoning them, he may destroy them. Each minion can be summoned (and destroyed) only once.

Polycarp's goal is to summon the strongest possible army. Formally, he wants to maximize the sum of power levels of all minions under his control (those which are summoned and not destroyed).

Help Polycarp to make up a plan of actions to summon the strongest possible army!

Input

The first line contains one integer T (1 ≤ T ≤ 75) — the number of test cases.

Each test case begins with a line containing two integers n and k (1 ≤ k ≤ n ≤ 75) — the number of minions availible for summoning, and the maximum number of minions that can be controlled by Polycarp, respectively.

Then n lines follow, the i-th line contains 2 integers a_i and b_i (1 ≤ a_i ≤ 10^5, 0 ≤ b_i ≤ 10^5) — the parameters of the i-th minion.

Output

For each test case print the optimal sequence of actions as follows:

Firstly, print m — the number of actions which Polycarp has to perform (0 ≤ m ≤ 2n). Then print m integers o_1, o_2, ..., o_m, where o_i denotes the i-th action as follows: if the i-th action is to summon the minion x, then o_i = x, and if the i-th action is to destroy the minion x, then o_i = -x. Each minion can be summoned at most once and cannot be destroyed before being summoned (and, obviously, cannot be destroyed more than once). The number of minions in Polycarp's army should be not greater than k after every action.

If there are multiple optimal sequences, print any of them.

Example

Input


3
5 2
5 3
7 0
5 0
4 0
10 0
2 1
10 100
50 10
5 5
1 5
2 4
3 3
4 2
5 1


Output


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

Note

Consider the example test.

In the first test case, Polycarp can summon the minion 2 with power level 7, then summon the minion 1, which will increase the power level of the previous minion by 3, then destroy the minion 1, and finally, summon the minion 5. After this, Polycarp will have two minions with power levels of 10.

In the second test case, Polycarp can control only one minion, so he should choose the strongest of them and summon it.

In the third test case, Polycarp is able to summon and control all five minions.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
For the given sequence with *n* different elements find the number of increasing subsequences with *k*<=+<=1 elements. It is guaranteed that the answer is not greater than 8·1018.

Input Specification:
First line contain two integer values *n* and *k* (1<=≤<=*n*<=≤<=105,<=0<=≤<=*k*<=≤<=10) — the length of sequence and the number of elements in increasing subsequences.

Next *n* lines contains one integer *a**i* (1<=≤<=*a**i*<=≤<=*n*) each — elements of sequence. All values *a**i* are different.

Output Specification:
Print one integer — the answer to the problem.

Demo Input:
['5 2\n1\n2\n3\n5\n4\n']

Demo Output:
['7\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef decided to redecorate his house, and now needs to decide between two different styles of interior design.

For the first style, tiling the floor will cost X_{1} rupees and painting the walls will cost Y_{1} rupees.

For the second style, tiling the floor will cost X_{2} rupees and painting the walls will cost Y_{2} rupees.

Chef will choose whichever style has the lower total cost. How much will Chef pay for his interior design?

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line of input, containing 4 space-separated integers X_{1}, Y_{1}, X_{2}, Y_{2} as described in the statement.

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

For each test case, output on a new line the amount Chef will pay for interior design.

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

$1 ≤ T ≤ 100$
$1 ≤ X_{1}, Y_{1}, X_{2}, Y_{2} ≤ 100$

----- Sample Input 1 ------ 
4
10 20 9 25
10 20 9 20
10 20 20 10
100 43 85 61

----- Sample Output 1 ------ 
30
29
30
143
----- explanation 1 ------ 
Test case $1$: The first style costs $10 + 20 = 30$ rupees, and the second costs $9 + 25 = 34$ rupees. The first is cheaper, so Chef will pay $30$ rupees.

Test case $2$: The first style costs $10 + 20 = 30$ rupees, and the second costs $9 + 20 = 29$ rupees. The second is cheaper, so Chef will pay $29$ rupees.

Test case $3$: The first style costs $10 + 20 = 30$ rupees, and the second costs $20 + 10 = 30$ rupees. Both styles cost the same, so Chef is always going to pay $30$ rupees.

Test case $4$: The first style costs $100 + 43 = 143$ rupees, and the second costs $85 + 61 = 146$ rupees. The first is cheaper, so Chef will pay $143$ rupees.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is very fond of horses. He enjoys watching them race. As expected, he has a stable full of horses. He, along with his friends, goes to his stable during the weekends to watch a few of these horses race. Chef wants his friends to enjoy the race and so he wants the race to be close. This can happen only if the horses are comparable on their skill i.e. the difference in their skills is less.
There are N horses in the stable. The skill of the horse i is represented by an integer S[i]. The Chef needs to pick 2 horses for the race such that the difference in their skills is minimum. This way, he would be able to host a very interesting race. Your task is to help him do this and report the minimum difference that is possible between 2 horses in the race.

-----Input:-----
First line of the input file contains a single integer T, the number of test cases.

Every test case starts with a line containing the integer N.

The next line contains N space separated integers where the i-th integer is S[i].

-----Output:-----
For each test case, output a single line containing the minimum difference that is possible.

-----Constraints:-----
1 ≤ T ≤ 10
2 ≤ N ≤ 5000
1 ≤ S[i] ≤ 1000000000

-----Example:-----Input:
1
5
4 9 1 32 13

Output:
3

Explanation: The minimum difference can be achieved if we pick horses with skills 1 and 4 for the race.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Andre has very specific tastes. Recently he started falling in love with arrays.

Andre calls an nonempty array b good, if sum of its elements is divisible by the length of this array. For example, array [2, 3, 1] is good, as sum of its elements — 6 — is divisible by 3, but array [1, 1, 2, 3] isn't good, as 7 isn't divisible by 4. 

Andre calls an array a of length n perfect if the following conditions hold: 

  * Every nonempty subarray of this array is good. 
  * For every i (1 ≤ i ≤ n), 1 ≤ a_i ≤ 100. 



Given a positive integer n, output any perfect array of length n. We can show that for the given constraints such an array always exists.

An array c is a subarray of an array d if c can be obtained from d by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

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 every test case contains a single integer n (1 ≤ n ≤ 100).

Output

For every test, output any perfect array of length n on a separate line. 

Example

Input


3
1
2
4


Output


24
19 33
7 37 79 49

Note

Array [19, 33] is perfect as all 3 its subarrays: [19], [33], [19, 33], have sums divisible by their lengths, and therefore are good.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a grid with `$m$` rows and `$n$` columns. Return the number of unique ways that start from the top-left corner and go to the bottom-right corner. You are only allowed to move right and down.

For example, in the below grid of `$2$` rows and `$3$` columns, there are `$10$` unique paths:

```
o----o----o----o
|    |    |    |
o----o----o----o
|    |    |    |
o----o----o----o
```

**Note:** there are random tests for grids up to 1000 x 1000 in most languages, so a naive solution will not work.

---
*Hint: use mathematical permutation and combination*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: I'm Feeling Lucky!

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have one chip and one chance to play roulette. Are you feeling lucky?

Input Specification:
none

Output Specification:
Print your bet. Your chip must be placed entirely within some square (not on an edge or a corner shared by adjacent squares).

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that returns the count of characters that have to be removed in order to get a string with no consecutive repeats.

*Note:* This includes any characters

##  Examples

```python
'abbbbc'  => 'abc'    #  answer: 3
'abbcca'  => 'abca'   #  answer: 2
'ab cca'  => 'ab ca'  #  answer: 1
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Indraneel has to sort the books in his library. His library has one long shelf. His books are numbered $1$ through $N$ and he wants to rearrange the books so that they appear in the sequence $1,2, ..., N$.
He intends to do this by a sequence of moves. In each move he can pick up any book from the shelf and insert it at a different place in the shelf. Suppose Indraneel has $5$ books and they are initially arranged in the order
21453214532 \quad 1 \quad 4 \quad 5 \quad 3
Indraneel will rearrange this in ascending order by first moving book $1$ to the beginning of the shelf to get
12453124531 \quad 2 \quad 4 \quad 5 \quad 3
Then, moving book $3$ to position $3$, he gets
12345123451 \quad 2 \quad 3 \quad 4 \quad 5
Your task is to write a program to help Indraneel determine the minimum number of moves that are necessary to sort his book shelf.

-----Input:-----
The first line of the input will contain a single integer $N$ indicating the number of books in Indraneel's library. This is followed by a line containing a permutation of $1, 2, ..., N$ indicating the intial state of Indraneel's book-shelf.

-----Output:-----
A single integer indicating the minimum number of moves necessary to sort Indraneel's book-shelf.

-----Constraints:-----
- $1 \leq N \leq 200000$.
- You may also assume that in $50 \%$ of the inputs, $1 \leq N \leq 5000$.

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

-----Sample Output-----
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation of length n is an array p=[p_1,p_2,...,p_n], which contains every integer from 1 to n (inclusive) and, moreover, each number appears exactly once. For example, p=[3,1,4,2,5] is a permutation of length 5.

For a given number n (n ≥ 2), find a permutation p in which absolute difference (that is, the absolute value of difference) of any two neighboring (adjacent) elements is between 2 and 4, inclusive. Formally, find such permutation p that 2 ≤ |p_i - p_{i+1}| ≤ 4 for each i (1 ≤ i < n).

Print any such permutation for the given integer n or determine that it does not exist.

Input

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

Each test case is described by a single line containing an integer n (2 ≤ n ≤ 1000).

Output

Print t lines. Print a permutation that meets the given requirements. If there are several such permutations, then print any of them. If no such permutation exists, print -1.

Example

Input


6
10
2
4
6
7
13


Output


9 6 10 8 4 7 3 1 5 2 
-1
3 1 4 2 
5 3 6 2 4 1 
5 1 3 6 2 4 7 
13 9 7 11 8 4 1 3 5 2 6 10 12 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer, $N$. Write a program to determine if $N$ is an element of the Fibonacci sequence.  

The first few elements of the Fibonacci sequence are $0,1,1,2,3,5,8,13,\cdots$. A Fibonacci sequence is one where every element is a sum of the previous two elements in the sequence. The first two elements are ${0}$ and ${1}$. 

Formally: 

$\begin{aligned}&\textit{fib}_0=0\\ &\textit{fib}_1=1\\ &\vdots\\ &\textit{fib}_n=fib_{n-1}+fib_{n-2}\forall n>1\end{aligned}$

Function Description   

Complete the isFibo function in the editor below.   

isFibo has the following parameters: 

- int n: the number to check   

Returns 

- string: either IsFibo or IsNotFibo

Input Format 

The first line contains ${t}}$, number of test cases. 

${t}}$ lines follow. Each line contains an integer $n$.

Constraints 

$1\leq t\leq10^5$ 

$1\leq n\leq10^{10}$

Sample Input  

STDIN   Function
-----   --------
3       t = 3
5       n = 5
7       n = 7
8       n = 8

Sample Output  

IsFibo
IsNotFibo
IsFibo

Explanation 

$5$ is a Fibonacci number given by ${fib}_5=3+2$ 

$7$ is not a Fibonacci number 

$8$ is a Fibonacci number given by ${fib}_6=5+3$  

Time Limit 

The time limit for this challenge is given here.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Priority queue is a container of elements which the element with the highest priority should be extracted first.

For $n$ priority queues $Q_i$ ($i = 0, 1, ..., n-1$) of integers, perform a sequence of the following operations.

* insert($t$, $x$): Insert $x$ to $Q_t$.
* getMax($t$): Report the maximum value in $Q_t$. If $Q_t$ is empty, do nothing.
* deleteMax($t$): Delete the maximum element from $Q_t$. If $Q_t$ is empty, do nothing.



In the initial state, all queues are empty.

Constraints

* $1 \leq n \leq 1,000$
* $1 \leq q \leq 200,000$
* $-1,000,000,000 \leq x \leq 1,000,000,000$

Input

The input is given in the following format.


$n \; q$
$query_1$
$query_2$
:
$query_q$


Each query $query_i$ is given by


0 $t$ $x$


or


1 $t$


or


2 $t$


where the first digits 0, 1 and 2 represent insert, getMax and deleteMax operations respectively.

Output

For each getMax operation, print an integer in a line.

Example

Input

2 10
0 0 3
0 0 9
0 0 1
1 0
2 0
1 0
0 0 4
1 0
0 1 8
1 1


Output

9
3
4
8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The MST (Meaningless State Team) company won another tender for an important state reform in Berland.

There are n cities in Berland, some pairs of the cities are connected by roads. Each road has its price. One can move along any road in any direction. The MST team should carry out the repair works on some set of roads such that one can get from any city to any other one moving only along the repaired roads. Moreover, this set should contain exactly k capital roads (that is, the roads that start or finish in the capital). The number of the capital is 1.

As the budget has already been approved, the MST Company will profit by finding the set with minimum lengths of roads.

Input

The first input line contains three integers n, m, k (1 ≤ n ≤ 5000;0 ≤ m ≤ 105;0 ≤ k < 5000), where n is the number of cities in the country, m is the number of roads in the country, k is the number of capital roads in the required set. Then m lines enumerate the roads in question. Each road is specified by three numbers ai, bi, wi (1 ≤ ai, bi ≤ n; 1 ≤ w ≤ 105), where ai, bi are the numbers of cities linked by a road and wi is its length. 

Between each pair of cities no more than one road exists. There are no roads that start and finish in one city. The capital's number is 1.

Output

In the first line print the number of roads in the required set. The second line should contain the numbers of roads included in the sought set. If the sought set does not exist, print -1.

Examples

Input

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


Output

3
1 5 2

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