vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There are $n$ people who want to participate in a boat competition. The weight of the $i$-th participant is $w_i$. Only teams consisting of two people can participate in this competition. As an organizer, you think that it's fair to allow only teams with the same total weight.

So, if there are $k$ teams $(a_1, b_1)$, $(a_2, b_2)$, $\dots$, $(a_k, b_k)$, where $a_i$ is the weight of the first participant of the $i$-th team and $b_i$ is the weight of the second participant of the $i$-th team, then the condition $a_1 + b_1 = a_2 + b_2 = \dots = a_k + b_k = s$, where $s$ is the total weight of each team, should be satisfied.

Your task is to choose such $s$ that the number of teams people can create is the maximum possible. Note that each participant can be in no more than one team.

You have to answer $t$ independent test cases.


-----Input-----

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

The first line of the test case contains one integer $n$ ($1 \le n \le 50$) — the number of participants. The second line of the test case contains $n$ integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le n$), where $w_i$ is the weight of the $i$-th participant.


-----Output-----

For each test case, print one integer $k$: the maximum number of teams people can compose with the total weight $s$, if you choose $s$ optimally.


-----Example-----
Input
5
5
1 2 3 4 5
8
6 6 6 6 6 6 8 8
8
1 2 2 1 2 1 1 2
3
1 3 3
6
1 1 3 4 2 2

Output
2
3
4
1
2



-----Note-----

In the first test case of the example, we can reach the optimal answer for $s=6$. Then the first boat is used by participants $1$ and $5$ and the second boat is used by participants $2$ and $4$ (indices are the same as weights).

In the second test case of the example, we can reach the optimal answer for $s=12$. Then first $6$ participants can form $3$ pairs.

In the third test case of the example, we can reach the optimal answer for $s=3$. The answer is $4$ because we have $4$ participants with weight $1$ and $4$ participants with weight $2$.

In the fourth test case of the example, we can reach the optimal answer for $s=4$ or $s=6$.

In the fifth test case of the example, we can reach the optimal answer for $s=3$. Note that participant with weight $3$ can't use the boat because there is no suitable pair for him in the list.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The term of this problem is the same as the previous one, the only exception — increased restrictions.


-----Input-----

The first line contains two positive integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 10^9) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where the i-th number is equal to the number of grams of the i-th ingredient, needed to bake one cookie.

The third line contains the sequence b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 10^9), where the i-th number is equal to the number of grams of the i-th ingredient, which Apollinaria has.


-----Output-----

Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.


-----Examples-----
Input
1 1000000000
1
1000000000

Output
2000000000

Input
10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1

Output
0

Input
3 1
2 1 4
11 3 16

Output
4

Input
4 3
4 3 5 6
11 12 14 20

Output
3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
INTERCAL is the oldest of esoteric programming languages. One of its many weird features is the method of character-based output, known as Turing Tape method. It converts an array of unsigned 8-bit integers into a sequence of characters to print, using the following method.

The integers of the array are processed one by one, starting from the first. Processing *i*-th element of the array is done in three steps:

1. The 8-bit binary notation of the ASCII-code of the previous printed character is reversed. When the first element of the array is processed, the result of this step is considered to be 0.

2. The *i*-th element of the array is subtracted from the result of the previous step modulo 256.

3. The binary notation of the result of the previous step is reversed again to produce ASCII-code of the *i*-th character to be printed.

You are given the text printed using this method. Restore the array used to produce this text.

Input Specification:
The input will consist of a single line *text* which contains the message printed using the described method. String *text* will contain between 1 and 100 characters, inclusive. ASCII-code of each character of *text* will be between 32 (space) and 126 (tilde), inclusive.

Output Specification:
Output the initial array, which was used to produce *text*, one integer per line.

Demo Input:
['Hello, World!\n']

Demo Output:
['238\n108\n112\n0\n64\n194\n48\n26\n244\n168\n24\n16\n162\n']

Note:
Let's have a closer look at the beginning of the example. The first character is "H" with ASCII-code 72 = 01001000<sub class="lower-index">2</sub>. Its reverse is 00010010<sub class="lower-index">2</sub> = 18, and this number should become the result of the second step of processing. The result of the first step is considered to be 0, so the first element of the array has to be (0 - 18) mod 256 = 238, where *a* mod *b* is the remainder of division of *a* by *b*.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Masha really loves algebra. On the last lesson, her strict teacher Dvastan gave she new exercise.

You are given geometric progression b defined by two integers b_1 and q. Remind that a geometric progression is a sequence of integers b_1, b_2, b_3, ..., where for each i > 1 the respective term satisfies the condition b_{i} = b_{i} - 1·q, where q is called the common ratio of the progression. Progressions in Uzhlyandia are unusual: both b_1 and q can equal 0. Also, Dvastan gave Masha m "bad" integers a_1, a_2, ..., a_{m}, and an integer l.

Masha writes all progression terms one by one onto the board (including repetitive) while condition |b_{i}| ≤ l is satisfied (|x| means absolute value of x). There is an exception: if a term equals one of the "bad" integers, Masha skips it (doesn't write onto the board) and moves forward to the next term.

But the lesson is going to end soon, so Masha has to calculate how many integers will be written on the board. In order not to get into depression, Masha asked you for help: help her calculate how many numbers she will write, or print "inf" in case she needs to write infinitely many integers.


-----Input-----

The first line of input contains four integers b_1, q, l, m (-10^9 ≤ b_1, q ≤ 10^9, 1 ≤ l ≤ 10^9, 1 ≤ m ≤ 10^5) — the initial term and the common ratio of progression, absolute value of maximal number that can be written on the board and the number of "bad" integers, respectively.

The second line contains m distinct integers a_1, a_2, ..., a_{m} (-10^9 ≤ a_{i} ≤ 10^9) — numbers that will never be written on the board.


-----Output-----

Print the only integer, meaning the number of progression terms that will be written on the board if it is finite, or "inf" (without quotes) otherwise.


-----Examples-----
Input
3 2 30 4
6 14 25 48

Output
3
Input
123 1 2143435 4
123 11 -5453 141245

Output
0
Input
123 1 2143435 4
54343 -13 6 124

Output
inf


-----Note-----

In the first sample case, Masha will write integers 3, 12, 24. Progression term 6 will be skipped because it is a "bad" integer. Terms bigger than 24 won't be written because they exceed l by absolute value.

In the second case, Masha won't write any number because all terms are equal 123 and this is a "bad" integer.

In the third case, Masha will write infinitely integers 123.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
[3R2 - Standby for Action](https://www.youtube.com/watch?v=P2ZVC9aoiKo)

Our dear Cafe's owner, JOE Miller, will soon take part in a new game TV-show "1 vs. n"!

The game goes in rounds, where in each round the host asks JOE and his opponents a common question. All participants failing to answer are eliminated. The show ends when only JOE remains (we assume that JOE never answers a question wrong!).

For each question JOE answers, if there are s (s > 0) opponents remaining and t (0 ≤ t ≤ s) of them make a mistake on it, JOE receives \displaystylet/s dollars, and consequently there will be s - t opponents left for the next question.

JOE wonders what is the maximum possible reward he can receive in the best possible scenario. Yet he has little time before show starts, so can you help him answering it instead?

Input

The first and single line contains a single integer n (1 ≤ n ≤ 10^5), denoting the number of JOE's opponents in the show.

Output

Print a number denoting the maximum prize (in dollars) JOE could have.

Your answer will be considered correct if it's absolute or relative error won't exceed 10^{-4}. In other words, if your answer is a and the jury answer is b, then it must hold that (|a - b|)/(max(1, b)) ≤ 10^{-4}.

Examples

Input


1


Output


1.000000000000


Input


2


Output


1.500000000000

Note

In the second example, the best scenario would be: one contestant fails at the first question, the other fails at the next one. The total reward will be \displaystyle 1/2 + 1/1 = 1.5 dollars.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Convergents of e
The square root of 2 can be written as an infinite continued fraction.
![img](http://img0.ph.126.net/x1Hyc4iHQg0Jz2EInmT3ag==/6597639313681841979.png)  
The infinite continued fraction can be written, √2 = [1;(2)], (2) indicates that 2 repeats ad infinitum. In a similar way, √23 = [4;(1,3,1,8)].

It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for √2.
![img](http://img1.ph.126.net/xme9gNBQdA7bvQkwIftznQ==/6597819633588793645.png)  
Hence the sequence of the first ten convergents for √2 are:

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, …

What is most surprising is that the important mathematical constant,
e = [2; 1,2,1, 1,4,1, 1,6,1 , … , 1,2k,1, …].

The first ten terms in the sequence of convergents for e are:

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, …

The sum of digits in the numerator of the 10th convergent is 1+4+5+7=17.

Find the sum of digits in the numerator of the mth convergent of the continued fraction for e.


- Powered by [Project Euler](https://projecteuler.net/problem=65)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Blake is a CEO of a large company called "Blake Technologies". He loves his company very much and he thinks that his company should be the best. That is why every candidate needs to pass through the interview that consists of the following problem.

We define function f(x, l, r) as a bitwise OR of integers x_{l}, x_{l} + 1, ..., x_{r}, where x_{i} is the i-th element of the array x. You are given two arrays a and b of length n. You need to determine the maximum value of sum f(a, l, r) + f(b, l, r) among all possible 1 ≤ l ≤ r ≤ n. [Image] 


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the length of the arrays.

The second line contains n integers a_{i} (0 ≤ a_{i} ≤ 10^9).

The third line contains n integers b_{i} (0 ≤ b_{i} ≤ 10^9).


-----Output-----

Print a single integer — the maximum value of sum f(a, l, r) + f(b, l, r) among all possible 1 ≤ l ≤ r ≤ n.


-----Examples-----
Input
5
1 2 4 3 2
2 3 3 12 1

Output
22
Input
10
13 2 7 11 8 4 9 8 5 1
5 7 18 9 2 3 0 11 8 6

Output
46


-----Note-----

Bitwise OR of two non-negative integers a and b is the number c = a OR b, such that each of its digits in binary notation is 1 if and only if at least one of a or b have 1 in the corresponding position in binary notation.

In the first sample, one of the optimal answers is l = 2 and r = 4, because f(a, 2, 4) + f(b, 2, 4) = (2 OR 4 OR 3) + (3 OR 3 OR 12) = 7 + 15 = 22. Other ways to get maximum value is to choose l = 1 and r = 4, l = 1 and r = 5, l = 2 and r = 4, l = 2 and r = 5, l = 3 and r = 4, or l = 3 and r = 5.

In the second sample, the maximum value is obtained for l = 1 and r = 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
PowerShell had N natural numbers. He wanted to test Xenny's speed in finding the sum and difference of several numbers.

He decided to ask Xenny several questions. In each question, he gave him two positive integers L and R. He asked him to find the sum of all integers from index L to index R (inclusive) and the difference of all integers from index R to index L (inclusive).

(Numbers are 1-indexed) 

He asked Xenny Q such questions.

Your task is to report the answer that Xenny gave to each of the Q questions.

Input Format:

First line contains 2 space-separated integers - N and Q.

Second line contains N space-separated natural numbers.

Q lines follow - each line contains 2 space-separated postiive integers L and R.

Output Format:

Output Q lines - the answer to each question.

Each line should contain 2 space-separated integers - the required sum and difference.

Constraints:

1 ≤ N ≤ 10^6

1 ≤ L ≤ R ≤ 10^6

1 ≤ Q ≤ 10^5

-1000000 ≤ Numbers ≤ 1000000

SAMPLE INPUT
4 1
1 2 3 4
1 3

SAMPLE OUTPUT
6 0

Explanation

1 + 2 + 3 = 6

3 - 2 - 1 = 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is the easy version of the problem. The only difference is that in this version q = 1. You can make hacks only if both versions of the problem are solved.

There is a process that takes place on arrays a and b of length n and length n-1 respectively. 

The process is an infinite sequence of operations. Each operation is as follows: 

  * First, choose a random integer i (1 ≤ i ≤ n-1). 
  * Then, simultaneously set a_i = min\left(a_i, \frac{a_i+a_{i+1}-b_i}{2}\right) and a_{i+1} = max\left(a_{i+1}, \frac{a_i+a_{i+1}+b_i}{2}\right) without any rounding (so values may become non-integer). 

See notes for an example of an operation.

It can be proven that array a converges, i. e. for each i there exists a limit a_i converges to. Let function F(a, b) return the value a_1 converges to after a process on a and b.

You are given array b, but not array a. However, you are given a third array c. Array a is good if it contains only integers and satisfies 0 ≤ a_i ≤ c_i for 1 ≤ i ≤ n.

Your task is to count the number of good arrays a where F(a, b) ≥ x for q values of x. Since the number of arrays can be very large, print it modulo 10^9+7.

Input

The first line contains a single integer n (2 ≤ n ≤ 100).

The second line contains n integers c_1, c_2 …, c_n (0 ≤ c_i ≤ 100).

The third line contains n-1 integers b_1, b_2, …, b_{n-1} (0 ≤ b_i ≤ 100).

The fourth line contains a single integer q (q=1).

The fifth line contains q space separated integers x_1, x_2, …, x_q (-10^5 ≤ x_i ≤ 10^5).

Output

Output q integers, where the i-th integer is the answer to the i-th query, i. e. the number of good arrays a where F(a, b) ≥ x_i modulo 10^9+7.

Example

Input


3
2 3 4
2 1
1
-1


Output


56

Note

The following explanation assumes b = [2, 1] and c=[2, 3, 4] (as in the sample).

Examples of arrays a that are not good: 

  * a = [3, 2, 3] is not good because a_1 > c_1; 
  * a = [0, -1, 3] is not good because a_2 < 0. 



One possible good array a is [0, 2, 4]. We can show that no operation has any effect on this array, so F(a, b) = a_1 = 0.

Another possible good array a is [0, 1, 4]. In a single operation with i = 1, we set a_1 = min((0+1-2)/(2), 0) and a_2 = max((0+1+2)/(2), 1). So, after a single operation with i = 1, a becomes equal to [-1/2, 3/2, 4]. We can show that no operation has any effect on this array, so F(a, b) = -1/2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A close friend of yours, a duck with financial problems, has requested your help with a matter that will help him pay off his debts. He is the nephew of an extremely wealthy duck, who has a large vault, filled with mountains of coins. This wealthy duck has a certain coin in his possession which has a lot of sentimental value to him. Usually, it is kept under a protective glass dome on a velvet cushion.

However, during a recent relocating of the coins in the vault, the special coin was accidentally moved into the vault, leading to an extremely stressful situation for your friend’s uncle. Luckily, the coin has recently been located. Unfortunately, it is completely opposite to the entrance to the vault, and due to the mountains of coins inside the vault, actually reaching the coin is no simple task.

He is therefore willing to pay your friend to retrieve this coin, provided that he brings his own equipment to scale the mountains of coins. Your friend has decided he will bring a ladder, but he is still uncertain about its length. While a longer ladder means that he can scale higher cliffs, it also costs more money. He therefore wants to buy the shortest ladder such that he can reach the special coin, so that he has the largest amount of money left to pay off his debts.

The vault can be represented as a rectangular grid of stacks of coins of various heights (in meters), with the entrance at the north west corner (the first height in the input, the entrance to the vault is at this height as well) and the special coin at the south east corner (the last height in the input). Your avian companion has figured out the height of the coins in each of these squares. From a stack of coins he can attempt to climb up or jump down to the stack immediately north, west, south or east of it. Because your friend cannot jump or fly (he is a very special kind of duck that even wears clothes), successfully performing a climb of $n$ meters will require him to bring a ladder of at least $n$ meters. He does not mind jumping down, no matter the height; he just lets gravity do all the work.

-----Input-----
The first line contains two integers: the length $M$, and the width $N$ of the vault, satisfying $1 \leq M,N \leq 1000$.

The following $M$ lines each contain $N$ integers. Each integer specifies the height of the pile of coins in the vault at the corresponding position. (The first line describes the north-most stacks from west to east; the last line describes the south-most stacks from west to east). The heights are given in meters and all heights are at least $0$ and at most $10^9$ (yes, your friend’s uncle is very rich).

-----Output-----
Output a single line containing a single integer: the length in meters of the shortest ladder that allows you to get from the north west corner to the south east corner.

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

Sample Input 2:
1 4
4 3 2 1
Sample Output 2:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three piles of casino chips: white, green and black chips:

* the first pile contains only white chips
* the second pile contains only green chips
* the third pile contains only black chips

Each day you take exactly two chips of different colors and head to the casino. You can choose any color, but you are not allowed to take two chips of the same color in a day.

You will be given an array representing the number of chips of each color and your task is to return the maximum number of days you can pick the chips. Each day you need to take exactly two chips.

```python 
solve([1,1,1]) = 1, because after you pick on day one, there will be only one chip left
solve([1,2,1] = 2, you can pick twice; you pick two chips on day one then on day two
solve([4,1,1]) = 2
```

```javascript 
solve([1,1,1]) = 1, because after you pick on day one, there will be only one chip left
solve([1,2,1]) = 2, you can pick twice; you pick two chips on day one then on day two
solve([4,1,1]) = 2
```

```go 
solve([1,1,1]) = 1, because after you pick on day one, there will be only one chip left
solve([1,2,1]) = 2, you can pick twice; you pick two chips on day one then on day two
solve([4,1,1]) = 2
```


```ruby 
solve([1,1,1]) = 1, because after you pick on day one, there will be only one chip left
solve([1,2,1]) = 2, you can pick twice; you pick two chips on day, two chips on day two
solve([4,1,1]) = 2
```

More examples in the test cases. Good luck!

Brute force is not the way to go here. Look for a simplifying mathematical approach.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A string is called bracket sequence if it does not contain any characters other than "(" and ")". A bracket sequence is called regular if it it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, "", "(())" and "()()" are regular bracket sequences; "))" and ")((" are bracket sequences (but not regular ones), and "(a)" and "(1)+(1)" are not bracket sequences at all.

You have a number of strings; each string is a bracket sequence of length $2$. So, overall you have $cnt_1$ strings "((", $cnt_2$ strings "()", $cnt_3$ strings ")(" and $cnt_4$ strings "))". You want to write all these strings in some order, one after another; after that, you will get a long bracket sequence of length $2(cnt_1 + cnt_2 + cnt_3 + cnt_4)$. You wonder: is it possible to choose some order of the strings you have such that you will get a regular bracket sequence? Note that you may not remove any characters or strings, and you may not add anything either.


-----Input-----

The input consists of four lines, $i$-th of them contains one integer $cnt_i$ ($0 \le cnt_i \le 10^9$).


-----Output-----

Print one integer: $1$ if it is possible to form a regular bracket sequence by choosing the correct order of the given strings, $0$ otherwise.


-----Examples-----
Input
3
1
4
3

Output
1

Input
0
0
0
0

Output
1

Input
1
2
3
4

Output
0



-----Note-----

In the first example it is possible to construct a string "(())()(()((()()()())))", which is a regular bracket sequence.

In the second example it is possible to construct a string "", which is a regular bracket sequence.

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