vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Vasya should paint a fence in front of his own cottage. The fence is a sequence of n wooden boards arranged in a single row. Each board is a 1 centimeter wide rectangle. Let's number the board fence using numbers 1, 2, ..., n from left to right. The height of the i-th board is h_{i} centimeters.

Vasya has a 1 centimeter wide brush and the paint of two colors, red and green. Of course, the amount of the paint is limited. Vasya counted the area he can paint each of the colors. It turned out that he can not paint over a square centimeters of the fence red, and he can not paint over b square centimeters green. Each board of the fence should be painted exactly one of the two colors. Perhaps Vasya won't need one of the colors.

In addition, Vasya wants his fence to look smart. To do this, he should paint the fence so as to minimize the value that Vasya called the fence unattractiveness value. Vasya believes that two consecutive fence boards, painted different colors, look unattractive. The unattractiveness value of a fence is the total length of contact between the neighboring boards of various colors. To make the fence look nice, you need to minimize the value as low as possible. Your task is to find what is the minimum unattractiveness Vasya can get, if he paints his fence completely. $1$ 

The picture shows the fence, where the heights of boards (from left to right) are 2,3,2,4,3,1. The first and the fifth boards are painted red, the others are painted green. The first and the second boards have contact length 2, the fourth and fifth boards have contact length 3, the fifth and the sixth have contact length 1. Therefore, the unattractiveness of the given painted fence is 2+3+1=6.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 200) — the number of boards in Vasya's fence.

The second line contains two integers a and b (0 ≤ a, b ≤ 4·10^4) — the area that can be painted red and the area that can be painted green, correspondingly.

The third line contains a sequence of n integers h_1, h_2, ..., h_{n} (1 ≤ h_{i} ≤ 200) — the heights of the fence boards.

All numbers in the lines are separated by single spaces.


-----Output-----

Print a single number — the minimum unattractiveness value Vasya can get if he paints his fence completely. If it is impossible to do, print  - 1.


-----Examples-----
Input
4
5 7
3 3 4 1

Output
3

Input
3
2 3
1 3 1

Output
2

Input
3
3 3
2 2 2

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 
Chef recently learned about ratios and proportions. He wrote some positive integers a, b, c, d on a paper. Chef wants to know whether he can shuffle these numbers so as to make some proportion? Formally, four numbers x, y, z, w are said to make a proportion if ratio of x : y is same as that of z : w.

------ Input ------ 

Only line of the input contains four space separated positive integers - a, b, c, d.

------ Output ------ 

Print "Possible" if it is possible to shuffle a, b, c, d to make proportion, otherwise "Impossible" (without quotes).

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

$1 ≤ a, b, c, d  ≤ 1000$

----- Sample Input 1 ------ 
1 2 4 2
----- Sample Output 1 ------ 
Possible
----- explanation 1 ------ 
By swapping 4 and the second 2, we get 1 2 2 4. Note that 1 2 2 4 make proportion as 1 : 2 = 2 : 4. Hence answer is "Possible"

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarpus analyzes a string called abracadabra. This string is constructed using the following algorithm: 
 -  On the first step the string consists of a single character "a". -  On the *k*-th step Polycarpus concatenates two copies of the string obtained on the (*k*<=-<=1)-th step, while inserting the *k*-th character of the alphabet between them. Polycarpus uses the alphabet that consists of lowercase Latin letters and digits (a total of 36 characters). The alphabet characters are numbered like this: the 1-st character is "a", the 2-nd — "b", ..., the 26-th — "z", the 27-th — "0", the 28-th — "1", ..., the 36-th — "9". 
Let's have a closer look at the algorithm. On the second step Polycarpus will concatenate two strings "a" and insert the character "b" between them, resulting in "aba" string. The third step will transform it into "abacaba", and the fourth one - into "abacabadabacaba". Thus, the string constructed on the *k*-th step will consist of 2*k*<=-<=1 characters. 

Polycarpus wrote down the string he got after 30 steps of the given algorithm and chose two non-empty substrings of it. Your task is to find the length of the longest common substring of the two substrings selected by Polycarpus.

A substring *s*[*i*... *j*] (1<=≤<=*i*<=≤<=*j*<=≤<=|*s*|) of string *s* = *s*1*s*2... *s*|*s*| is a string *s**i**s**i*<=+<=1... *s**j*. For example, substring *s*[2...4] of string *s* = "abacaba" equals "bac". The string is its own substring.

The longest common substring of two strings *s* and *t* is the longest string that is a substring of both *s* and *t*. For example, the longest common substring of "contest" and "systemtesting" is string "test". There can be several common substrings of maximum length.

Input Specification:
The input consists of a single line containing four integers *l*1, *r*1, *l*2, *r*2 (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=109, *i*<==<=1,<=2). The numbers are separated by single spaces. *l**i* and *r**i* give the indices of the first and the last characters of the *i*-th chosen substring, correspondingly (*i*<==<=1,<=2). The characters of string abracadabra are numbered starting from 1.

Output Specification:
Print a single number — the length of the longest common substring of the given strings. If there are no common substrings, print 0.

Demo Input:
['3 6 1 4\n', '1 1 4 4\n']

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

Note:
In the first sample the first substring is "acab", the second one is "abac". These two substrings have two longest common substrings "ac" and "ab", but we are only interested in their length — 2.

In the second sample the first substring is "a", the second one is "c". These two substrings don't have any common characters, so the length of their longest common substring is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Non-Secret Cypher

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Berland starts to seize the initiative on the war with Flatland. To drive the enemy from their native land, the berlanders need to know exactly how many more flatland soldiers are left in the enemy's reserve. Fortunately, the scouts captured an enemy in the morning, who had a secret encrypted message with the information the berlanders needed so much.

The captured enemy had an array of positive integers. Berland intelligence have long been aware of the flatland code: to convey the message, which contained a number *m*, the enemies use an array of integers *a*. The number of its subarrays, in which there are at least *k* equal numbers, equals *m*. The number *k* has long been known in the Berland army so General Touristov has once again asked Corporal Vasya to perform a simple task: to decipher the flatlanders' message.

Help Vasya, given an array of integers *a* and number *k*, find the number of subarrays of the array of numbers *a*, which has at least *k* equal numbers.

Subarray *a*[*i*... *j*] (1<=≤<=*i*<=≤<=*j*<=≤<=*n*) of array *a*<==<=(*a*1,<=*a*2,<=...,<=*a**n*) is an array, made from its consecutive elements, starting from the *i*-th one and ending with the *j*-th one: *a*[*i*... *j*]<==<=(*a**i*,<=*a**i*<=+<=1,<=...,<=*a**j*).

Input Specification:
The first line contains two space-separated integers *n*, *k* (1<=≤<=*k*<=≤<=*n*<=≤<=4·105), showing how many numbers an array has and how many equal numbers the subarrays are required to have, correspondingly. 

The second line contains *n* space-separated integers *a**i* (1<=≤<=*a**i*<=≤<=109) — elements of the array.

Output Specification:
Print the single number — the number of such subarrays of array *a*, that they have at least *k* equal integers.

Please do not use the %lld specifier to read or write 64-bit integers in С++. In is preferred to use the cin, cout streams or the %I64d specifier.

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

Demo Output:
['3', '2', '6']

Note:
In the first sample are three subarrays, containing at least two equal numbers: (1,2,1), (2,1,2) and (1,2,1,2).

In the second sample are two subarrays, containing three equal numbers: (1,2,1,1,3) and (1,2,1,1).

In the third sample any subarray contains at least one 1 number. Overall they are 6: (1), (1), (1), (1,1), (1,1) and (1,1,1).

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In the evenings Donkey would join Shrek to look at the stars. They would sit on a log, sipping tea and they would watch the starry sky. The sky hung above the roof, right behind the chimney. Shrek's stars were to the right of the chimney and the Donkey's stars were to the left. Most days the Donkey would just count the stars, so he knew that they are exactly *n*. This time he wanted a challenge. He imagined a coordinate system: he put the origin of the coordinates at the intersection of the roof and the chimney, directed the *OX* axis to the left along the roof and the *OY* axis — up along the chimney (see figure). The Donkey imagined two rays emanating from he origin of axes at angles α1 and α2 to the *OX* axis.

Now he chooses any star that lies strictly between these rays. After that he imagines more rays that emanate from this star at the same angles α1 and α2 to the *OX* axis and chooses another star that lies strictly between the new rays. He repeats the operation as long as there still are stars he can choose between the rays that emanate from a star. 

As a result, the Donkey gets a chain of stars. He can consecutively get to each star if he acts by the given rules.

Your task is to find the maximum number of stars *m* that the Donkey's chain can contain.

Note that the chain must necessarily start in the point of the origin of the axes, that isn't taken into consideration while counting the number *m* of stars in the chain.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=105) — the number of stars. The second line contains simple fractions representing relationships "*a*/*b* *c*/*d*", such that  and  (0<=≤<=*a*,<=*b*,<=*c*,<=*d*<=≤<=105; ; ; ). The given numbers *a*, *b*, *c*, *d* are integers.

Next *n* lines contain pairs of integers *x**i*, *y**i* (1<=≤<=*x**i*,<=*y**i*<=≤<=105)— the stars' coordinates.

It is guaranteed that all stars have distinct coordinates.

Output Specification:
In a single line print number *m* — the answer to the problem.

Demo Input:
['15\n1/3 2/1\n3 1\n6 2\n4 2\n2 5\n4 5\n6 6\n3 4\n1 6\n2 1\n7 4\n9 3\n5 3\n1 3\n15 5\n12 4\n']

Demo Output:
['4\n']

Note:
In the sample the longest chain the Donkey can build consists of four stars. Note that the Donkey can't choose the stars that lie on the rays he imagines.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a knapsack with the capacity of W. There are also n items, the i-th one has weight w_i. 

You want to put some of these items into the knapsack in such a way that their total weight C is at least half of its size, but (obviously) does not exceed it. Formally, C should satisfy: ⌈ W/2⌉ ≤ C ≤ W. 

Output the list of items you will put into the knapsack or determine that fulfilling the conditions is impossible. 

If there are several possible lists of items satisfying the conditions, you can output any. Note that you don't have to maximize the sum of weights of items in the knapsack.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^4). Description of the test cases follows.

The first line of each test case contains integers n and W (1 ≤ n ≤ 200 000, 1≤ W ≤ 10^{18}). 

The second line of each test case contains n integers w_1, w_2, ..., w_n (1 ≤ w_i ≤ 10^9) — weights of the items.

The sum of n over all test cases does not exceed 200 000.

Output

For each test case, if there is no solution, print a single integer -1. 

If there exists a solution consisting of m items, print m in the first line of the output and m integers j_1, j_2, ..., j_m (1 ≤ j_i ≤ n, all j_i are distinct) in the second line of the output — indices of the items you would like to pack into the knapsack.

If there are several possible lists of items satisfying the conditions, you can output any. Note that you don't have to maximize the sum of weights items in the knapsack.

Example

Input


3
1 3
3
6 2
19 8 19 69 9 4
7 12
1 1 1 17 1 1 1


Output


1
1
-1
6
1 2 3 5 6 7

Note

In the first test case, you can take the item of weight 3 and fill the knapsack just right.

In the second test case, all the items are larger than the knapsack's capacity. Therefore, the answer is -1.

In the third test case, you fill the knapsack exactly in half.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Taro Aizu's company has a boss who hates being indivisible. When Taro goes out to eat with his boss, he pays by splitting the bill, but when the payment amount is not divisible by the number of participants, his boss always pays for it.

One day, Taro became the secretary of the dinner party. Mr. Taro, who has little money, wondered if he could invite his boss to get a treat. I have to place an order with a restaurant, but I don't know how many people will participate yet, so it seems that I want to place an order so that any number of people can participate. At the same time as Mr. Taro, you who are also planning to attend the dinner party decided to cooperate with Mr. Taro to calculate the amount that is less than the budget amount and is not divisible by any number of people.

Create a program that inputs the type of dish, the price of each dish, and the budget amount, and outputs the total amount (excluding 1 and the total amount) that is not divisible by any number that is less than or equal to the budget amount. You can order multiple dishes of each type, but you do not have to order all types of dishes. However, if there is no such total amount, output NA.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by two lines of zeros. Each dataset is given in the following format:


n x
v1
v2
::
vn


On the first line, the type of dish n (1 ≤ n ≤ 30) and the budget amount x (1 ≤ x ≤ 1000000) are given, separated by blanks. The next n lines are given the integer vi (1 ≤ vi ≤ 1000000), which represents the amount of the i-type dish.

The number of datasets does not exceed 100.

Output

For each input dataset, print the total amount or NA closest to the budget amount on one line.

Example

Input

4 15000
305
260
129
500
3 400
10
20
30
3 200909
5
9
12
0 0


Output

14983
NA
200909

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer n, we need to find a range of positive integers such that all the number in that range are composite and length of that range is n. You may return anyone range in the case of more than one answer.
Input:
First line consists of T test cases. Only line, consists of an Integer N.
Output:
Single line output, "1" if range found else "0".
Constraints:
1<=T<=100
1<=N<=100
Example:
Input:
2
3
5
Output:
1
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Farmer John is hosting a tennis tournament with his n cows. Each cow has a skill level si, and no two cows having the same skill level. Every cow plays every other cow exactly once in the tournament, and each cow beats every cow with skill level lower than its own.

However, Farmer John thinks the tournament will be demoralizing for the weakest cows who lose most or all of their matches, so he wants to flip some of the results. In particular, at k different instances, he will take two integers ai, bi (ai < bi) and flip all the results between cows with skill level between ai and bi inclusive. That is, for any pair x, y <image> he will change the result of the match on the final scoreboard (so if x won the match, the scoreboard will now display that y won the match, and vice versa). It is possible that Farmer John will change the result of a match multiple times. It is not guaranteed that ai and bi are equal to some cow's skill level.

Farmer John wants to determine how balanced he made the tournament results look. In particular, he wants to count the number of triples of cows (p, q, r) for which the final leaderboard shows that cow p beats cow q, cow q beats cow r, and cow r beats cow p. Help him determine this number.

Note that two triples are considered different if they do not contain the same set of cows (i.e. if there is a cow in one triple that is not in the other).

Input

On the first line are two space-separated integers, n and k (3 ≤ n ≤ 105; 0 ≤ k ≤ 105). On the next line are n space-separated distinct integers, s1, s2, ..., sn (1 ≤ si ≤ 109), denoting the skill levels of the cows. On the next k lines are two space separated integers, ai and bi (1 ≤ ai < bi ≤ 109) representing the changes Farmer John made to the scoreboard in the order he makes it.

Output

A single integer, containing the number of triples of cows (p, q, r) for which the final leaderboard shows that cow p beats cow q, cow q beats cow r, and cow r beats cow p.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

3 2
1 2 3
1 2
2 3


Output

1


Input

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


Output

3

Note

In the first sample, cow 3 > cow 1, cow 3 > cow 2, and cow 2 > cow 1. However, the results between cows 1 and 2 and cows 2 and 3 are flipped, so now FJ's results show that cow 1 > cow 2, cow 2 > cow 3, and cow 3 > cow 1, so cows 1, 2, and 3 form a balanced triple. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to write function ```findSum```.

Upto and including ```n```, this function will return the sum of all multiples of 3 and 5.

For example:

```findSum(5)``` should return 8 (3 + 5)

```findSum(10)``` should return 33 (3 + 5 + 6 + 9 + 10)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Welcome to Codeforces Stock Exchange! We're pretty limited now as we currently allow trading on one stock, Codeforces Ltd. We hope you'll still be able to make profit from the market!

In the morning, there are $n$ opportunities to buy shares. The $i$-th of them allows to buy as many shares as you want, each at the price of $s_i$ bourles.

In the evening, there are $m$ opportunities to sell shares. The $i$-th of them allows to sell as many shares as you want, each at the price of $b_i$ bourles. You can't sell more shares than you have.

It's morning now and you possess $r$ bourles and no shares.

What is the maximum number of bourles you can hold after the evening?


-----Input-----

The first line of the input contains three integers $n, m, r$ ($1 \leq n \leq 30$, $1 \leq m \leq 30$, $1 \leq r \leq 1000$) — the number of ways to buy the shares on the market, the number of ways to sell the shares on the market, and the number of bourles you hold now.

The next line contains $n$ integers $s_1, s_2, \dots, s_n$ ($1 \leq s_i \leq 1000$); $s_i$ indicates the opportunity to buy shares at the price of $s_i$ bourles.

The following line contains $m$ integers $b_1, b_2, \dots, b_m$ ($1 \leq b_i \leq 1000$); $b_i$ indicates the opportunity to sell shares at the price of $b_i$ bourles.


-----Output-----

Output a single integer — the maximum number of bourles you can hold after the evening.


-----Examples-----
Input
3 4 11
4 2 5
4 4 5 4

Output
26

Input
2 2 50
5 7
4 2

Output
50



-----Note-----

In the first example test, you have $11$ bourles in the morning. It's optimal to buy $5$ shares of a stock at the price of $2$ bourles in the morning, and then to sell all of them at the price of $5$ bourles in the evening. It's easy to verify that you'll have $26$ bourles after the evening.

In the second example test, it's optimal not to take any action.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You love coffee and want to know what beans you can afford to buy it.

The first argument to your search function will be a number which represents your budget.

The second argument will be an array of coffee bean prices.

Your 'search' function should return the stores that sell coffee within your budget. 

The search function should return a string of prices for the coffees beans you can afford. The prices in this string are to be sorted in ascending order.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi is solving quizzes. He has easily solved all but the last one.
The last quiz has three choices: 1, 2, and 3.
With his supernatural power, Takahashi has found out that the choices A and B are both wrong.
Print the correct choice for this problem.

-----Constraints-----
 - Each of the numbers A and B is 1, 2, or 3.
 - A and B are different.

-----Input-----
Input is given from Standard Input in the following format:
A
B

-----Output-----
Print the correct choice.

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

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

When we know 3 and 1 are both wrong, the correct choice is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given a lower case string and your task will be to remove `k` characters from that string using the following rule:
```Python
- first remove all letter 'a', followed by letter 'b', then 'c', etc...
- remove the leftmost character first.
```

```Python
For example: 
solve('abracadabra', 1) = 'bracadabra' # remove the leftmost 'a'.
solve('abracadabra', 2) = 'brcadabra'  # remove 2 'a' from the left.
solve('abracadabra', 6) = 'rcdbr'      # remove 5 'a', remove 1 'b' 
solve('abracadabra', 8) = 'rdr'
solve('abracadabra',50) = ''
```

More examples in the test cases. Good luck!

Please also try: 

[Simple time difference](https://www.codewars.com/kata/5b76a34ff71e5de9db0000f2)

[Simple remove duplicates](https://www.codewars.com/kata/5ba38ba180824a86850000f7)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have $n \times n$ square grid and an integer $k$. Put an integer in each cell while satisfying the conditions below.  All numbers in the grid should be between $1$ and $k$ inclusive.  Minimum number of the $i$-th row is $1$ ($1 \le i \le n$).  Minimum number of the $j$-th column is $1$ ($1 \le j \le n$). 

Find the number of ways to put integers in the grid. Since the answer can be very large, find the answer modulo $(10^{9} + 7)$. [Image] These are the examples of valid and invalid grid when $n=k=2$. 


-----Input-----

The only line contains two integers $n$ and $k$ ($1 \le n \le 250$, $1 \le k \le 10^{9}$).


-----Output-----

Print the answer modulo $(10^{9} + 7)$.


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

Output
7

Input
123 456789

Output
689974806



-----Note-----

In the first example, following $7$ cases are possible. [Image] 

In the second example, make sure you print the answer modulo $(10^{9} + 7)$.

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