vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Chefland is a $1D$ city where each of the $N$ houses is located at a distinct positive integer coordinate $A_{1}, A_{2}, \ldots A_{N}$. The chef is planning to create $K$ hills in the city. Note that two hills cannot be present at the same location but the location of hills and houses can overlap and each hill will also be at any integer (positive, negative or zero) coordinate. 

Each citizen would want to travel to the farthest hill from his house. Travelling will create air pollution and Chef wants to minimise the total pollution in the city. Help Chef find the minimum sum of distance travelled by everyone. In other words, help Chef create the hills at optimal locations, so that the sum of the distance of every house to the hill farthest from it is minimum possible.

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contains two lines of input.
First line contains $2$ integers $N, K$ separated by a space.
Second line contains $N$ integers $A_{1}, A_{2}, \ldots, A_{N}$, representing the location of the houses. 

------ Output: ------
For each testcase, find the minimum possible sum of distances if Chef creates the hills at optimal locations, in a separate line.

------ Constraints  ------
$1 ≤ T ≤ 10$
$1 ≤ N, K ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
$A_{i} < A_{i + 1} \forall$ valid $i$

----- Sample Input 1 ------ 
3

3 1

1 2 3

1 5

1

2 2

1 5
----- Sample Output 1 ------ 
2

2

5
----- explanation 1 ------ 
TestCase 1: Optimal solution includes creating hill at $2$. Its distance from the house at coordinate $1$ is $1$, and so is its distance from the house at coordinate $3$. Its distance from the house at coordinate $2$ is $0$. Thus, total distance is $1+0+1=2$.

TestCase 2: Optimal solution includes creating hills at $\{-1, 0, 1, 2, 3 \}$. The farthest hills from the house at coordinate $1$ are at coordinates $-1$ and $3$. The citizen can choose to travel to any of them, and the distance shall be $2$.

TestCase 3: Optimal solution includes creating hills at $\{1, 2 \}$ or $\{4, 5 \}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a board of size $n \times n$, where $n$ is odd (not divisible by $2$). Initially, each cell of the board contains one figure.

In one move, you can select exactly one figure presented in some cell and move it to one of the cells sharing a side or a corner with the current cell, i.e. from the cell $(i, j)$ you can move the figure to cells:   $(i - 1, j - 1)$;  $(i - 1, j)$;  $(i - 1, j + 1)$;  $(i, j - 1)$;  $(i, j + 1)$;  $(i + 1, j - 1)$;  $(i + 1, j)$;  $(i + 1, j + 1)$; 

Of course, you can not move figures to cells out of the board. It is allowed that after a move there will be several figures in one cell.

Your task is to find the minimum number of moves needed to get all the figures into one cell (i.e. $n^2-1$ cells should contain $0$ figures and one cell should contain $n^2$ figures).

You have to answer $t$ independent test cases.


-----Input-----

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

The only line of the test case contains one integer $n$ ($1 \le n < 5 \cdot 10^5$) — the size of the board. It is guaranteed that $n$ is odd (not divisible by $2$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$ ($\sum n \le 5 \cdot 10^5$).


-----Output-----

For each test case print the answer — the minimum number of moves needed to get all the figures into one cell.


-----Example-----
Input
3
1
5
499993

Output
0
40
41664916690999888

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Lena is a programmer. She got a task to solve at work.

There is an empty set of pairs of integers and *n* queries to process. Each query is one of three types:
 1.  Add a pair (*a*,<=*b*) to the set. 1.  Remove a pair added in the query number *i*. All queries are numbered with integers from 1 to *n*. 1.  For a given integer *q* find the maximal value *x*·*q*<=+<=*y* over all pairs (*x*,<=*y*) from the set. 
Help Lena to process the queries.

Input Specification:
The first line of input contains integer *n* (1<=≤<=*n*<=≤<=3·105) — the number of queries.

Each of the next *n* lines starts with integer *t* (1<=≤<=*t*<=≤<=3) — the type of the query.

A pair of integers *a* and *b* (<=-<=109<=≤<=*a*,<=*b*<=≤<=109) follows in the query of the first type.

An integer *i* (1<=≤<=*i*<=≤<=*n*) follows in the query of the second type. It is guaranteed that *i* is less than the number of the query, the query number *i* has the first type and the pair from the *i*-th query is not already removed.

An integer *q* (<=-<=109<=≤<=*q*<=≤<=109) follows in the query of the third type.

Output Specification:
For the queries of the third type print on a separate line the desired maximal value of *x*·*q*<=+<=*y*.

If there are no pairs in the set print "EMPTY SET".

Demo Input:
['7\n3 1\n1 2 3\n3 1\n1 -1 100\n3 1\n2 4\n3 1\n']

Demo Output:
['EMPTY SET\n5\n99\n5\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Advertising has become part of our routine. And now, in the era of progressive technologies, we need your ideas to make advertising better!

In this problem we'll look at a simplified version of context advertising. You've got a text, consisting of exactly n words. A standard advertising banner has exactly r lines, each line can contain at most c characters. The potential customer always likes it when they can see lots of advertising, so you should determine which maximum number of consecutive words from the text can be written on the banner. Single words in one line of the banner should be separated by spaces. You are allowed to insert more than one space at once. Note that you are not allowed to break the words, that is, each word in the text must occupy exactly one line in the banner. Besides, you cannot change the word order, that is, if you read the banner text consecutively, from top to bottom and from left to right, you should get some consecutive part of the advertisement text.

More formally, the statement can be written like that. Let's say that all words are indexed from 1 to n in the order in which they occur in the advertisement text. Then you have to choose all words, starting from some i-th one and ending with some j-th one (1 ≤ i ≤ j ≤ n), so that all of them could be written on the banner. There must be as many words as possible. See the samples for clarifications.

Input

The first input line contains three integers n, r, c (1 ≤ n, r, c ≤ 106; r × c ≤ 106). The next line contains a text, consisting of n words. The words consist only of lowercase English letters and are not empty. The words in the lines are separated by single spaces. The total number of characters in all words doesn't exceed 5·106.

Output

Print at most r lines, in each line print at most c characters — the optimal advertisement banner. If there are multiple advertisement banners, print any of them. 

Note that some lines of the banner can be empty. You are allowed not to print such lines.

Examples

Input

9 4 12
this is a sample text for croc final round


Output

this is a
sample text
for croc
final round


Input

9 1 9
this is a sample text for croc final round


Output

this is a


Input

6 2 3
croc a a a croc a


Output

a a
a


Input

2 2 5
first second


Output

first

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A country has coins with denominations
```python
coins_list = d1 < d2 < · · · < dn.
```
You want to make change for n cents, using the smallest number of coins.

```python
# Example 1: U.S. coins
d1 = 1 d2 = 5 d3 = 10 d4 = 25

## Optimal change for 37 cents – 1 quarter, 1 dime, 2 pennies.

# Example 2: Alien Planet Z coins
Z_coin_a = 1 Z_coin_b = 3 Z_coin_c = 4

## Optimal change for 6 cents - 2 Z_coin_b's
```

Write a function that will take a list of coin denominations and a desired amount and provide the least amount of coins needed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Airports are being built on a straight road according to a new construction plan. For convenience, imagine a number line on which at different points airports can be positioned. Because a plane can't take off and start landing immediately, there will be flight between two airports in locations $\boldsymbol{x}$ and $y$ if and only if $|x-y|\geq d$, where $\boldsymbol{d}$ is a constant.

Changing the position of an airport from $\boldsymbol{x}$ to $y$ costs $|x-y|$. The cost to fix a certain plan is the minimum total cost of changing the positions of airports. After the changes, it should be possible to travel between any pair of airports, possibly taking flights through some intermediate airports. Note that it's possible that two airports have the same initial position, and this can be the case  after changes too.

On $i^{\mbox{th}}$ day, a plan to build a new airport with position $x_i$ is announced. On each day that a new airport is announced, print the smallest cost to fix the set of airports announced so far . Note that you should not change the positions of any airports, just calculate the cost to do it.

Input Format

Input contains multiple queries. 

The first line consists of an integer $\textit{q}$ which is the number of queries. Each query is given as follows. 

The first line of each query contains two integers $n$ and $\boldsymbol{d}$, the number of days, and the minimum distance respectively. 

The second line of each test case contains $n$ space-separated integers $x_i$ denoting the position of the airport that was announced on $i^{\mbox{th}}$ day.

Constraints

$3\leq n\leq2\times10^5$
$|x_i|\leq10^8$
$0\leq d\leq10^8$
the sum of $n$ over all test cases in a file will not exceed $2\cdot10^{5}$

Output Format

Print one line for each query. 

A line for a query with $n$ airports should have $n$ numbers on it where the $i^{\mbox{th}}$ one should be the minimum cost to fix airports in positions $x_{1},x_{2},\ldots,x_{i}$.

Sample Input 0
1
3 1
0 0 0

Sample Output 0
0 1 1

Explanation 0

The answer for a single airport is always zero. When we have many airports in the same position, it's enough to move only one of them to satisfy the condition from the statement.

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

Sample Output 1
0 2 2 3 3

Explanation 1

For each new day that an airport is inserted, the cheapest rearranging of existing airports is shown on the diagram above. Note that cost changes for every day and travelling between airports can be done possibly flying through some intermediate ones. Costs are calculated without changing actual positions of the airports.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n cities and m edges connected by some number of flights. You are given an array flights where flights[i] = [from_{i}, to_{i}, price_{i}] indicates that there is a flight from the city from_{i} to city to_{i} with cost price_{i}.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
 
Note: The price from city A to B may be different From price from city B to A. 
Example 1:
Input:
n = 4
flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
src = 0
dst = 3
k = 1
Output:
700
Explanation:
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
Constraint:
1 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= from_{i}, to_{i} < n
from_{i} != to_{i}
1 <= price_{i} <= 10^{4}
There will not be any multiple flights between the two cities.
0 <= src, dst, k < n
src != dst

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are well-known formulas: <image>, <image>, <image>. Also mathematicians found similar formulas for higher degrees.

Find the value of the sum <image> modulo 109 + 7 (so you should find the remainder after dividing the answer by the value 109 + 7).

Input

The only line contains two integers n, k (1 ≤ n ≤ 109, 0 ≤ k ≤ 106).

Output

Print the only integer a — the remainder after dividing the value of the sum by the value 109 + 7.

Examples

Input

4 1


Output

10


Input

4 2


Output

30


Input

4 3


Output

100


Input

4 0


Output

4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two arrays A and B consisting of integers, sorted in non-decreasing order. Check whether it is possible to choose k numbers in array A and choose m numbers in array B so that any number chosen in the first array is strictly less than any number chosen in the second array.

Input

The first line contains two integers nA, nB (1 ≤ nA, nB ≤ 105), separated by a space — the sizes of arrays A and B, correspondingly.

The second line contains two integers k and m (1 ≤ k ≤ nA, 1 ≤ m ≤ nB), separated by a space.

The third line contains nA numbers a1, a2, ... anA ( - 109 ≤ a1 ≤ a2 ≤ ... ≤ anA ≤ 109), separated by spaces — elements of array A.

The fourth line contains nB integers b1, b2, ... bnB ( - 109 ≤ b1 ≤ b2 ≤ ... ≤ bnB ≤ 109), separated by spaces — elements of array B.

Output

Print "YES" (without the quotes), if you can choose k numbers in array A and m numbers in array B so that any number chosen in array A was strictly less than any number chosen in array B. Otherwise, print "NO" (without the quotes).

Examples

Input

3 3
2 1
1 2 3
3 4 5


Output

YES


Input

3 3
3 3
1 2 3
3 4 5


Output

NO


Input

5 2
3 1
1 1 1 1 1
2 2


Output

YES

Note

In the first sample test you can, for example, choose numbers 1 and 2 from array A and number 3 from array B (1 < 3 and 2 < 3).

In the second sample test the only way to choose k elements in the first array and m elements in the second one is to choose all numbers in both arrays, but then not all the numbers chosen in A will be less than all the numbers chosen in B: <image>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Seyyed and MoJaK are friends of Sajjad. Sajjad likes a permutation. Seyyed wants to change the permutation in a way that Sajjad won't like it. Seyyed thinks more swaps yield more probability to do that, so he makes MoJaK to perform a swap between every pair of positions (i, j), where i < j, exactly once. MoJaK doesn't like to upset Sajjad.

Given the permutation, determine whether it is possible to swap all pairs of positions so that the permutation stays the same. If it is possible find how to do that. 


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 1000) — the size of the permutation.

As the permutation is not important, you can consider a_{i} = i, where the permutation is a_1, a_2, ..., a_{n}.


-----Output-----

If it is not possible to swap all pairs of positions so that the permutation stays the same, print "NO",

Otherwise print "YES", then print $\frac{n(n - 1)}{2}$ lines: the i-th of these lines should contain two integers a and b (a < b) — the positions where the i-th swap is performed.


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

Output
NO

Input
1

Output
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N robots and M exits on a number line. The N + M coordinates of these are all integers and all distinct. For each i (1 \leq i \leq N), the coordinate of the i-th robot from the left is x_i. Also, for each j (1 \leq j \leq M), the coordinate of the j-th exit from the left is y_j.

Snuke can repeatedly perform the following two kinds of operations in any order to move all the robots simultaneously:

* Increment the coordinates of all the robots on the number line by 1.
* Decrement the coordinates of all the robots on the number line by 1.



Each robot will disappear from the number line when its position coincides with that of an exit, going through that exit. Snuke will continue performing operations until all the robots disappear.

When all the robots disappear, how many combinations of exits can be used by the robots? Find the count modulo 10^9 + 7. Here, two combinations of exits are considered different when there is a robot that used different exits in those two combinations.

Constraints

* 1 \leq N, M \leq 10^5
* 1 \leq x_1 < x_2 < ... < x_N \leq 10^9
* 1 \leq y_1 < y_2 < ... < y_M \leq 10^9
* All given coordinates are integers.
* All given coordinates are distinct.

Input

Input is given from Standard Input in the following format:


N M
x_1 x_2 ... x_N
y_1 y_2 ... y_M


Output

Print the number of the combinations of exits that can be used by the robots when all the robots disappear, modulo 10^9 + 7.

Examples

Input

2 2
2 3
1 4


Output

3


Input

3 4
2 5 10
1 3 7 13


Output

8


Input

4 1
1 2 4 5
3


Output

1


Input

4 5
2 5 7 11
1 3 6 9 13


Output

6


Input

10 10
4 13 15 18 19 20 21 22 25 27
1 5 11 12 14 16 23 26 29 30


Output

22

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
To destroy humanity, The Monster Association sent $n$ monsters to Earth's surface. The $i$-th monster has health $h_i$ and power $p_i$.

With his last resort attack, True Spiral Incineration Cannon, Genos can deal $k$ damage to all monsters alive. In other words, Genos can reduce the health of all monsters by $k$ (if $k > 0$) with a single attack.

However, after every attack Genos makes, the monsters advance. With their combined efforts, they reduce Genos' attack damage by the power of the $^\dagger$weakest monster $^\ddagger$alive. In other words, the minimum $p_i$ among all currently living monsters is subtracted from the value of $k$ after each attack.

$^\dagger$The Weakest monster is the one with the least power.

$^\ddagger$A monster is alive if its health is strictly greater than $0$.

Will Genos be successful in killing all the monsters?


-----Input-----

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

The first line of each test case contains two integers, $n$ and $k$ ($1 \le n, k \le 10^5$) — the number of monsters and Genos' initial attack damage. Then two lines follow, each containing $n$ integers describing the arrays $h$ and $p$ ($1 \le h_i, p_i \le 10^9$).

It's guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print the answer — "YES" (without quotes) if Genos could kill all monsters and "NO" otherwise.


-----Examples-----

Input
3
6 7
18 5 13 9 10 1
2 7 2 1 2 6
3 4
5 5 5
4 4 4
3 2
2 1 3
1 1 1
Output
YES
NO
YES


-----Note-----

In the first example, after Genos' first attack, $h$ and $k$ will update to:

$h: [11,0,6,2,3,0]$

$k: 7-1 = 6$

After second attack:

$h: [5,0,0,0,0,0]$

$k: 6-2 = 4$

After third attack:

$h: [1,0,0,0,0,0]$

$k: 4-2 = 2$

After fourth attack:

$h: [0,0,0,0,0,0]$

As Genos could kill all monsters, the answer is YES.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We will consider the numbers $a$ and $b$ as adjacent if they differ by exactly one, that is, $|a-b|=1$.

We will consider cells of a square matrix $n \times n$ as adjacent if they have a common side, that is, for cell $(r, c)$ cells $(r, c-1)$, $(r, c+1)$, $(r-1, c)$ and $(r+1, c)$ are adjacent to it.

For a given number $n$, construct a square matrix $n \times n$ such that:

Each integer from $1$ to $n^2$ occurs in this matrix exactly once;

If $(r_1, c_1)$ and $(r_2, c_2)$ are adjacent cells, then the numbers written in them must not be adjacent.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$). Then $t$ test cases follow.

Each test case is characterized by one integer $n$ ($1 \le n \le 100$).


-----Output-----

For each test case, output:

-1, if the required matrix does not exist;

the required matrix, otherwise (any such matrix if many of them exist).

The matrix should be outputted as $n$ lines, where each line contains $n$ integers.


-----Examples-----

Input
3
1
2
3
Output
1
-1
2 9 7
4 6 3
1 8 5


-----Note-----

None

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya has got 2*n* cards, each card contains some integer. The numbers on the cards can be the same. Let's index all cards by consecutive integers from 1 to 2*n*. We'll denote the number that is written on a card with number *i*, as *a**i*. In order to play one entertaining game with his friends, Petya needs to split the cards into pairs so that each pair had equal numbers on the cards. Help Petya do that.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=3·105). The second line contains the sequence of 2*n* positive integers *a*1,<=*a*2,<=...,<=*a*2*n* (1<=≤<=*a**i*<=≤<=5000) — the numbers that are written on the cards. The numbers on the line are separated by single spaces.

Output Specification:
If it is impossible to divide the cards into pairs so that cards in each pair had the same numbers, print on a single line integer -1. But if the required partition exists, then print *n* pairs of integers, a pair per line — the indices of the cards that form the pairs.

Separate the numbers on the lines by spaces. You can print the pairs and the numbers in the pairs in any order. If there are multiple solutions, print any of them.

Demo Input:
['3\n20 30 10 30 20 10\n', '1\n1 2\n']

Demo Output:
['4 2\n1 5\n6 3\n', '-1']

Note:
none

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