vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given an array of integers nums, you start with an initial positive value startValue.
In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right).
Return the minimum positive value of startValue such that the step by step sum is never less than 1.
 
Example 1:
Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
                step by step sum
                startValue = 4 | startValue = 5 | nums
                  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
                  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
                  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
                  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
                  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

Example 2:
Input: nums = [1,2]
Output: 1
Explanation: Minimum start value should be positive. 

Example 3:
Input: nums = [1,-2,-3]
Output: 5

 
Constraints:

1 <= nums.length <= 100
-100 <= nums[i] <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Oath of the Night's Watch

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
"Night gathers, and now my watch begins. It shall not end until my death. I shall take no wife, hold no lands, father no children. I shall wear no crowns and win no glory. I shall live and die at my post. I am the sword in the darkness. I am the watcher on the walls. I am the shield that guards the realms of men. I pledge my life and honor to the Night's Watch, for this night and all the nights to come." — The Night's Watch oath.

With that begins the watch of Jon Snow. He is assigned the task to support the stewards.

This time he has *n* stewards with him whom he has to provide support. Each steward has his own strength. Jon Snow likes to support a steward only if there exists at least one steward who has strength strictly less than him and at least one steward who has strength strictly greater than him.

Can you find how many stewards will Jon support?

Input Specification:
First line consists of a single integer *n* (1<=≤<=*n*<=≤<=105) — the number of stewards with Jon Snow.

Second line consists of *n* space separated integers *a*1,<=*a*2,<=...,<=*a**n* (0<=≤<=*a**i*<=≤<=109) representing the values assigned to the stewards.

Output Specification:
Output a single integer representing the number of stewards which Jon will feed.

Demo Input:
['2\n1 5\n', '3\n1 2 5\n']

Demo Output:
['0', '1']

Note:
In the first sample, Jon Snow cannot support steward with strength 1 because there is no steward with strength less than 1 and he cannot support steward with strength 5 because there is no steward with strength greater than 5.

In the second sample, Jon Snow can support steward with strength 2 because there are stewards with strength less than 2 and greater than 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Berland Government decided to improve relations with neighboring countries. First of all, it was decided to build new roads so that from each city of Berland and neighboring countries it became possible to reach all the others. There are n cities in Berland and neighboring countries in total and exactly n - 1 two-way roads. Because of the recent financial crisis, the Berland Government is strongly pressed for money, so to build a new road it has to close some of the existing ones. Every day it is possible to close one existing road and immediately build a new one. Your task is to determine how many days would be needed to rebuild roads so that from each city it became possible to reach all the others, and to draw a plan of closure of old roads and building of new ones.

Input

The first line contains integer n (2 ≤ n ≤ 1000) — amount of cities in Berland and neighboring countries. Next n - 1 lines contain the description of roads. Each road is described by two space-separated integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — pair of cities, which the road connects. It can't be more than one road between a pair of cities. No road connects the city with itself.

Output

Output the answer, number t — what is the least amount of days needed to rebuild roads so that from each city it became possible to reach all the others. Then output t lines — the plan of closure of old roads and building of new ones. Each line should describe one day in the format i j u v — it means that road between cities i and j became closed and a new road between cities u and v is built. Cities are numbered from 1. If the answer is not unique, output any.

Examples

Input

2
1 2


Output

0


Input

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


Output

1
3 1 3 7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a number n and an array b_1, b_2, …, b_{n+2}, obtained according to the following algorithm: 

  * some array a_1, a_2, …, a_n was guessed; 
  * array a was written to array b, i.e. b_i = a_i (1 ≤ i ≤ n); 
  * The (n+1)-th element of the array b is the sum of the numbers in the array a, i.e. b_{n+1} = a_1+a_2+…+a_n; 
  * The (n+2)-th element of the array b was written some number x (1 ≤ x ≤ 10^9), i.e. b_{n+2} = x; The 
  * array b was shuffled. 



For example, the array b=[2, 3, 7, 12 ,2] it could be obtained in the following ways: 

  * a=[2, 2, 3] and x=12; 
  * a=[3, 2, 7] and x=2. 



For the given array b, find any array a that could have been guessed initially.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

The first line of each test case contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5).

The second row of each test case contains n+2 integers b_1, b_2, …, b_{n+2} (1 ≤ b_i ≤ 10^9).

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, output: 

  * "-1", if the array b could not be obtained from any array a; 
  * n integers a_1, a_2, …, a_n, otherwise. 



If there are several arrays of a, you can output any.

Example

Input


4
3
2 3 7 12 2
4
9 1 7 1 6 5
5
18 2 2 3 2 9 2
3
2 6 9 2 1


Output


2 3 7 
-1
2 2 2 3 9 
1 2 6 

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Chris knows there's no fun in playing dominoes, he thinks it's too random and doesn't require skill. Instead, he decided to play with the dominoes and make a "domino show".

Chris arranges *n* dominoes in a line, placing each piece vertically upright. In the beginning, he simultaneously pushes some of the dominoes either to the left or to the right. However, somewhere between every two dominoes pushed in the same direction there is at least one domino pushed in the opposite direction.

After each second, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right. When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces. The figure shows one possible example of the process.

Given the initial directions Chris has pushed the dominoes, find the number of the dominoes left standing vertically at the end of the process!

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=3000), the number of the dominoes in the line. The next line contains a character string *s* of length *n*. The *i*-th character of the string *s**i* is equal to 
 -  "L", if the *i*-th domino has been pushed to the left; -  "R", if the *i*-th domino has been pushed to the right; -  ".", if the *i*-th domino has not been pushed. 
It is guaranteed that if *s**i*<==<=*s**j*<==<="L" and *i*<=&lt;<=*j*, then there exists such *k* that *i*<=&lt;<=*k*<=&lt;<=*j* and *s**k*<==<="R"; if *s**i*<==<=*s**j*<==<="R" and *i*<=&lt;<=*j*, then there exists such *k* that *i*<=&lt;<=*k*<=&lt;<=*j* and *s**k*<==<="L".

Output Specification:
Output a single integer, the number of the dominoes that remain vertical at the end of the process.

Demo Input:
['14\n.L.R...LR..L..\n', '5\nR....\n', '1\n.\n']

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

Note:
The first example case is shown on the figure. The four pieces that remain standing vertically are highlighted with orange.

In the second example case, all pieces fall down since the first piece topples all the other pieces.

In the last example case, a single piece has not been pushed in either direction.

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

There are `n` bears in the orchard and they picked a lot of apples. 

They distribute apples like this:

```
The first bear divided the apple into n piles, each with the same number. leaving an apple at last, and the apple was thrown away. Then he took 1 pile and left the n-1 pile.

The second bear divided the apple into n piles, each with the same number. leaving an apple at last, and the apple was thrown away. Then he took 1 pile and left the n-1 pile.

and so on..
```

Hmm.. your task is coming, please calculate the minimum possible number of these apples (before they start distributing)

# Input/Output


`[input]` integer `n`

The number of bears.

`2 <= n <= 9` (JS, Crystal and C)
`2 <= n <= 50` (Ruby and Python)

`[output]` an integer

The minimum possible number of apples.

# Example

For `n = 5`, the output should be `3121`.

```
5 bears distribute apples:

1st bear divided the apples into 5 piles, each pile has 624 apples, and 1 apple was thrown away.
3121 - 1 = 624 x 5
1st bear took 1 pile of apples, 2496 apples left.
3121 - 1 - 624 = 2496

2nd bear divided the apples into 5 piles, each pile has 499 apples, and 1 apple was thrown away.
2496 - 1 = 499 x 5
2nd bear took 1 pile of apples, 1996 apples left.
2496 - 1 - 499 = 1996

3rd bear divided the apples into 5 piles, each pile has 399 apples, and 1 apple was thrown away.
1996 - 1 = 399 x 5
3rd bear took 1 pile of apples, 1596 apples left.
1996 - 1 - 399 = 1596

4th bear divided the apples into 5 piles, each pile has 319 apples, and 1 apple was thrown away.
1596 - 1 = 319 x 5
4th bear took 1 pile of apples, 1276 apples left.
1596 - 1 - 319 = 1276

5th bear divided the apples into 5 piles, each pile has 255 apples, and 1 apple was thrown away.
1276 - 1 = 255 x 5
5th bear took 1 pile of apples, 1020 apples left.
1276 - 1 - 255 = 1020
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a pattern containing only I's and D's. I for increasing and D for decreasing.
Devise an algorithm to print the minimum number following that pattern.
Digits from 1-9 and digits can't repeat.
 
Example 1:
Input:
D
Output:
21
Explanation:
D is meant for decreasing,
So we choose the minimum number
among 21,31,54,87,etc.
 
Example 2:
Input:
IIDDD
Output:
126543
Explanation:
Above example is self- explanatory,
1 < 2 < 6 > 5 > 4 > 3
  I - I - D - D - D
 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function printMinNumberForPattern() which takes the string S and returns a string containing the minimum number following the valid pattern.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ Length of String ≤ 8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ember and Storm play a game. First, Ember picks a labelled tree T of n vertices, such that the degree of every vertex is at most d. Then, Storm picks two distinct vertices u and v in this tree and writes down the labels of the vertices in the path from u to v in a sequence a1, a2... ak. Finally, Ember picks any index i (1 ≤ i < k) in the array. Now he performs one of the following two operations exactly once:

  * flip the subrange [i + 1, k] and add ai to it. After this, the sequence becomes a1, ... ai, ak + ai, ak - 1 + ai, ... ai + 1 + ai
  * negate the subrange [i + 1, k] and add ai to it. i.e., the array becomes a1, ... ai, - ai + 1 + ai, - ai + 2 + ai, ... - ak + ai



Ember wins if the array is monotonically increasing or decreasing after this. Otherwise Storm wins.

The game can be described by the tuple (T, u, v, i, op) where op is «flip» or «negate» depending on the action Ember chose in the last turn. Find the number of tuples that can occur if Ember and Storm play optimally. When they play optimally, if there are multiple moves by which they are guaranteed to win, then they may play any of the winning moves. Otherwise, if someone loses no matter what they play, then they may play any of the possible moves.

Report the answer modulo m.

Input

The input consists of a single line containing three integers n, d and m (2 ≤ n ≤ 200, 1 ≤ d < n, 1 ≤ m ≤ 2·109).

Output

Print a single number — the number of possible tuples if Ember and Storm play as described, modulo m.

Examples

Input

2 1 1000000007


Output

4


Input

3 1 250


Output

0


Input

3 2 100


Output

36

Note

In the first sample case, there is only one possible tree. There are two possible paths, 1 to 2 and 2 to 1. For both paths, i can only be 1, and op can take both possibilities. Therefore, the answer is 4.

In the second sample, there are no possible trees.

In the third sample, there are three possible trees. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The New Year celebrations in Berland last n days. Only this year the winter is snowless, that’s why the winter celebrations’ organizers should buy artificial snow. There are m snow selling companies in Berland. Every day the i-th company produces wi cubic meters of snow. Next day the snow thaws and the company has to produce wi cubic meters of snow again. During the celebration new year discounts are on, that’s why the snow cost decreases every day. It is known that on the first day the total cost of all the snow produced by the i-th company is equal to ci bourles. Every day this total cost decreases by ai bourles, i.e. on the second day it is equal to ci - ai,and on the third day — to ci - 2ai, and so on. It is known that for one company the cost of the snow produced by it does not get negative or equal to zero. You have to organize the snow purchase so as to buy every day exactly W snow cubic meters. At that it is not necessary to buy from any company all the snow produced by it. If you buy ni cubic meters of snow (0 ≤ ni ≤ wi, the number ni is not necessarily integer!) from the i-th company at one of the days when the cost of its snow is equal to si, then its price will total to <image> bourles. During one day one can buy the snow from several companies. In different days one can buy the snow from different companies. It is required to make the purchases so as to spend as little money as possible. It is guaranteed that the snow produced by the companies will be enough.

Input

The first line contains integers n, m and W (1 ≤ n ≤ 100, 1 ≤ m ≤ 500000, 1 ≤ W ≤ 109) which represent the number of days, the number of companies and the amount of snow that needs to be purchased on every one of the n days. The second line contains m integers wi. The third line contains m integers ci. The fourth line contains m integers ai. All the numbers are strictly positive and do not exceed 109. For all the i the inequation ci - (n - 1)ai > 0 holds true. 

Output

Print a single number — the answer to the given problem. Print the answer in the format with the decimal point (even if the answer is integer, it must contain the decimal point), without "e" and without leading zeroes. The answer should differ with the right one by no more than 10 - 9.

Examples

Input

2 3 10
4 4 4
5 5 8
1 2 5


Output

22.000000000000000


Input

100 2 1000000000
999999998 999999999
1000000000 1000000000
1 1


Output

99999995149.999995249999991

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string s consisting of n characters. These characters are among the first k lowercase letters of the Latin alphabet. You have to perform n operations with the string.

During the i-th operation, you take the character that initially occupied the i-th position, and perform one of the following actions with it:

  * swap it with the previous character in the string (if it exists). This operation is represented as L; 
  * swap it with the next character in the string (if it exists). This operation is represented as R; 
  * cyclically change it to the previous character in the alphabet (b becomes a, c becomes b, and so on; a becomes the k-th letter of the Latin alphabet). This operation is represented as D; 
  * cyclically change it to the next character in the alphabet (a becomes b, b becomes c, and so on; the k-th letter of the Latin alphabet becomes a). This operation is represented as U; 
  * do nothing. This operation is represented as 0. 



For example, suppose the initial string is test, k = 20, and the sequence of operations is URLD. Then the string is transformed as follows:

  1. the first operation is U, so we change the underlined letter in test to the next one in the first 20 Latin letters, which is a. The string is now aest; 
  2. the second operation is R, so we swap the underlined letter with the next one in the string aest. The string is now aset; 
  3. the third operation is L, so we swap the underlined letter with the previous one in the string aset (note that this is now the 2-nd character of the string, but it was initially the 3-rd one, so the 3-rd operation is performed to it). The resulting string is saet; 
  4. the fourth operation is D, so we change the underlined letter in saet to the previous one in the first 20 Latin letters, which is s. The string is now saes. 



The result of performing the sequence of operations is saes.

Given the string s and the value of k, find the lexicographically smallest string that can be obtained after applying a sequence of operations to s.

Input

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

Each test case consists of two lines. The first line contains two integers n and k (1 ≤ n ≤ 500; 2 ≤ k ≤ 26). 

The second line contains a string s consisting of n characters. Each character is one of the k first letters of the Latin alphabet (in lower case).

Output

For each test case, print one line containing the lexicographically smallest string that can be obtained from s using one sequence of operations.

Example

Input


6
4 2
bbab
7 5
cceddda
6 5
ecdaed
7 4
dcdbdaa
8 3
ccabbaca
5 7
eabba


Output


aaaa
baccacd
aabdac
aabacad
aaaaaaaa
abadb

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n arrays a_1, a_2, ..., a_n; each array consists of exactly m integers. We denote the y-th element of the x-th array as a_{x, y}.

You have to choose two arrays a_i and a_j (1 ≤ i, j ≤ n, it is possible that i = j). After that, you will obtain a new array b consisting of m integers, such that for every k ∈ [1, m] b_k = max(a_{i, k}, a_{j, k}).

Your goal is to choose i and j so that the value of min _{k = 1}^{m} b_k is maximum possible.

Input

The first line contains two integers n and m (1 ≤ n ≤ 3 ⋅ 10^5, 1 ≤ m ≤ 8) — the number of arrays and the number of elements in each array, respectively.

Then n lines follow, the x-th line contains the array a_x represented by m integers a_{x, 1}, a_{x, 2}, ..., a_{x, m} (0 ≤ a_{x, y} ≤ 10^9).

Output

Print two integers i and j (1 ≤ i, j ≤ n, it is possible that i = j) — the indices of the two arrays you have to choose so that the value of min _{k = 1}^{m} b_k is maximum possible. If there are multiple answers, print any of them.

Example

Input


6 5
5 0 3 1 2
1 8 9 1 3
1 2 3 4 5
9 1 0 3 7
2 3 0 6 3
6 4 1 7 0


Output


1 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers K and S.

Three variable X, Y and Z takes integer values satisfying 0≤X,Y,Z≤K.

How many different assignments of values to X, Y and Z are there such that X + Y + Z = S?  

-----Constraints-----
 - 2≤K≤2500 
 - 0≤S≤3K 
 - K and S are integers.  

-----Input-----
The input is given from Standard Input in the following format:
K S

-----Output-----
Print the number of the triples of X, Y and Z that satisfy the condition.

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

-----Sample Output-----
6

There are six triples of X, Y and Z that satisfy the condition:
 - X = 0, Y = 0, Z = 2 
 - X = 0, Y = 2, Z = 0 
 - X = 2, Y = 0, Z = 0 
 - X = 0, Y = 1, Z = 1 
 - X = 1, Y = 0, Z = 1 
 - X = 1, Y = 1, Z = 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kolya Gerasimov loves kefir very much. He lives in year 1984 and knows all the details of buying this delicious drink. One day, as you probably know, he found himself in year 2084, and buying kefir there is much more complicated.

Kolya is hungry, so he went to the nearest milk shop. In 2084 you may buy kefir in a plastic liter bottle, that costs a rubles, or in glass liter bottle, that costs b rubles. Also, you may return empty glass bottle and get c (c < b) rubles back, but you cannot return plastic bottles.

Kolya has n rubles and he is really hungry, so he wants to drink as much kefir as possible. There were no plastic bottles in his 1984, so Kolya doesn't know how to act optimally and asks for your help.


-----Input-----

First line of the input contains a single integer n (1 ≤ n ≤ 10^18) — the number of rubles Kolya has at the beginning.

Then follow three lines containing integers a, b and c (1 ≤ a ≤ 10^18, 1 ≤ c < b ≤ 10^18) — the cost of one plastic liter bottle, the cost of one glass liter bottle and the money one can get back by returning an empty glass bottle, respectively.


-----Output-----

Print the only integer — maximum number of liters of kefir, that Kolya can drink.


-----Examples-----
Input
10
11
9
8

Output
2

Input
10
5
6
1

Output
2



-----Note-----

In the first sample, Kolya can buy one glass bottle, then return it and buy one more glass bottle. Thus he will drink 2 liters of kefir.

In the second sample, Kolya can buy two plastic bottle and get two liters of kefir, or he can buy one liter glass bottle, then return it and buy one plastic bottle. In both cases he will drink two liters of kefir.

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