Chef loves to play chess, so he bought a new chessboard with width M$M$ and height N$N$ recently.
Chef considers a chessboard correct if its width (number of columns) is equal to its height (number of rows) and each cell has no side-adjacent cell of the same color (this is the so-called "chess order" which you can see in real-world chessboards). Chef's chessboard does not have to be a correct chessboard (in particular, it may have N≠M$N \neq M$).
A sub-board of Chef's chessboard is a rectangular piece of this board with an arbitrarily chosen top left and bottom right cell (possibly equal to the original chessboard). Every sub-board is also a chessboard.
Chef can invert some cells; inverting a cell means changing its color from white to black or from black to white. After inverting those cells, he wants to cut the maximum correct sub-board out of the original chessboard.
Chef has not yet decided how many cells he would like to invert. Now he wonders about the answers to Q$Q$ question. In the i$i$-th question (1≤i≤Q$1 \le i \le Q$), he is allowed to invert at most ci$c_i$ cells (possibly zero); he would like to know the side length of the largest possible correct sub-board of his chessboard. Help Chef answer these questions.
-----Input-----
- The first line of the input contains two space-separated integers N$N$ and M$M$.
- N$N$ lines follow. For each valid i$i$, the i$i$-th of these lines contains a string with length M$M$ describing the i$i$-th row of Chef's chessboard. Each character of this string is either '0', representing a black cell, or '1', representing a white cell.
- The next line contains a single integer Q$Q$.
- The last line contains Q$Q$ space-separated integers c1,c2,…,cQ$c_1, c_2, \dots, c_Q$.
-----Output-----
For each question, print a single line containing one integer — the maximum size of a correct sub-board.
-----Constraints-----
- 1≤N,M≤200$1 \le N, M \le 200$
- 1≤Q≤105$1 \le Q \le 10^5$
- 0≤ci≤109$0 \le c_i \le 10^9$ for each valid i$i$
-----Subtasks-----
Subtask #1 (20 points):
- 1≤N,M≤20$1 \le N, M \le 20$
- 1≤Q≤100$1 \le Q \le 100$
Subtask #2 (30 points): 1≤N,M≤20$1 \le N, M \le 20$
Subtask #3 (50 points): original constraints
-----Example Input-----
8 8
00101010
00010101
10101010
01010101
10101010
01010101
10101010
01010101
4
1 2 0 1001
-----Example Output-----
7
8
6
8
-----Explanation-----
If we don't change the board, the best answer here is the 6x6 bottom right sub-board. We can invert cells (2,2)$(2, 2)$ and (1,1)$(1, 1)$ to get a better answer.
n,m = [int(i) for i in input().split()]
sqsets = list(range(2,min(n,m)+1))
ci = []
for i in range(n):
    ci.append(list(input()))
cc = [[0 for i in range(m+1)] for j in range(n+1)]
def cache_creation_part(x,y):
    cc[y][x] = cc[y][x - 1] + cc[y - 1][x] - cc[y - 1][x - 1]
    if (y + x) % 2 == 0:
        cc[y][x] += int(ci[y - 1][x - 1] != '1')
    else:
        cc[y][x] += int(ci[y - 1][x - 1] != '0')

def cache_creation(m,n):
    for y in range(1,n+1):
        for x in range(1, m + 1):
            cache_creation_part(x,y)

def operation(x,y,k):
    return cc[y + k][x + k] + cc[y][x] - cc[y + k][x] - cc[y][x + k]

c = 0
kd = {k:c for k in sqsets}
def kd_creation(m,n,sqsets):
    cache_creation(m,n)
    for k in sqsets:
        kd[k] = (10**9)+1
        for y in range(n-k+1):
            for x in range(m-k+1):
                cu = operation(x,y,k)
                kd[k] = min(kd[k], cu, k*k-cu)
kd_creation(m,n,sqsets)
del cc
del ci
del sqsets
tc = int(input())
tc = [int(x) for x in input().split()]
for u in tc:
    p = 0
    for i in kd:
        if kd[i] <= u:
            p = max(i, p)
    print(p)
n,m = [int(i) for i in input().split()]
sqsets = list(range(2,min(n,m)+1))
ci = []
for i in range(n):
    ci.append(list(input()))
cc = [[0 for i in range(m+1)] for j in range(n+1)]
def cache_creation_part(x,y):
    cc[y][x] = cc[y][x - 1] + cc[y - 1][x] - cc[y - 1][x - 1]
    if (y + x) % 2 == 0:
        cc[y][x] += int(ci[y - 1][x - 1] != '1')
    else:
        cc[y][x] += int(ci[y - 1][x - 1] != '0')

def cache_creation(m,n):
    for y in range(1,n+1):
        for x in range(1, m + 1):
            cache_creation_part(x,y)

def operation(x,y,k):
    return cc[y + k][x + k] + cc[y][x] - cc[y + k][x] - cc[y][x + k]

c = 0
kd = {k:c for k in sqsets}
def kd_creation(m,n,sqsets):
    cache_creation(m,n)
    for k in sqsets:
        kd[k] = (10**9)+1
        for y in range(n-k+1):
            for x in range(m-k+1):
                cu = operation(x,y,k)
                kd[k] = min(kd[k], cu, k*k-cu)
kd_creation(m,n,sqsets)
del cc
del ci
del sqsets
tc = int(input())
tc = [int(x) for x in input().split()]
for u in tc:
    p = 0
    for i in kd:
        if kd[i] <= u:
            p = max(i, p)
    print(p)