One of the recommendations made this year was for

to make a pre-recorded opening speech for the DMPG that would be played at the satellite sites.To achieve this, ~~fooling around with~~ learning about the camera's features, he realized that he accidentally messed up the camera's exposure correction! Panicking, he recalls what she taught him about exposure:

A photo can be represented as a grid of by pixels, and the pixel in row and column has a brightness , which can be any real number from to inclusive. If you average the brightnesses of all the pixels in a typical image, the result is called the

proper exposure.Most digital cameras have an exposure correction feature. By choosing a correction constant and multiplying all the pixel brightnesses in an image by , a darker or brighter image can be obtained.

When applying a correction constant, if any pixel brightnesses become greater than 1, those values are "clipped" and reduced to 1.

Armed with this knowledge, Kirito knows that to re-calibrate the camera, he has to answer queries:

What is the correction constant necessary for the proper exposure of this image to be ?

Since he would prefer not to work with floating-point numbers, for each query , he would like to know the **smallest integer such that applying the correction constant to the image results in a proper exposure greater than or equal to .**

#### Constraints

##### Subtask 1 [10%]

##### Subtask 2 [90%]

#### Input Specification

The first line of input will contain space separated integers, and .

The next lines will each contain space-separated integers, the pixel brightnesses **multiplied by **.

This will be followed by a single integer, .

The next integers will each contain a single integer, **multiplied by **.

#### Output Specification

lines, where the th line contains the smallest possible that will result in a proper exposure greater than or equal to .

#### Sample Input 1

```
2 3
360000 304000 120000
408000 312000 960000
1
480000
```

#### Sample Output 1

`1250000`

#### Sample Input 2

```
2 3
480000 580000 560000
380000 400000 480000
3
120000
480000
360000
```

#### Sample Output 2

```
250000
1000000
750000
```

## Comments