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.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
n,m=map(int,input().split())
L=[]
for i in range(n):
    s=input()
    L.append(s)

cost=[]
h2=[0]*(m+1)
cost.append(h2)
for i in range(n):
    h=[0]
    for j in range(m):
        if(L[i][j]=='0' and (i+j)%2!=0):
            h.append(1)
        elif(L[i][j]=='1' and (i+j)%2==0):
            h.append(1)
        else:
            h.append(0)
    cost.append(h)

pre=[]
h2=[0]*(m+1)
pre.append(h2)
for i in range(1,n+1):
    h=[0]
    c=0
    for j in range(1,m+1):
        c+=cost[i][j]
        c2=c
        if(i>0):
            c2+=pre[i-1][j]
        h.append(c2)
    pre.append(h)

bs=[0]*((m*n)+10)

for i in range(1,n+1):
    for j in range(1,m+1):
        for k in range(1,min(m,n)+1):
            if(i-k>=0 and j-k>=0):
                c=pre[i][j]-pre[i-k][j]-pre[i][j-k]+pre[i-k][j-k]
                c=min(c,(k*k)-c)
                bs[c]=max(bs[c],k)

mx=bs[0]
for i in range(1,len(bs)):
    mx=max(mx,bs[i])
    bs[i]=mx

Q=int(input())
q=[int(x) for x in input().split()]
for i in range(0,len(q)):
    qr=min(m*n,q[i])
    print(bs[qr])




n,m=map(int,input().split())
L=[]
for i in range(n):
    s=input()
    L.append(s)

cost=[]
h2=[0]*(m+1)
cost.append(h2)
for i in range(n):
    h=[0]
    for j in range(m):
        if(L[i][j]=='0' and (i+j)%2!=0):
            h.append(1)
        elif(L[i][j]=='1' and (i+j)%2==0):
            h.append(1)
        else:
            h.append(0)
    cost.append(h)

pre=[]
h2=[0]*(m+1)
pre.append(h2)
for i in range(1,n+1):
    h=[0]
    c=0
    for j in range(1,m+1):
        c+=cost[i][j]
        c2=c
        if(i>0):
            c2+=pre[i-1][j]
        h.append(c2)
    pre.append(h)

bs=[0]*((m*n)+10)

for i in range(1,n+1):
    for j in range(1,m+1):
        for k in range(1,min(m,n)+1):
            if(i-k>=0 and j-k>=0):
                c=pre[i][j]-pre[i-k][j]-pre[i][j-k]+pre[i-k][j-k]
                c=min(c,(k*k)-c)
                bs[c]=max(bs[c],k)

mx=bs[0]
for i in range(1,len(bs)):
    mx=max(mx,bs[i])
    bs[i]=mx

Q=int(input())
q=[int(x) for x in input().split()]
for i in range(0,len(q)):
    qr=min(m*n,q[i])
    print(bs[qr])




n,m=map(int,input().split())
chess=[]
for _ in range(n):
    chess.append([int(x) for x in list(input())])
chessO=[]
chessL=[]
fixO=[]
fixL=[]
for _ in range(n):
    p=[0]*m
    fixL.append(p)
    q=[0]*m
    fixO.append(q)
    tm=[0]*m
    chessO.append(tm)
    to=[0]*m
    chessL.append(to)

for i in range(n):
    for j in range(m):
        chessO[i][j]=((i+j)%2)^chess[i][j]
        chessL[i][j]=((i+j+1)%2)^chess[i][j]
        fixO[i][j]=chessO[i][j]
        fixL[i][j]=chessL[i][j]

for i in range(n):
    for j in range(1,m):
        fixO[i][j]=fixO[i][j-1]+chessO[i][j]
        fixL[i][j]=fixL[i][j-1]+chessL[i][j]

ans=[-1]*min(m,n)
for i in range(n):
    for j in range(m):
        for k in range(min(n-i,m-j)):
            errorO,errorL=0,0
            for l in range(i,i+k+1):
                errorO+=fixO[l][j+k]-fixO[l][j]+chessO[l][j]
                errorL+=fixL[l][j+k]-fixL[l][j]+chessL[l][j]
            if ans[k]==-1 or ans[k]>min(errorO,errorL): ans[k]=min(errorO,errorL)
final=[0]*50000
maxo=9999999999
for i in range(min(m,n)-1,-1,-1):
    if ans[i]!=-1 and ans[i]<maxo:
        maxo=ans[i]
        final[maxo]=i
tmp=final[0]
for i in range(1,50000):
    if  final[i]>tmp:
        tmp=final[i]
    final[i]=tmp
input()
q=[int(x) for x in input().split()]

for x in q:
    if x>50000-2 : print(final[45000]+1)
    else: print(final[x]+1)
    


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)

# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2018/10/30 19:45

"""


N, M = map(int, input().split())

A = []

for i in range(N):
    A.append([int(x) for x in input()])

# for row in A:
#     print(row)


#f(r, c, color, width) = f(r+1, c+1, color, width-1) + mismatches_in_edge

mxMN, mnMN = max(M, N), min(M, N)
ans = [float('inf') for _ in range(mxMN + 1)]
f = [[[[0 for _ in range(mxMN + 1)] for color in range(2)] for c in range(M+1)] for r in range(N+1)]

for width in range(1, min(N, N)+1):
    for color in [0, 1]:
        for sr in range(N-width+1):
            for sc in range(N-width+1):
                steps = f[sr+1][sc+1][color][width-1]

                cc = color
                for c in range(sc, sc+width):
                    steps += 0 if A[sr][c] == cc else 1
                    cc ^= 1
                cc = color ^ 1
                for r in range(sr+1, sr+width):
                    steps += 0 if A[r][sc] == cc else 1
                    cc ^= 1

                f[sr][sc][color][width] = steps
                ans[width] = min(ans[width], steps)

qc = input()
qs = [int(x) for x in input().split()]

# print()
# print(ans)
for q in qs:
    print(bisect.bisect_right(ans, q) - 1)



n,m=list(map(int,input().split()))
grid=[ list(map(int,list(input()))) for i in range(n)]
obs0=[ [ 0 for j in range(m)] for i in range(n)] 
obs1=[ [ 0 for j in range(m)] for i in range(n) ]
max_side=min(m,n)
side_c=[ 40000 for i in range(max_side+1)]
side_c[0]=0
side_c[1]=0
#print(grid)
for i in range(n):
	for j in range(m):
		if (i+j)%2==0:
			obs0[i][j]=0
			obs1[i][j]=1
		else:
			obs0[i][j]=1
			obs1[i][j]=0
#print(obs0)
#print(obs1)
for i in range(n):
	for j in range(m):
		if obs0[i][j]!=grid[i][j]:
			obs0[i][j]=1
		else:
			obs0[i][j]=0
		if obs1[i][j]!=grid[i][j]:
			obs1[i][j]=1
		else:
			obs1[i][j]=0
#print(obs0)
#print(obs1)

for i in range(n):
	for j in range(1,m):
		obs0[i][j]+=obs0[i][j-1]
		obs1[i][j]+=obs1[i][j-1]
for j in range(m):
	for i in  range(1,n):
		obs0[i][j]+=obs0[i-1][j]
		obs1[i][j]+=obs1[i-1][j]
for side in range(2,max_side+1):
	for i in range(n):
		for j in range(m):
			if i+side>n or j+side>m:
				continue
			count0 = obs0[i+side-1][j+side-1] + (i!=0 and j!=0)*obs0[i-1][j-1] -(j!=0)*obs0[i+side-1][j-1] -(i!=0)*obs0[i-1][j+side-1] 
			count1 = obs1[i+side-1][j+side-1] + (i!=0 and j!=0)*obs1[i-1][j-1] -(j!=0)*obs1[i+side-1][j-1] -(i!=0)*obs1[i-1][j+side-1]
			side_c[side]=min(count0,count1,side_c[side])
input()
#print(side_c)
#print(*obs0,sep="\n")
#print(*obs1,sep="\n")
list_c=list(map(int,input().split()))
for i in range(len(list_c)):
	c=list_c[i]
	answer=1
	for side in range(2,max_side+1):
		if c<side_c[side]:
			answer=side-1
			break
	if c>=side_c[max_side]:
		answer=max_side
	print(answer)





n,m=map(int,input().split())
b=[[int(x) for x in list(input())] for x in range(n)]
c=int(input())

size=min(n,m)
res=[size**2 for x in range(size+1)]

def invert(i,j,r,ele):
    count=0
    
    for index,x in enumerate(range(i,i+r)):
        temp=ele
        if index%2:
            temp=0 if ele else 1
            
        for y in range(j,j+r):
            count+=0 if temp==b[x][y] else 1
            temp=0 if temp else 1
    return count


for s in range(size,1,-1):
    flag=0
    for x in range(n-s+1):
        for y in range(m-s+1):
            ic=min(invert(x,y,s,0),invert(x,y,s,1))
            res[s]=min(res[s],ic)
            # print(x,y,s,ic)
            if not ic:
                flag=1
                break
        if flag:
            break
    if flag:
        break

for t in map(int,input().split()):
    for index,e in reversed(list(enumerate(res))):
        if e<=t:
            print(index)
            break

res = list(map(lambda x: 0 if x==size**2 else x,res))

import sys

dp=[[0 for i in range(201)]for i in range(201)]
Q =[sys.maxsize for i in range(201)]
Q1=[sys.maxsize for i in range(201)]


def compareWith(A ,B ,n ,m , f):
    
    for i in range(1,n+1):
        for j in range(1,m+1):
            
            a=0
            if(A[i-1][j-1]!=B[i-1][j-1]):
                a=1
            
            dp[i][j]=a + dp[i-1][j] + dp[i][j-1] -dp[i-1][j-1]
            
    
    for i in range(1,n+1):
        for j in range(1,m+1):
            k=i
            l=j
            r=1
            while k<=n and l<=m:
                a=findError(i,j,k,l)
                Q[r]=min(Q[r],a)
                k+=1
                l+=1
                r+=1
                
    if f==1:
        Q1=Q[:]


def findError(i,j,k,l):
    return dp[k][l]-dp[k][j-1]-dp[i-1][l]+dp[i-1][j-1]
    



n, m = map(int, input().split()) 

A=[]
C=[]
B=[]

for i in range(n):
    s=input()
    A.append(s)
    
for i in range(n):
    sb=""
    sc=""
    for j in range(m):
        if(i%2==0):
            if(j%2==0):
                sb+='1'
                sc+='0'
            else:
                sb+='0'
                sc+='1'
        else:
            if(j%2==1):
                sb+='1'
                sc+='0'
            else:
                sb+='0'
                sc+='1'
    B.append(sb)
    C.append(sc)
    
# print(*B, sep='\n')
# print("****")
# print(*C, sep='\n')

compareWith(A,B,n,m,1)
compareWith(A,C,n,m,0)

q=int(input())
c=list(map(int,input().split()))

for i in c:
    a=0
    for j in range(1,min(m,n)+1):
        if i>=Q[j] or i>=Q1[j]:
            a=max(a,j)
    
    print(a)


    

# cook your dish here
n,m=map(int,input().split())
R=n
C=m
a=[None]*n
z=[0]*n
o=[1]*n
for i in range(m):
    if i%2!=0:
        z[i]=1
        o[i]=0
zi=[None]*n
oi=[None]*n
for i in range(n):
    a[i]=input()
    a[i]=list(a[i])
    for j in range(m):
        a[i][j]=int(a[i][j])
    
    if i%2==0:
        zi[i]=z[:]
        oi[i]=o[:]
    else:
        zi[i]=o[:]
        oi[i]=z[:]
forzi=0
foroi=0
psao = [[0 for x in range(C)] for y in range(R)]  
psaz = [[0 for x in range(C)] for y in range(R)] 
noioo=0
noizz=0
noio=0
noiz=0
for i in range(n):
    noiz=0
    noio=0
    
    for j in range(m):
        
        if i==0:
            if a[i][j]!=oi[i][j]:
                noio+=1
            else:
                noiz+=1
            psao[i][j]=noio
            psaz[i][j]=noiz
        else:
            if a[i][j]!=oi[i][j]:
                noio+=1
            else:
                noiz+=1
            psaz[i][j]=noiz+psaz[i-1][j]
            psao[i][j]=noio+psao[i-1][j]
    

        
    


mmm=[]
for i in range(2,min(m,n)+1):
    c=0
    ap=[]
    for j in range(n-i+1):
        for k in range(m-i+1):
            czz=0
            czz1=0
            czz2=0
            coo=0
            cor=0
            czz+=(psaz[j+i-1][k+i-1])
            coo+=(psao[j+i-1][k+i-1])

            if k-1>=0:
                czz-=(psaz[j+i-1][k-1])
                coo-=(psao[j+i-1][k-1])
            else:
                czz+=0
            if j-1>=0:
                czz-=(psaz[j-1][k+i-1])
                coo-=(psao[j-1][k+i-1])

            else:
                czz+=0
            if j-1>=0 and k-1>=0:
                czz+=(psaz[j-1][k-1])
                coo+=(psao[j-1][k-1])
            else:
                czz+=0
            
            ap.append((min((abs(coo)),abs(czz))))
    mmm.append(min(ap))

q=int(input())
lo=[int(pp) for pp in input().split()]
maxq=max(mmm)
for i in range(q):
    if lo[i]>maxq:
        print(min(n,m))
    else:
        j=len(mmm)-1
        ind=0
        while j>=0:
            if lo[i]>=mmm[j]:
                ind=j+2
                break
            j-=1
        print(ind)