vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Martha — as a professional problemsetter — proposed a problem for a world-class contest. This is the problem statement:

Tomorrow is Nadia's birthday, and Bardia (her brother) is assigned to make the balloons ready!

There are n balloons (initially empty) that are tied to a straight line on certain positions x_1, x_2, ..., x_{n}. Bardia inflates the balloons from left to right. As a result, i-th balloon gets bigger and bigger until its radius reaches the pressure endurance p_{i} or it touches another previously-inflated balloon. [Image] 

While Bardia was busy with the balloons, he wondered "What will be the sum of radius of balloons after all of the balloons are inflated?". Being a nerdy type of guy, he is now thinking about the problem instead of preparing his sister's birthday. Calculate the answer to Bardia's problem so that Nadia's birthday won't be balloon-less.

Artha — Martha's student — claimed his solution got accepted. Martha (being his teacher for a long time!) knew he couldn't have solved the problem for real and thus thinks there is something wrong with the testcases. Artha isn't anyhow logical, which means there is no way for Martha to explain the wrong point in his algorithm. So, the only way is to find a testcase to prove him wrong!

Artha's pseudo-code is shown below: [Image] 

You should output a small testcase for the problem such that Artha's algorithm is incorrect. The algorithm's output is considered correct if it differs from the correct value by no more than 1.


-----Input-----

Please pay attention! No input will be given to your program for this problem. So you do not have to read from the input anything.


-----Output-----

You should output the generated small testcase (which Artha's solution doesn't get it right). It should be in the following format:  First line must contain the only number n (1 ≤ n ≤ 500).  The i-th of the next n lines should contain the description of the i-th balloon — two space-separated integers x_{i}, p_{i} (1 ≤ p_{i} ≤ 10^6, 0 ≤ x_1 < x_2 < ... < x_{n} ≤ 10^6). 


-----Examples-----


-----Note-----

The testcase depicted in the figure above (just showing how output should be formatted):

4

0 9

6 3

12 7

17 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Happy new year! The year 2020 is also known as Year Gyeongja (경자년, gyeongja-nyeon) in Korea. Where did the name come from? Let's briefly look at the Gapja system, which is traditionally used in Korea to name the years.

There are two sequences of $n$ strings $s_1, s_2, s_3, \ldots, s_{n}$ and $m$ strings $t_1, t_2, t_3, \ldots, t_{m}$. These strings contain only lowercase letters. There might be duplicates among these strings.

Let's call a concatenation of strings $x$ and $y$ as the string that is obtained by writing down strings $x$ and $y$ one right after another without changing the order. For example, the concatenation of the strings "code" and "forces" is the string "codeforces".

The year 1 has a name which is the concatenation of the two strings $s_1$ and $t_1$. When the year increases by one, we concatenate the next two strings in order from each of the respective sequences. If the string that is currently being used is at the end of its sequence, we go back to the first string in that sequence.

For example, if $n = 3, m = 4, s = ${"a", "b", "c"}, $t =$ {"d", "e", "f", "g"}, the following table denotes the resulting year names. Note that the names of the years may repeat. [Image] 

You are given two sequences of strings of size $n$ and $m$ and also $q$ queries. For each query, you will be given the current year. Could you find the name corresponding to the given year, according to the Gapja system?


-----Input-----

The first line contains two integers $n, m$ ($1 \le n, m \le 20$).

The next line contains $n$ strings $s_1, s_2, \ldots, s_{n}$. Each string contains only lowercase letters, and they are separated by spaces. The length of each string is at least $1$ and at most $10$.

The next line contains $m$ strings $t_1, t_2, \ldots, t_{m}$. Each string contains only lowercase letters, and they are separated by spaces. The length of each string is at least $1$ and at most $10$.

Among the given $n + m$ strings may be duplicates (that is, they are not necessarily all different).

The next line contains a single integer $q$ ($1 \le q \le 2\,020$).

In the next $q$ lines, an integer $y$ ($1 \le y \le 10^9$) is given, denoting the year we want to know the name for.


-----Output-----

Print $q$ lines. For each line, print the name of the year as per the rule described above.


-----Example-----
Input
10 12
sin im gye gap eul byeong jeong mu gi gyeong
yu sul hae ja chuk in myo jin sa o mi sin
14
1
2
3
4
10
11
12
13
73
2016
2017
2018
2019
2020

Output
sinyu
imsul
gyehae
gapja
gyeongo
sinmi
imsin
gyeyu
gyeyu
byeongsin
jeongyu
musul
gihae
gyeongja



-----Note-----

The first example denotes the actual names used in the Gapja system. These strings usually are either a number or the name of some animal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Of course our child likes walking in a zoo. The zoo has n areas, that are numbered from 1 to n. The i-th area contains ai animals in it. Also there are m roads in the zoo, and each road connects two distinct areas. Naturally the zoo is connected, so you can reach any area of the zoo from any other area using the roads.

Our child is very smart. Imagine the child want to go from area p to area q. Firstly he considers all the simple routes from p to q. For each route the child writes down the number, that is equal to the minimum number of animals among the route areas. Let's denote the largest of the written numbers as f(p, q). Finally, the child chooses one of the routes for which he writes down the value f(p, q).

After the child has visited the zoo, he thinks about the question: what is the average value of f(p, q) for all pairs p, q (p ≠ q)? Can you answer his question?

Input

The first line contains two integers n and m (2 ≤ n ≤ 105; 0 ≤ m ≤ 105). The second line contains n integers: a1, a2, ..., an (0 ≤ ai ≤ 105). Then follow m lines, each line contains two integers xi and yi (1 ≤ xi, yi ≤ n; xi ≠ yi), denoting the road between areas xi and yi.

All roads are bidirectional, each pair of areas is connected by at most one road.

Output

Output a real number — the value of <image>.

The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 4.

Examples

Input

4 3
10 20 30 40
1 3
2 3
4 3


Output

16.666667


Input

3 3
10 20 30
1 2
2 3
3 1


Output

13.333333


Input

7 8
40 20 10 30 20 50 40
1 2
2 3
3 4
4 5
5 6
6 7
1 4
5 7


Output

18.571429

Note

Consider the first sample. There are 12 possible situations:

  * p = 1, q = 3, f(p, q) = 10. 
  * p = 2, q = 3, f(p, q) = 20. 
  * p = 4, q = 3, f(p, q) = 30. 
  * p = 1, q = 2, f(p, q) = 10. 
  * p = 2, q = 4, f(p, q) = 20. 
  * p = 4, q = 1, f(p, q) = 10. 



Another 6 cases are symmetrical to the above. The average is <image>.

Consider the second sample. There are 6 possible situations:

  * p = 1, q = 2, f(p, q) = 10. 
  * p = 2, q = 3, f(p, q) = 20. 
  * p = 1, q = 3, f(p, q) = 10. 



Another 3 cases are symmetrical to the above. The average is <image>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find places where a R × C pattern is found within a H × W region. Print top-left coordinates (i, j) of sub-regions where the pattern found. The top-left and bottom-right coordinates of the region is (0, 0) and (H-1, W-1) respectively.

Constraints

* 1 ≤ H, W ≤ 1000
* 1 ≤ R, C ≤ 1000
* The input consists of alphabetical characters and digits

Input

In the first line, two integers H and W are given. In the following H lines, i-th lines of the region are given.

In the next line, two integers R and C are given. In the following R lines, i-th lines of the pattern are given.

Example

Input

4 5
00010
00101
00010
00100
3 2
10
01
10


Output

0 3
1 2

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 [Bengali] as well.

Recently, Chef's College Examination has concluded. He was enrolled in $3$ courses and he scored $A, B, C$ in them, respectively. To pass the semester, he must score at least $A_{min}, B_{min}, C_{min}$ marks in the respective subjects along with a cumulative score of at least $T_{min}$, i.e, $A + B + C ≥ T_{min}$.

Given seven integers $A_{min}, B_{min}, C_{min}, T_{min}, A, B, C$, tell whether Chef passes the semester or not.

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

The first line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contains of a single line of input, seven integers $A_{min}, B_{min}, C_{min}, T_{min}, A, B, C$ each separated by aspace.

------ Output: ------
Output in a single line, the answer, which should be "YES" if Chef passes the semester and "NO" if not.

You may print each character of the string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

------ Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ A_{min}, B_{min}, C_{min}, A, B, C ≤ 100$
$A_{min} + B_{min} + C_{min} ≤ T_{min} ≤ 300$

----- Sample Input 1 ------ 
5

1 1 1 300 2 2 2

3 2 2 6 2 2 2

2 3 2 6 2 2 2

2 2 3 6 2 2 2

100 100 100 300 100 100 100
----- Sample Output 1 ------ 
NO

NO

NO

NO

YES
----- explanation 1 ------ 
TestCase 1: Chef is passing in all the subjects individually but his total score ($2 + 2 + 2 = 6$) is much below the required threshold of $300$ marks. So Chef doesn't pass the semester.

TestCase 2: Chef's score in the first subject is less than the threshold, so he doesn't pass the semester.

TestCase 3: Chef's score in the second subject is less than the threshold, so he doesn't pass the semester.

TestCase 4: Chef's score in the third subject is less than the threshold, so he doesn't pass the semester.

TestCase 5: Chef is passing in all the subjects individually and also his total score is equal to the required threshold of $300$ marks. So Chef passes the semester.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bees are one of the most industrious insects. Since they collect nectar and pollen from flowers, they have to rely on the trees in the forest. For simplicity they numbered the $n$ trees from $0$ to $n - 1$. Instead of roaming around all over the forest, they use a particular list of paths. A path is based on two trees, and they can move either way i.e. from one tree to another in straight line. They don’t use paths that are not in their list.

As technology has been improved a lot, they also changed their working strategy. Instead of hovering over all the trees in the forest, they are targeting particular trees, mainly trees with lots of flowers. So, they planned that they will build some new hives in some targeted trees. After that they will only collect their foods from these trees. They will also remove some paths from their list so that they don’t have to go to a tree with no hive in it.

Now, they want to build the hives such that if one of the paths in their new list go down (some birds or animals disturbs them in that path) it’s still possible to go from any hive to another using the existing paths.

They don’t want to choose less than two trees and as hive-building requires a lot of work, they need to keep the number of hives as low as possible. Now you are given the trees with the paths they use, your task is to propose a new bee hive colony for them.

-----Input-----
The first line contains two integers $n$ ($2 \leq n \leq 500$) and $m$ ($0 \leq m \leq 20000$), where $n$ denotes the number of trees and $m$ denotes the number of paths. Each of the next $m$ lines contains two integers $u$ and $v$ ($0 \leq u, v < n, u \neq v$) meaning that there is a path between tree $u$ and $v$. Assume that there can be at most one path between tree $u$ to $v$, and needless to say that a path will not be given more than once in the input.

-----Output-----
Print the number of beehives in the proposed colony or ‘impossible’ if its impossible to find such a colony.

-----Note-----
The dataset is huge. Use fast I/O methods.

-----Examples-----
Sample Input 1:
3 3
0 1
1 2
2 0
Sample Output 1:
3

Sample Input 2:
2 1
0 1
Sample Output 2:
impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You received as a gift a very clever robot walking on a rectangular board. Unfortunately, you understood that it is broken and behaves rather strangely (randomly). The board consists of N rows and M columns of cells. The robot is initially at some cell on the i-th row and the j-th column. Then at every step the robot could go to some another cell. The aim is to go to the bottommost (N-th) row. The robot can stay at it's current cell, move to the left, move to the right, or move to the cell below the current. If the robot is in the leftmost column it cannot move to the left, and if it is in the rightmost column it cannot move to the right. At every step all possible moves are equally probable. Return the expected number of step to reach the bottommost row.

Input

On the first line you will be given two space separated integers N and M (1 ≤ N, M ≤ 1000). On the second line you will be given another two space separated integers i and j (1 ≤ i ≤ N, 1 ≤ j ≤ M) — the number of the initial row and the number of the initial column. Note that, (1, 1) is the upper left corner of the board and (N, M) is the bottom right corner.

Output

Output the expected number of steps on a line of itself with at least 4 digits after the decimal point.

Examples

Input

10 10
10 4


Output

0.0000000000


Input

10 14
5 14


Output

18.0038068653

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array containing only zeros and ones, find the index of the zero that, if converted to one, will make the longest sequence of ones.

For instance, given the array:

```
[1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1]
```

replacing the zero at index 10 (counting from 0) forms a sequence of 9 ones:

```
[1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1]
                  '------------^------------'
```


Your task is to complete the function that determines where to replace a zero with a one to make the maximum length subsequence.


**Notes:**
- If there are multiple results, return the last one:

 `[1, 1, 0, 1, 1, 0, 1, 1] ==> 5`


- The array will always contain only zeros and ones.


Can you do this in one pass?

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's tell you the legendary story of two famous kings William and Harold . Both were sworn enemies of each other & William want to conquer the Harold's city . But first William has to defeat Harold's army.

Harold has an army not a huge one but a tactical one. He has got teams in his army in the form of rectangular blocks, such that if any of them are left, William will lose the battle.

Each soldier has a rank in the army, and only a specified rectangular arrangement of them forms a tactical team. If any one of the soldiers in the team dies all the soldiers of that team die. You need to find them and kill them all .But William has limited resources and need to do this in minimum number of ammunition.

You need to find the number of missiles required to defeat Harold and kill all the tactical groups.
One missile will kill only one soldiers .

As we all know tactical team are costly so numbers of tactical team in Harold's army will be always less then equal to 100.

Input Format

2 Integers N and M denoting the dimensions of the army
Next N lines contains M integers each denoting the rank of the soldier
single integer Q denoting number of queries
each query consists
PN PM : Two Integer denoting the size of group
Next PN lines contain PM integers denoting the arrangement of the soldiers to form the tactical group

Output Format

print the minimum number of missiles to destroy all the tactical groups

Constraints:

1 ≤ N, M, PN, PM ≤ 1000
1 ≤ Q ≤ 10
1 ≤ rank ≤ 9

SAMPLE INPUT
4 4
1 2 5 3
2 5 3 3
5 3 1 1
6 8 1 7
2
2 2 
2 5
5 3
1 2
5 3

SAMPLE OUTPUT
1
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently, Duff has been practicing weight lifting. As a hard practice, Malek gave her a task. He gave her a sequence of weights. Weight of i-th of them is 2^{w}_{i} pounds. In each step, Duff can lift some of the remaining weights and throw them away. She does this until there's no more weight left. Malek asked her to minimize the number of steps. [Image] 

Duff is a competitive programming fan. That's why in each step, she can only lift and throw away a sequence of weights 2^{a}_1, ..., 2^{a}_{k} if and only if there exists a non-negative integer x such that 2^{a}_1 + 2^{a}_2 + ... + 2^{a}_{k} = 2^{x}, i. e. the sum of those numbers is a power of two.

Duff is a competitive programming fan, but not a programmer. That's why she asked for your help. Help her minimize the number of steps. 


-----Input-----

The first line of input contains integer n (1 ≤ n ≤ 10^6), the number of weights.

The second line contains n integers w_1, ..., w_{n} separated by spaces (0 ≤ w_{i} ≤ 10^6 for each 1 ≤ i ≤ n), the powers of two forming the weights values.


-----Output-----

Print the minimum number of steps in a single line.


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

Output
2

Input
4
0 1 2 3

Output
4



-----Note-----

In the first sample case: One optimal way would be to throw away the first three in the first step and the rest in the second step. Also, it's not possible to do it in one step because their sum is not a power of two.

In the second sample case: The only optimal way is to throw away one weight in each step. It's not possible to do it in less than 4 steps because there's no subset of weights with more than one weight and sum equal to a power of two.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three sticks with positive integer lengths of a, b, and c centimeters. You can increase length of some of them by some positive integer number of centimeters (different sticks can be increased by a different length), but in total by at most l centimeters. In particular, it is allowed not to increase the length of any stick.

Determine the number of ways to increase the lengths of some sticks so that you can form from them a non-degenerate (that is, having a positive area) triangle. Two ways are considered different, if the length of some stick is increased by different number of centimeters in them.


-----Input-----

The single line contains 4 integers a, b, c, l (1 ≤ a, b, c ≤ 3·10^5, 0 ≤ l ≤ 3·10^5).


-----Output-----

Print a single integer — the number of ways to increase the sizes of the sticks by the total of at most l centimeters, so that you can make a non-degenerate triangle from it.


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

Output
4

Input
1 2 3 1

Output
2

Input
10 2 1 7

Output
0



-----Note-----

In the first sample test you can either not increase any stick or increase any two sticks by 1 centimeter.

In the second sample test you can increase either the first or the second stick by one centimeter. Note that the triangle made from the initial sticks is degenerate and thus, doesn't meet the conditions.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are working for the Gryzzl company, headquartered in Pawnee, Indiana.

The new national park has been opened near Pawnee recently and you are to implement a geolocation system, so people won't get lost. The concept you developed is innovative and minimalistic. There will be n antennas located somewhere in the park. When someone would like to know their current location, their Gryzzl hologram phone will communicate with antennas and obtain distances from a user's current location to all antennas.

Knowing those distances and antennas locations it should be easy to recover a user's location... Right? Well, almost. The only issue is that there is no way to distinguish antennas, so you don't know, which distance corresponds to each antenna. Your task is to find a user's location given as little as all antennas location and an unordered multiset of distances.

Input

The first line of input contains a single integer n (2 ≤ n ≤ 10^5) which is the number of antennas.

The following n lines contain coordinates of antennas, i-th line contain two integers x_i and y_i (0 ≤ x_i,y_i ≤ 10^8). It is guaranteed that no two antennas coincide.

The next line of input contains integer m (1 ≤ n ⋅ m ≤ 10^5), which is the number of queries to determine the location of the user.

Following m lines contain n integers 0 ≤ d_1 ≤ d_2 ≤ ... ≤ d_n ≤ 2 ⋅ 10^{16} each. These integers form a multiset of squared distances from unknown user's location (x;y) to antennas.

For all test cases except the examples it is guaranteed that all user's locations (x;y) were chosen uniformly at random, independently from each other among all possible integer locations having 0 ≤ x, y ≤ 10^8.

Output

For each query output k, the number of possible a user's locations matching the given input and then output the list of these locations in lexicographic order.

It is guaranteed that the sum of all k over all points does not exceed 10^6.

Examples

Input


3
0 0
0 1
1 0
1
1 1 2


Output


1 1 1 


Input


4
0 0
0 1
1 0
1 1
2
0 1 1 2
2 5 5 8


Output


4 0 0 0 1 1 0 1 1 
4 -1 -1 -1 2 2 -1 2 2 

Note

As you see in the second example, although initially a user's location is picked to have non-negative coordinates, you have to output all possible integer locations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have an array $a$ of length $n$. You can exactly once select an integer $len$ between $1$ and $n - 1$ inclusively, and then sort in non-decreasing order the prefix of the array of length $len$ and the suffix of the array of length $n - len$ independently.

For example, if the array is $a = [3, 1, 4, 5, 2]$, and you choose $len = 2$, then after that the array will be equal to $[1, 3, 2, 4, 5]$.

Could it be that after performing this operation, the array will not be sorted in non-decreasing order?


-----Input-----

There are several test cases in the input data. The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer $n$ ($2 \leq n \leq 10^4$) — the length of the array.

The second line of the test case contains a sequence of integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the array elements.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.


-----Output-----

For each test case of input data, output "YES" (without quotes), if the array may be not sorted in non-decreasing order, output "NO" (without quotes) otherwise. You can output each letter in any case (uppercase or lowercase).


-----Examples-----

Input
3
3
2 2 1
4
3 1 2 1
5
1 2 2 4 4
Output
YES
YES
NO


-----Note-----

In the first test case, it's possible to select $len = 1$, then after operation, the array will not be sorted in non-decreasing order and will be equal to $[2, 1, 2]$.

In the second test case, it's possible to select $len = 3$, then after operation, the array will not be sorted in non-decreasing order and will be equal to $[1, 2, 3, 1]$.

In the third test case, the array will be sorted in non-decreasing order for every possible $len$.

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