vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:


Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.


Example 2:


Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little X has met the following problem recently. 

Let's define *f*(*x*) as the sum of digits in decimal representation of number *x* (for example, *f*(1234)<==<=1<=+<=2<=+<=3<=+<=4). You are to calculate 

Of course Little X has solved this problem quickly, has locked it, and then has tried to hack others. He has seen the following C++ code:

Input Specification:
The first line contains a single integer *a* (1<=≤<=*a*<=≤<=1018).

Output Specification:
Print two integers: *l*,<=*r* (1<=≤<=*l*<=≤<=*r*<=&lt;<=10200) — the required test data. Leading zeros aren't allowed. It's guaranteed that the solution exists.

Demo Input:
['46\n', '126444381000032\n']

Demo Output:
['1 10\n', '2333333 2333333333333\n']

Note:
none

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

A string is called a square string if it can be obtained by concatenating two copies of the same string. For example, "abab", "aa" are square strings, while "aaa", "abba" are not. Given a string, how many (non-empty) subsequences of the string are square strings? A subsequence of a string can be obtained by deleting zero or more characters from it, and maintaining the relative order of the remaining characters.

Input Format

The first line contains the number of test cases, $T$. 

$T$ test cases follow. Each case contains a string, $S$.

Output Format

Output $T$ lines, one for each test case, containing the required answer modulo 1000000007.

Constraints: 

$1\leq T\leq20$ 

$S$ will have at most $200$ lowercase characters ('a' - 'z').

Sample Input

3 

aaa 

abab 

baaba

Sample Output

3 

3 

6

Explanation

For the first case, there are 3 subsequences of length 2, all of which are square strings. 

For the second case, the subsequences "abab", "aa", "bb" are square strings. 

Similarly, for the third case, "bb", "baba" (twice), and "aa" (3 of them) are the square subsequences.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string t and n strings s_1, s_2, ..., s_n. All strings consist of lowercase Latin letters.

Let f(t, s) be the number of occurences of string s in string t. For example, f('aaabacaa', 'aa') = 3, and f('ababa', 'aba') = 2.

Calculate the value of ∑_{i=1}^{n} ∑_{j=1}^{n} f(t, s_i + s_j), where s + t is the concatenation of strings s and t. Note that if there are two pairs i_1, j_1 and i_2, j_2 such that s_{i_1} + s_{j_1} = s_{i_2} + s_{j_2}, you should include both f(t, s_{i_1} + s_{j_1}) and f(t, s_{i_2} + s_{j_2}) in answer.

Input

The first line contains string t (1 ≤ |t| ≤ 2 ⋅ 10^5).

The second line contains integer n (1 ≤ n ≤ 2 ⋅ 10^5).

Each of next n lines contains string s_i (1 ≤ |s_i| ≤ 2 ⋅ 10^5).

It is guaranteed that ∑_{i=1}^{n} |s_i| ≤ 2 ⋅ 10^5. All strings consist of lowercase English letters.

Output

Print one integer — the value of ∑_{i=1}^{n} ∑_{j=1}^{n} f(t, s_i + s_j).

Examples

Input


aaabacaa
2
a
aa


Output


5


Input


aaabacaa
4
a
a
a
b


Output


33

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is a really nice and respectful person, in sharp contrast to his little brother, who is a very nasty and disrespectful person. Chef always sends messages to his friends in all small letters, whereas the little brother sends messages in all capital letters.
You just received a message given by a string s. You don't know whether this message is sent by Chef or his brother. Also, the communication channel through which you received the message is erroneous and hence can flip a letter from uppercase to lowercase or vice versa. However, you know that this channel can make at most K such flips.
Determine whether the message could have been sent only by Chef, only by the little brother, by both or by none.

-----Input-----

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers N and K denoting the length of the string s and the maximum number of flips that the erroneous channel can make.
- The second line contains a single string s denoting the message you received.

-----Output-----
For each test case, output a single line containing one string — "chef", "brother", "both" or "none".

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 100
- 0 ≤ K ≤ N
- s consists only of (lowercase and uppercase) English letters

-----Example-----
Input

4
5 1
frauD
5 1
FRAUD
4 4
Life
10 4
sTRAWBerry

Output

chef
brother
both
none

-----Explanation-----
Example case 1: Only one flip is possible. So it is possible that Chef sent "fraud" and the channel flipped the last character to get "frauD". However, it is not possible for the brother to have sent "FRAUD", because then it would need 4 flips. Hence the answer is "chef".
Example case 2: Only one flip is possible. So it is possible that the brother sent "FRAUD" and the channel didn't flip anything. However, it is not possible for Chef to have sent "fraud", because then it would need 5 flips. Hence the answer is "brother".
Example case 3: Four flips are allowed. It is possible that Chef sent "life" and the channel flipped the first character to get "Life". It is also possible that the brother sent "LIFE" and the channel flipped the last three characters to get "Life". Hence the answer is "both".
Example case 4: Four flips are allowed. It is not possible that Chef sent "strawberry", because it would need five flips to get "sTRAWBerry". It is also not possible that the brother sent "STRAWBERRY", because that would also need five flips. Hence the answer is "none".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Each student eagerly awaits the day he would pass the exams successfully. Thus, Vasya was ready to celebrate, but, alas, he didn't pass it. However, many of Vasya's fellow students from the same group were more successful and celebrated after the exam.

Some of them celebrated in the BugDonalds restaurant, some of them — in the BeaverKing restaurant, the most successful ones were fast enough to celebrate in both of restaurants. Students which didn't pass the exam didn't celebrate in any of those restaurants and elected to stay home to prepare for their reexamination. However, this quickly bored Vasya and he started checking celebration photos on the Kilogramm. He found out that, in total, BugDonalds was visited by $A$ students, BeaverKing — by $B$ students and $C$ students visited both restaurants. Vasya also knows that there are $N$ students in his group.

Based on this info, Vasya wants to determine either if his data contradicts itself or, if it doesn't, how many students in his group didn't pass the exam. Can you help him so he won't waste his valuable preparation time?


-----Input-----

The first line contains four integers — $A$, $B$, $C$ and $N$ ($0 \leq A, B, C, N \leq 100$).


-----Output-----

If a distribution of $N$ students exists in which $A$ students visited BugDonalds, $B$ — BeaverKing, $C$ — both of the restaurants and at least one student is left home (it is known that Vasya didn't pass the exam and stayed at home), output one integer — amount of students (including Vasya) who did not pass the exam. 

If such a distribution does not exist and Vasya made a mistake while determining the numbers $A$, $B$, $C$ or $N$ (as in samples 2 and 3), output $-1$.


-----Examples-----
Input
10 10 5 20

Output
5
Input
2 2 0 4

Output
-1
Input
2 2 2 1

Output
-1


-----Note-----

The first sample describes following situation: $5$ only visited BugDonalds, $5$ students only visited BeaverKing, $5$ visited both of them and $5$ students (including Vasya) didn't pass the exam.

In the second sample $2$ students only visited BugDonalds and $2$ only visited BeaverKing, but that means all $4$ students in group passed the exam which contradicts the fact that Vasya didn't pass meaning that this situation is impossible.

The third sample describes a situation where $2$ students visited BugDonalds but the group has only $1$ which makes it clearly impossible.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given some positive integers, I wish to print the integers such that all take up the same width by adding a minimum number of leading zeroes. No leading zeroes shall be added to the largest integer.

For example, given `1, 23, 2, 17, 102`, I wish to print out these numbers as follows:

```python
001
023
002
017
102
```

Write a function `print_nums(n1, n2, n3, ...)` that takes a variable number of arguments and returns the string to be printed out.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a$ of $n$ integers, where $n$ is odd. You can make the following operation with it:  Choose one of the elements of the array (for example $a_i$) and increase it by $1$ (that is, replace it with $a_i + 1$). 

You want to make the median of the array the largest possible using at most $k$ operations.

The median of the odd-sized array is the middle element after the array is sorted in non-decreasing order. For example, the median of the array $[1, 5, 2, 3, 5]$ is $3$.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $n$ is odd, $1 \le k \le 10^9$) — the number of elements in the array and the largest number of operations you can make.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).


-----Output-----

Print a single integer — the maximum possible median after the operations.


-----Examples-----
Input
3 2
1 3 5

Output
5
Input
5 5
1 2 1 1 1

Output
3
Input
7 7
4 1 2 4 3 4 4

Output
5


-----Note-----

In the first example, you can increase the second element twice. Than array will be $[1, 5, 5]$ and it's median is $5$.

In the second example, it is optimal to increase the second number and than increase third and fifth. This way the answer is $3$.

In the third example, you can make four operations: increase first, fourth, sixth, seventh element. This way the array will be $[5, 1, 2, 5, 3, 5, 5]$ and the median will be $5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The objective is to return all pairs of integers from a given array of integers that have a difference of 2.

The result array should be sorted in ascending order of values.

Assume there are no duplicate integers in the array. The order of the integers in the input array should not matter.


## Examples
~~~if-not:python
```
[1, 2, 3, 4]  should return [[1, 3], [2, 4]]

[4, 1, 2, 3]  should also return [[1, 3], [2, 4]]

[1, 23, 3, 4, 7] should return [[1, 3]]

[4, 3, 1, 5, 6] should return [[1, 3], [3, 5], [4, 6]]
```
~~~
~~~if:python
```
[1, 2, 3, 4]  should return [(1, 3), (2, 4)]

[4, 1, 2, 3]  should also return [(1, 3), (2, 4)]

[1, 23, 3, 4, 7] should return [(1, 3)]

[4, 3, 1, 5, 6] should return [(1, 3), (3, 5), (4, 6)]
```
~~~

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

Write a function that takes an array of words and smashes them together into a sentence and returns the sentence. You can ignore any need to sanitize words or add punctuation, but you should add spaces between each word. **Be careful, there shouldn't be a space at the beginning or the end of the sentence!**

## Example

```
['hello', 'world', 'this', 'is', 'great']  =>  'hello world this is great'
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $N$ robots who work for $Y$ days and on each day they
produce some toys .on some days a few robots are given rest.
So depending on the availability of robots owner has 
made a time table which decides which robots will work on 
the particular day.
Only contiguous robots must be selected as they can form 
a link of communication among themselves.
Initially, all robots have the capacity of one toy.
On each day capacity for the chosen robot is updated i.e
capacity = capacity $+$$ ($minimum capacity of given range % $1000000007)$ .
After calculating the minimum capacity of a given range, compute
it as modulo 1000000007 ($10^9 + 7$).
After $Y$ days find the minimum capacity of the $N$ robots and compute it as modulo 1000000007 ($10^9 + 7$).   

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Next Line contains a single integer N.
- Next Line contains a single integer Y.
- Next $Y$ lines contains l and r range of chosen robots .

-----Output:-----
For each testcase, output in a single line answer , the minimum capacity of the $N$ robots after $Y$ days and compute it as modulo 1000000007 ($10^9 + 7$) .

-----Constraints-----
- $1 \leq T \leq 100$
- $100 \leq N \leq 10^4$
- $200 \leq Y \leq 1000$
- $0<=l , r<=N-1$  , $l<=r$

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

-----Sample Output:-----
4

-----EXPLANATION:-----
Initial capacity of the $5$ robots
1 1 1 1 1 
Minimum in range [0,3] = 1
Update the capacity in the range [0,3]
Now capacity becomes, 
Day 1 - 2 2 2 2 1
Similarly capacities changes for each day 
Day 2 - 2 4 4 2 1
Day 3 - 2 4 4 2 2
Day 4 - 4 6 6 4 4
so after 4 days minimum capacity is $4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya has a simple graph (that is, a graph without loops or multiple edges) consisting of n vertices and m edges.

The weight of the i-th vertex is a_i.

The weight of the i-th edge is w_i.

A subgraph of a graph is some set of the graph vertices and some set of the graph edges. The set of edges must meet the condition: both ends of each edge from the set must belong to the chosen set of vertices. 

The weight of a subgraph is the sum of the weights of its edges, minus the sum of the weights of its vertices. You need to find the maximum weight of subgraph of given graph. The given graph does not contain loops and multiple edges.

Input

The first line contains two numbers n and m (1 ≤ n ≤ 10^3, 0 ≤ m ≤ 10^3) - the number of vertices and edges in the graph, respectively.

The next line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) - the weights of the vertices of the graph.

The following m lines contain edges: the i-e edge is defined by a triple of integers v_i, u_i, w_i (1 ≤ v_i, u_i ≤ n, 1 ≤ w_i ≤ 10^9, v_i ≠ u_i). This triple means that between the vertices v_i and u_i there is an edge of weight w_i. It is guaranteed that the graph does not contain loops and multiple edges.

Output

Print one integer — the maximum weight of the subgraph of the given graph.

Examples

Input


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


Output


8


Input


3 3
9 7 8
1 2 1
2 3 2
1 3 3


Output


0

Note

In the first test example, the optimal subgraph consists of the vertices {1, 3, 4} and has weight 4 + 4 + 5 - (1 + 2 + 2) = 8. In the second test case, the optimal subgraph is empty.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An infinite army of ants is marching on an infinite 2-D plane. Since ants are disciplined, here's how they march: each ant chooses exactly one x coordinate and moves along it in positive y direction, starting from (x, 0). There exists exactly one ant for each x coordinate on that plane and hence there are infinite ants!

There are N horizontal barriers lying on this plane. The i^th barrier is defined by (xi, yi) and di, which means that the barrier is blocking all ants which want to pass through points lying on line segment connecting (xi, yi) and (xi + di, yi). Once an ant encounters a barrier, it stops moving.

Given all the barriers, your task is to find the total number of ants, that will be ever blocked at some point in their march.

INPUT

The first line contains an integer N which denotes the number of barriers. Next N lines follow, each contains 3 space separated integers,  "xi yi di" as explained in problem statement above.

Note: The barriers in the input may overlap.

OUTPUT

Output a single integer, the number of ants that will be ever blocked at some point in their march.

CONSTRAINTS

1 ≤ N ≤ 10^5
1 ≤ xi, yi, di ≤ 10^9

SAMPLE INPUT
2
1 1 4
7 3 5

SAMPLE OUTPUT
11

Explanation

Here 5 ants will be blocked on points (1,1) , (2, 1) , (3, 1), (4, 1) and (5, 1).

6 ants will be blocked on (7, 3), (8, 3), (9, 3), (10, 3), (11, 3), (12, 3).

In total, 11 ants are blocked in their journey.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vanya walks late at night along a straight street of length l, lit by n lanterns. Consider the coordinate system with the beginning of the street corresponding to the point 0, and its end corresponding to the point l. Then the i-th lantern is at the point ai. The lantern lights all points of the street that are at the distance of at most d from it, where d is some positive number, common for all lanterns. 

Vanya wonders: what is the minimum light radius d should the lanterns have to light the whole street?

Input

The first line contains two integers n, l (1 ≤ n ≤ 1000, 1 ≤ l ≤ 109) — the number of lanterns and the length of the street respectively. 

The next line contains n integers ai (0 ≤ ai ≤ l). Multiple lanterns can be located at the same point. The lanterns may be located at the ends of the street.

Output

Print the minimum light radius d, needed to light the whole street. The answer will be considered correct if its absolute or relative error doesn't exceed 10 - 9.

Examples

Input

7 15
15 5 3 7 9 14 0


Output

2.5000000000


Input

2 5
2 5


Output

2.0000000000

Note

Consider the second sample. At d = 2 the first lantern will light the segment [0, 4] of the street, and the second lantern will light segment [3, 5]. Thus, the whole street will be lit.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n parliamentarians in Berland. They are numbered with integers from 1 to n. It happened that all parliamentarians with odd indices are Democrats and all parliamentarians with even indices are Republicans.

New parliament assembly hall is a rectangle consisting of a × b chairs — a rows of b chairs each. Two chairs are considered neighbouring if they share as side. For example, chair number 5 in row number 2 is neighbouring to chairs number 4 and 6 in this row and chairs with number 5 in rows 1 and 3. Thus, chairs have four neighbours in general, except for the chairs on the border of the hall

We know that if two parliamentarians from one political party (that is two Democrats or two Republicans) seat nearby they spent all time discussing internal party issues.

Write the program that given the number of parliamentarians and the sizes of the hall determine if there is a way to find a seat for any parliamentarian, such that no two members of the same party share neighbouring seats.


-----Input-----

The first line of the input contains three integers n, a and b (1 ≤ n ≤ 10 000, 1 ≤ a, b ≤ 100) — the number of parliamentarians, the number of rows in the assembly hall and the number of seats in each row, respectively.


-----Output-----

If there is no way to assigns seats to parliamentarians in a proper way print -1.

Otherwise print the solution in a lines, each containing b integers. The j-th integer of the i-th line should be equal to the index of parliamentarian occupying this seat, or 0 if this seat should remain empty. If there are multiple possible solution, you may print any of them.


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

Output
0 3
1 2

Input
8 4 3

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

Input
10 2 2

Output
-1



-----Note-----

In the first sample there are many other possible solutions. For example, 3 2

0 1



and 2 1

3 0



The following assignment 3 2

1 0



is incorrect, because parliamentarians 1 and 3 are both from Democrats party but will occupy neighbouring seats.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The statement of this problem is the same as the statement of problem C2. The only difference is that, in problem C1, $n$ is always even, and in C2, $n$ is always odd.

You are given a regular polygon with $2 \cdot n$ vertices (it's convex and has equal sides and equal angles) and all its sides have length $1$. Let's name it as $2n$-gon.

Your task is to find the square of the minimum size such that you can embed $2n$-gon in the square. Embedding $2n$-gon in the square means that you need to place $2n$-gon in the square in such way that each point which lies inside or on a border of $2n$-gon should also lie inside or on a border of the square.

You can rotate $2n$-gon and/or the square.


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 200$) — the number of test cases.

Next $T$ lines contain descriptions of test cases — one per line. Each line contains single even integer $n$ ($2 \le n \le 200$). Don't forget you need to embed $2n$-gon, not an $n$-gon.


-----Output-----

Print $T$ real numbers — one per test case. For each test case, print the minimum length of a side of the square $2n$-gon can be embedded in. Your answer will be considered correct if its absolute or relative error doesn't exceed $10^{-6}$.


-----Example-----
Input
3
2
4
200

Output
1.000000000
2.414213562
127.321336469

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dr. Kay Em, a genius scientist, developed a new missile named "Ikan-no-i." This missile has N jet engines. When the i-th engine is ignited, the missile's velocity changes to (vxi, vyi) immediately.

Your task is to determine whether the missile can reach the given target point (X, Y ). The missile can be considered as a mass point in a two-dimensional plane with the y-axis pointing up, affected by the gravity of 9.8 downward (i.e. the negative y-direction) and initially set at the origin (0, 0). The engines can be ignited at any time in any order. Still, note that at least one of them needs to be ignited to get the missile launched.



Input

The input consists of multiple datasets. Each dataset has the following format.

N
vx1 vy1
vx2 vy2
...
vxN vyN
X Y


All values are integers and meet the following constraints: 1 ≤ N ≤ 1,000, 0 < vxi ≤ 1,000, -1,000 ≤ vyi ≤ 1,000, 0 < X ≤ 1,000, -1,000 ≤ Y ≤ 1,000.

The end of input is indicated by a line with a single zero.

Output

For each dataset, output whether the missile can reach the target point in a line: "Yes" if it can, "No" otherwise.

Example

Input

1
1 1
10 -480
2
6 7
5 5
4 1
3
10 5
4 4
8 4
2 0
0


Output

Yes
Yes
No

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