Jai and Gopi are best friends. Both of them have a lot of girlfriends although they are nerds!!! One day one of Gopi’s girlfriends came to him and asked him to prove his love for her. Unfortunately Gopi has a meeting with another girlfriend and asks his best friend Jai to help him. Jai with an idea of increasing his girlfriend count accepts immediately. Jai on hearing the task finds it so simple and so asks his junior to complete the task which is you.

You are given a room of length L and breadth B which is divided into unit cells. In each unit cell there are some gems which amount to a certain value which can be positive, negative or even zero. You are asked to answer T queries. Each query consists of a number N and you need to collect gems from N unit cells such that the value of N unit cells when summed up must be maximum. The selection of N unit cells in a room of length L and breadth B must be in such a way that it must be a small room of length say some x and breadth some y provided x × y = N. If no such value for x and y exist then print -1.

Input

First line of input contains two space separated integers L and B which denotes the length and breadth of the room.

Following L lines contains B elements in each line each element specifying the value of the gems.

Next line contains T which is the number of queries.

Following T lines contains T elements where each element is the number N.

1 ≤ L, B ≤ 1000

All the L × B elements (x) will be in the range -100 ≤ x ≤ 100

1 ≤ T ≤ 10

1 ≤ N ≤ 10000

Output

Print the maximum value that can be obtained for each value of N.

Example

Input:
3 4
1 -2 3 -4
-5 6 -7 8
9 -10 11 -12
3
1
5
6

Output:
11
-1
4