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.

Source: codechef | Difficulty: HARD
Tags: Range queries


Solutions:
import sys
from collections import defaultdict
dp = defaultdict(int)
sys.setrecursionlimit(10 ** 9)
(a, b) = [int(j) for j in input().split()]
board = []
for i in range(a):
	l = [int(j) for j in input()]
	board.append(l)
b2 = [[0 for i in range(b)] for j in range(a)]
for i in range(a):
	for j in range(b):
		if (i + j) % 2:
			if board[i][j] == 0:
				b2[i][j] = 1
		elif board[i][j] == 1:
			b2[i][j] = 1

def fun(b2, x, y):
	if x < 0 or y < 0:
		return 0
	elif x == 0 and y == 0:
		if b2[0][0] == 0:
			dp[x, y] = 0
			return 0
		if b2[0][0] == 1:
			dp[x, y] = 1
			return 1
	elif (x, y) in dp:
		return dp[x, y]
	else:
		if b2[x][y] == 1:
			k = fun(b2, x, y - 1) + fun(b2, x - 1, y) - fun(b2, x - 1, y - 1) + 1
		else:
			k = fun(b2, x, y - 1) + fun(b2, x - 1, y) - fun(b2, x - 1, y - 1)
		dp[x, y] = k
		return k
fun(b2, a - 1, b - 1)
l = [1000000000000000000000 for i in range(201)]
for i in range(2, min(a, b) + 1):
	le = i ** 2
	mi = 10 ** 9
	for j in range(a - i + 1):
		for k in range(b - i + 1):
			k1 = dp[j + i - 1, k + i - 1] - dp[j - 1, k + i - 1] - dp[j + i - 1, k - 1] + dp[j - 1, k - 1]
			k2 = le - k1
			mi = min(k1, k2, mi)
	l[i - 1] = mi
l[0] = 0
lei = len(l)
q = int(input())
ql = [int(j) for j in input().split()]
for i in ql:
	high = i
	for i in range(lei):
		if l[i] > high:
			print(i)
			break


def pre():
	for i in range(n):
		for j in range(m):
			if a[i][j] == '1':
				b[i][j].append((1, 0))
			else:
				b[i][j].append((0, 1))
			hr = 1
			vr = 1
			co = 0
			if b[i][j][0][1]:
				co = 1
			for k in range(min(i, j)):
				hr = int(not hr)
				vr = int(not vr)
				if a[i - k - 1][j] != str(vr):
					co += 1
				if a[i][j - k - 1] != str(hr):
					co += 1
				wb = b[i - 1][j - 1][k][1] + co
				b[i][j].append(((k + 2) ** 2 - wb, wb))
(n, m) = [int(x) for x in input().split()]
a = []
for i in range(n):
	a.append(input())
b = [[[] for i in range(m)] for j in range(n)]
pre()
ans = [0] * 40000
for i in range(n):
	for j in range(m):
		for k in range(min(i, j) + 1):
			ans[b[i][j][k][0]] = max(ans[b[i][j][k][0]], k + 1)
			ans[b[i][j][k][1]] = max(ans[b[i][j][k][1]], k + 1)
for i in range(1, len(ans)):
	ans[i] = max(ans[i], ans[i - 1])
q = int(input())
qu = [int(x) for x in input().split()]
for el in qu:
	if el > 20000:
		print(min(n, m))
	else:
		print(ans[el])


(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) = 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)
			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 bisect
(n, m) = [int(x) for x in input().split()]
Board = [(m + 1) * [0]]
Wrong = [(m + 1) * [0]]
for i in range(n):
	row = [0] + [int(x) for x in input()]
	comRow = [0]
	for j in range(m):
		comRow.append(comRow[j] + Wrong[i][j + 1] - Wrong[i][j] + (i + j + row[j + 1]) % 2)
	Board.append(row)
	Wrong.append(comRow)
boardSize = [0] + min(n, m) * [n * n]
for k in range(len(boardSize)):
	for i in range(1, n + 1 - k):
		for j in range(1, m + 1 - k):
			changes = Wrong[i + k][j + k] - Wrong[i - 1][j + k] - Wrong[i + k][j - 1] + Wrong[i - 1][j - 1]
			boardSize[k] = min(boardSize[k], changes, (k + 1) * (k + 1) - changes)
q = int(input())
qu = [int(x) for x in input().split()]
for c in qu:
	print(min(bisect.bisect_right(boardSize, c), min(m, n)))


(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
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
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
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()
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)


def hz_arr(arr, N, M):
	ans = []
	for g in range(N):
		pref = [0]
		for h in range(M):
			if g % 2 == 0:
				if h % 2 == 0 and int(arr[g][h]) == 1:
					pref.append(pref[h] + 1)
				elif h % 2 == 1 and int(arr[g][h]) == 0:
					pref.append(pref[h] + 1)
				else:
					pref.append(pref[h])
			elif h % 2 == 0 and int(arr[g][h]) == 0:
				pref.append(pref[h] + 1)
			elif h % 2 == 1 and int(arr[g][h]) == 1:
				pref.append(pref[h] + 1)
			else:
				pref.append(pref[h])
		ans.append(pref)
	return ans

def ho_arr(arr, N, M):
	ans = []
	for g in range(N):
		pref = [0]
		for h in range(M):
			if g % 2 == 0:
				if h % 2 == 0 and int(arr[g][h]) == 0:
					pref.append(pref[h] + 1)
				elif h % 2 == 1 and int(arr[g][h]) == 1:
					pref.append(pref[h] + 1)
				else:
					pref.append(pref[h])
			elif h % 2 == 0 and int(arr[g][h]) == 1:
				pref.append(pref[h] + 1)
			elif h % 2 == 1 and int(arr[g][h]) == 0:
				pref.append(pref[h] + 1)
			else:
				pref.append(pref[h])
		ans.append(pref)
	return ans

def vz_arr(hz_arr, N, M):
	ans = []
	for y in range(M + 1):
		pref = [0]
		for x in range(N):
			pref.append(hz_arr[x][y] + pref[x])
		ans.append(pref)
	return ans

def vo_arr(ho_arr, N, M):
	ans = []
	for y in range(M + 1):
		pref = [0]
		for x in range(N):
			pref.append(ho_arr[x][y] + pref[x])
		ans.append(pref)
	return ans

def ret_max(arr, c):
	for d in range(len(arr) - 1, -1, -1):
		if arr[d] <= c:
			return d + 1

def zero(vz, p, q, l):
	return vz[p + l][q + l] - vz[p][q + l] - vz[p + l][q] + vz[p][q]

def one(vo, p, q, l):
	return vo[p + l][q + l] - vo[p][q + l] - vo[p + l][q] + vo[p][q]
[N, M] = [int(i) for i in input().split()]
arr = []
s = ''
for x in range(N):
	s = input()
	arr.append(s)
Q = int(input())
qry = [int(i) for i in input().split()]
lookup = []
hz = hz_arr(arr, N, M)
ho = ho_arr(arr, N, M)
vz = vz_arr(hz, N, M)
vo = vo_arr(ho, N, M)
for w in range(1, min(N, M) + 1):
	done = 0
	ans = pow(10, 9) + 1
	for p in range(N - w + 1):
		for q in range(M - w + 1):
			temp = min(zero(vz, p, q, w), one(vo, p, q, w))
			ans = min(ans, temp)
	lookup.append(ans)
for e in range(len(qry)):
	print(ret_max(lookup, qry[e]))


(n, m) = map(int, input().split())
dp = [[0 for x in range(m + 1)] for y in range(n + 1)]
l1 = [[0 for x in range(m)] for y in range(n)]
l2 = [[0 for x in range(m)] for y in range(n)]
for ii in range(n):
	for jj in range(m):
		if (ii + jj) % 2 == 0:
			l2[ii][jj] = 1
		else:
			l2[ii][jj] = 0
for i in range(n):
	s = input()
	for j in range(m):
		l1[i][j] = int(s[j])
l = [0] * min(n, m)
sq = min(n, m)
l3 = [0] * sq
for i in range(n):
	s = 0
	for j in range(m):
		if l1[i][j] != l2[i][j]:
			s += 1
			dp[i + 1][j + 1] = s
		else:
			dp[i + 1][j + 1] = s
for i in range(1, n + 1):
	for j in range(1, m + 1):
		dp[i][j] = dp[i - 1][j] + dp[i][j]
for no in range(sq, 1, -1):
	mymin = 1000000
	for i in range(n):
		for j in range(m):
			if i + no <= n and j + no <= m:
				ans = dp[i + no][j + no] - dp[i][j + no] - dp[i + no][j] + dp[i][j]
				ans = min(ans, no * no - ans)
				if ans < mymin:
					mymin = ans
	l3[no - 1] = mymin
	if mymin == 0:
		break
q = int(input())
lq = list(map(int, input().split()))
for i in lq:
	if i > sq * sq // 2:
		print(sq)
	else:
		for j in range(len(l3) - 1, -1, -1):
			if l3[j] <= i:
				print(j + 1)
				break


import numpy as np
(n, m) = [int(i) for i in input().strip().split(' ')]
arr = [0] * n
for i in range(n):
	inp = list(input())
	arr[i] = [int(k) for k in inp]
req = min(m, n)
dp_0 = [[[0 for k in range(m)] for j in range(n)] for i in range(req + 1)]
for i in range(n):
	for j in range(m):
		dp_0[1][i][j] = arr[i][j]
ans_arr = [0] * 20001
for i in range(2, req + 1):
	cl = 100000
	i2 = (i - 1) ** 2
	for j in range(0, n + 1 - i):
		for k in range(0, m + 1 - i):
			dp_0[i][j][k] = i2 - dp_0[i - 1][j + 1][k] + (i2 - dp_0[i - 1][j][k + 1]) - dp_0[i - 2][j + 1][k + 1] + dp_0[1][j][k] + dp_0[1][j + i - 1][k + i - 1]
			cl = min(min(dp_0[i][j][k], i ** 2 - dp_0[i][j][k]), cl)
	ans_arr[int(cl)] = i
prev = ans_arr[0]
for i in range(20001):
	curr = ans_arr[i]
	if curr == 0:
		ans_arr[i] = prev
	else:
		prev = ans_arr[i]
q = int(input())
que = [int(i) for i in input().strip().split(' ')]
for i in que:
	if i > 20000:
		print(int(ans_arr[-1]))
	else:
		print(int(ans_arr[i]))


def get_aux_matrix(C, n, m):
	mat = [[0 for j in range(0, m)] for i in range(0, N)]
	for i in range(0, m):
		mat[0][i] = C[0][i]
	for i in range(1, n):
		for j in range(0, m):
			mat[i][j] = C[i][j] + mat[i - 1][j]
	for i in range(0, n):
		for j in range(1, m):
			mat[i][j] += mat[i][j - 1]
	return mat

def sum_sub_matrix(mat, i1, j1, i2, j2):
	ret = mat[i2][j2]
	if i1 > 0:
		ret -= mat[i1 - 1][j2]
	if j1 > 0:
		ret -= mat[i2][j1 - 1]
	if i1 > 0 and j1 > 0:
		ret += mat[i1 - 1][j1 - 1]
	return ret

def get_nb_intersects(aux_C, side):
	ret = 2 ** 64
	for i in range(0, len(aux_C) - side + 1):
		for j in range(0, len(aux_C) - side + 1):
			ret = min(ret, sum_sub_matrix(aux_C, i, j, i + side - 1, j + side - 1))
	return ret
(N, M) = [int(s) for s in input().split(' ')]
board = []
for i in range(0, N):
	board.append([int(s) for s in input()])
C1 = [[0 for j in range(0, M)] for i in range(0, N)]
C2 = [[0 for j in range(0, M)] for i in range(0, N)]
for i in range(0, N):
	for j in range(0, M):
		if board[i][j] != (j % 2 + i % 2) % 2:
			C1[i][j] = 1
		if board[i][j] != (j % 2 + (i + 1) % 2) % 2:
			C2[i][j] = 1
aux_C1 = get_aux_matrix(C1, N, M)
aux_C2 = get_aux_matrix(C2, N, M)
cTab = [0] * (min(N, M) + 1)
cTab[1] = 0
for i in range(2, len(cTab)):
	c1 = get_nb_intersects(aux_C1, i)
	c2 = get_nb_intersects(aux_C2, i)
	cTab[i] = min(c1, c2)
Q = int(input())
for c in [int(s) for s in input().split(' ')]:
	side = len(cTab) - 1
	while cTab[side] > c:
		side = side - 1
	print(side)


(n, m) = map(int, input().split())
grid = []
for i in range(n):
	grid.append(list(map(int, input())))
inf = int(1000000000.0)
acc = [[0] * (m + 1) for i in range(n + 1)]
min_inv = [inf] * (min(n, m) + 1)

def comp_inv(flip=0):
	for i in range(n):
		for j in range(m):
			acc[i + 1][j + 1] = 0
			if i + j & 1:
				if grid[i][j] == flip:
					acc[i + 1][j + 1] += 1
			elif grid[i][j] == (not flip):
				acc[i + 1][j + 1] += 1
			acc[i + 1][j + 1] += acc[i + 1][j]
		for j in range(m):
			acc[i + 1][j + 1] += acc[i][j + 1]

def get_inv_sq(x, y, p, q):
	return acc[p + 1][q + 1] - acc[x][q + 1] - acc[p + 1][y] + acc[x][y]

def comp_min_inv():
	for sq_sz in range(0, min(n, m)):
		for i in range(0, n - sq_sz):
			for j in range(0, m - sq_sz):
				min_inv[sq_sz + 1] = min(min_inv[sq_sz + 1], get_inv_sq(i, j, i + sq_sz, j + sq_sz))
comp_inv()
comp_min_inv()
comp_inv(flip=1)
comp_min_inv()
q = int(input())
c_arr = map(int, input().split(' '))
for c in c_arr:
	for j in range(len(min_inv) - 1, 0, -1):
		if min_inv[j] <= c:
			print(j)
			break


from functools import reduce as rd
import operator as optr
import math
import itertools
inp = lambda : map(int, input().split())
(n, m) = inp()
matrix1 = [] * n
matrix2 = [] * n
maximum = [1000000] * 600
for row in range(n):
	st = input()
	l = []
	for abc in st:
		l.append(int(abc))
	matrix1.append(l)
for row in range(n):
	l = []
	for col in range(m):
		if (row + col) % 2 == 0 and matrix1[row][col] == 0:
			l.append(1)
		elif (row + col) % 2 == 0 and matrix1[row][col] == 1:
			l.append(0)
		elif (row + col) % 2 != 0 and matrix1[row][col] == 1:
			l.append(1)
		elif (row + col) % 2 != 0 and matrix1[row][col] == 0:
			l.append(0)
	matrix2.append(l)
for row in range(1, n):
	for col in range(m):
		matrix2[row][col] += matrix2[row - 1][col]
for row in range(1, n):
	for col in range(m):
		matrix2[col][row] += matrix2[col][row - 1]
fault = 0
for row in range(n):
	for col in range(m):
		fault = 0
		val = min(m - col, n - row)
		for k in range(1, val + 1):
			fault = matrix2[row + k - 1][col + k - 1]
			if row > 0:
				fault -= matrix2[row - 1][col + k - 1]
			if col > 0:
				fault -= matrix2[row + k - 1][col - 1]
			if row > 0 and col > 0:
				fault += matrix2[row - 1][col - 1]
			if fault > k ** 2 // 2:
				fault = k ** 2 - fault
			maximum[k] = min(maximum[k], fault)
a = min(n, m)
index = maximum[a]
query = int(input())
q = list(inp())
for c in q:
	if c > index:
		print(a)
	else:
		for dd in range(1, a + 1):
			if maximum[dd] == c:
				if maximum[dd + 1] == c:
					continue
				print(dd)
				break
			elif maximum[dd] > c:
				print(dd - 1)
				break


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'
		elif j % 2 == 1:
			sb += '1'
			sc += '0'
		else:
			sb += '0'
			sc += '1'
	B.append(sb)
	C.append(sc)
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)


(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)


from collections import defaultdict
pre = defaultdict(int)

def M1(gr, x, y):
	if x == 0 or y == 0:
		return 0
	elif (x, y) in pre:
		return pre[x, y]
	else:
		ans = M1(gr, x - 1, y) + M1(gr, x, y - 1) - M1(gr, x - 1, y - 1) + gr[x][y]
		pre[x, y] = ans
		return ans
(N, M) = (int(i) for i in input().split())
gr = [[int(i) for i in input()] for j in range(N)]
gr1 = [[0 for i in range(M + 1)] for j in range(N + 1)]
for i in range(1, N + 1):
	for j in range(1, M + 1):
		gr1[i][j] = 0 if gr[i - 1][j - 1] == (i + j) % 2 else 1
q = int(input())
qls = (int(i) for i in input().split())
M1(gr1, N, M)
maxlen = min(N, M)
sidelenarr = [200000000000 for i in range(202)]
for lenght in range(1, maxlen + 1):
	area = lenght * lenght
	for u in range(1, N - lenght + 2):
		x = u + lenght - 1
		for v in range(1, M - lenght + 2):
			y = v + lenght - 1
			pencelose = pre[x, y] - pre[u - 1, y] - pre[x, v - 1] + pre[u - 1, v - 1]
			sidelenarr[lenght] = min(pencelose, area - pencelose, sidelenarr[lenght])
sidelenarr[0] = 0
for i in range(1, 201):
	sidelenarr[i] = max(sidelenarr[i], sidelenarr[i - 1])

def bsearch(left, right, val):
	mid = (left + right) // 2
	if left == right:
		if sidelenarr[left] > val:
			return -1
		else:
			return left
	elif sidelenarr[mid] > val:
		return bsearch(left, mid, val)
	else:
		return max(bsearch(mid + 1, right, val), mid)
for i in qls:
	print(bsearch(0, maxlen + 1, i))


from collections import defaultdict
(n, m) = (int(s) for s in input().split())
c = [input() for j in range(n)]
l = [[int(s) for s in c[i]] for i in range(n)]
c1 = [[0 for i in range(m)] for k in range(n)]
for i in range(n):
	for j in range(m):
		w = 0
		if (i + j) % 2 == 1:
			w = 1
		if l[i][j] != w:
			c1[i][j] = 1
d1 = defaultdict(int)
for i in range(n):
	for j in range(m):
		if i == 0:
			d1[i, j] = c1[i][j] + d1[i, j - 1]
		else:
			d1[i, j] = c1[i][j] + d1[i - 1, j] + d1[i, j - 1] - d1[i - 1, j - 1]
d2 = defaultdict(int)
d2[0] = 0
d2[1] = 0
for i in range(2, min(n, m) + 1):
	mini = 10 ** 9 + 7
	for j in range(n - i + 1):
		for k in range(m - i + 1):
			ans1 = d1[j + i - 1, k + i - 1] - d1[j + i - 1, k - 1] - d1[j - 1, k + i - 1] + d1[j - 1, k - 1]
			ans2 = min(ans1, i ** 2 - ans1)
			if mini > ans2:
				mini = ans2
	d2[i] = mini
q = int(input())
l1 = [int(s) for s in input().split()]
for j in l1:
	low = 0
	high = min(n, m)
	ans = (low + high) // 2
	while low < high:
		if d2[ans] <= j:
			low = ans + 1
		else:
			high = ans
		ans = (low + high) // 2
	if ans == 0:
		print(0)
	elif ans == min(n, m):
		if d2[ans] <= j:
			print(ans)
		else:
			print(ans - 1)
	else:
		print(ans - 1)


(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)


(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])


(a, b) = map(int, input().split())
arr2d = []
for i in range(a):
	arr2d.append(list(map(int, input())))
gi = int(1000000000.0)
acc = [[0] * (b + 1) for i in range(a + 1)]
szm = [gi] * (min(a, b) + 1)

def citr(shift=0):
	for i in range(a):
		for j in range(b):
			acc[i + 1][j + 1] = 0
			if i + j & 1:
				if arr2d[i][j] == shift:
					acc[i + 1][j + 1] += 1
			elif arr2d[i][j] == (not shift):
				acc[i + 1][j + 1] += 1
			acc[i + 1][j + 1] += acc[i + 1][j]
		for j in range(b):
			acc[i + 1][j + 1] += acc[i][j + 1]

def szopp(x, y, p, q):
	return acc[p + 1][q + 1] - acc[x][q + 1] - acc[p + 1][y] + acc[x][y]

def citr2():
	for sz in range(0, min(a, b)):
		for i in range(0, a - sz):
			for j in range(0, b - sz):
				szm[sz + 1] = min(szm[sz + 1], szopp(i, j, i + sz, j + sz))
citr()
citr2()
citr(shift=1)
citr2()
q = int(input())
arr5 = map(int, input().split(' '))
for c in arr5:
	for j in range(len(szm) - 1, 0, -1):
		if szm[j] <= c:
			print(j)
			break


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
(N, M) = map(int, input().split())
A = []
for i in range(N):
	A.append([int(x) for x in input()])
(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()]
for q in qs:
	print(bisect.bisect_right(ans, q) - 1)


(n, m) = [int(i) for i in input().split(' ')]
a = []
for _ in range(n):
	a.append([int(i) for i in input()])
b1 = [[0 for i in range(m + 1)] for j in range(n + 1)]
b2 = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(n):
	for j in range(m):
		if i % 2 == 0 and j % 2 == 0 or (i % 2 == 1 and j % 2 == 1):
			if a[i][j] == 0:
				b1[i + 1][j + 1] = 0
				b2[i + 1][j + 1] = 1
			else:
				b1[i + 1][j + 1] = 1
				b2[i + 1][j + 1] = 0
		elif a[i][j] == 1:
			b1[i + 1][j + 1] = 0
			b2[i + 1][j + 1] = 1
		else:
			b1[i + 1][j + 1] = 1
			b2[i + 1][j + 1] = 0
for i in range(1, n + 1):
	for j in range(1, m + 1):
		b1[i][j] += b1[i - 1][j] + b1[i][j - 1] - b1[i - 1][j - 1]
		b2[i][j] += b2[i - 1][j] + b2[i][j - 1] - b2[i - 1][j - 1]
from collections import defaultdict as dd
d = []
for k in range(0, min(m, n)):
	r = 9999999999999999
	for i in range(1, n - k + 1):
		for j in range(1, m - k + 1):
			(x1, y1) = (i, j)
			(x2, y2) = (i + k, j + k)
			f1 = b1[x2][y2]
			f2 = b2[x2][y2]
			f1 -= b1[x1 - 1][y1 + k] + b1[x1 + k][y1 - 1] - b1[x1 - 1][y1 - 1]
			f2 -= b2[x1 - 1][y1 + k] + b2[x1 + k][y1 - 1] - b2[x1 - 1][y1 - 1]
			if r > min(f1, f2):
				r = min(f1, f2)
	d.append(r)
import bisect
nq = int(input())
q = [int(I) for I in input().split(' ')]
for i in q:
	t = bisect.bisect_right(d, i)
	print(t)


from bisect import bisect_right as br
for _ in range(1):
	(n, m) = [int(i) for i in input().split(' ')]
	l = []
	for i in range(n):
		l.append([int(i) for i in input()])
	dp1 = [[0] * (m + 1) for i in range(n + 1)]
	dp2 = [[0] * (m + 1) for i in range(n + 1)]
	k1 = [[0] * (m + 1) for i in range(n + 1)]
	k2 = [[0] * (m + 1) for i in range(n + 1)]
	for i in range(n + 1):
		for j in range(m + 1):
			if (i + j) % 2 == 0:
				k1[i][j] = 1
			else:
				k2[i][j] = 1
	for i in range(n):
		for j in range(m):
			if k1[i][j] == 1:
				if l[i][j] == 0:
					dp1[i + 1][j + 1] = 1
				else:
					dp2[i + 1][j + 1] = 1
			elif l[i][j] == 1:
				dp1[i + 1][j + 1] = 1
			else:
				dp2[i + 1][j + 1] = 1
	for i in range(n + 1):
		for j in range(1, m + 1):
			dp1[i][j] += dp1[i][j - 1]
			dp2[i][j] += dp2[i][j - 1]
	for i in range(m + 1):
		for j in range(1, n + 1):
			dp1[j][i] += dp1[j - 1][i]
			dp2[j][i] += dp2[j - 1][i]
	nk = min(n, m)
	ans = [40000 for i in range(nk)]
	for k in range(nk):
		for i in range(1, n - k + 1):
			for j in range(1, m - k + 1):
				chng1 = dp1[i + k][j + k] + dp1[i - 1][j - 1] - dp1[i + k][j - 1] - dp1[i - 1][j + k]
				chng2 = dp2[i + k][j + k] + dp2[i - 1][j - 1] - dp2[i + k][j - 1] - dp2[i - 1][j + k]
				ans[k] = min(ans[k], chng1, chng2)
	q = int(input())
	for i in [int(i) for i in input().split(' ')]:
		print(br(ans, i))


import sys
from collections import defaultdict as dd
from itertools import permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
mod = 10 ** 9 + 7

def ri(flag=0):
	if flag == 0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())
(n, m) = ri()
mat = []
for i in range(n):
	mat.append(input())
dp1 = [[0 for i in range(m + 1)] for j in range(n + 1)]
dp2 = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(n):
	for j in range(m):
		if (i + j) % 2 == 0:
			if mat[i][j] == '0':
				dp1[i + 1][j + 1] = 1
		elif mat[i][j] == '1':
			dp1[i + 1][j + 1] = 1
for i in range(n):
	for j in range(m):
		if (i + j) % 2 == 1:
			if mat[i][j] == '0':
				dp2[i + 1][j + 1] = 1
		elif mat[i][j] == '1':
			dp2[i + 1][j + 1] = 1
for i in range(1, n + 1):
	for j in range(1, m + 1):
		dp1[i][j] += dp1[i - 1][j] + dp1[i][j - 1] - dp1[i - 1][j - 1]
		dp2[i][j] += dp2[i - 1][j] + dp2[i][j - 1] - dp2[i - 1][j - 1]
res = dd(set)
for i in range(1, n + 1):
	for j in range(1, m + 1):
		try:
			k = 0
			while 1:
				get1 = dp1[i + k][j + k] + dp1[i - 1][j - 1] - dp1[i + k][j - 1] - dp1[i - 1][j + k]
				get2 = dp2[i + k][j + k] + dp2[i - 1][j - 1] - dp2[i + k][j - 1] - dp2[i - 1][j + k]
				res[k + 1].add(min(get1, get2))
				k += 1
		except:
			just = 1
ans = []
for i in res:
	ans.append((i, min(res[i])))
ans.sort()
final = []
for i in ans:
	final.append(i[1])
for i in range(ri(1)):
	qu = ri()
	for j in qu:
		print(br(final, j))


def sum_up(row1, col1, row2, col2):
	return sums[row2 + 1][col2 + 1] - sums[row2 + 1][col1] - sums[row1][col2 + 1] + sums[row1][col1]
(n, m) = map(int, input().strip().split())
c = []
arr1 = [[0 for i in range(205)] for j in range(205)]
arr2 = [[0 for i in range(205)] for j in range(205)]
for _ in range(n):
	c.append(list(input()))
(s1, s2) = ({}, {})
for i in range(n):
	for j in range(m):
		if (i + j) % 2 == 0:
			if c[i][j] == '1':
				arr1[i][j] = 0
			else:
				arr1[i][j] = 1
				s1[i] = j
		elif c[i][j] == '0':
			arr1[i][j] = 0
		else:
			arr1[i][j] = 1
			s1[i] = j
		if (i + j) % 2 != 0:
			if c[i][j] == '1':
				arr2[i][j] == 0
			else:
				arr2[i][j] = 1
				s2[i] = j
		elif c[i][j] == '0':
			arr2[i][j] = 0
		else:
			arr2[i][j] = 1
			s2[i] = j
max_poss = min(n, m)
dp1 = [-1] * 1000005
dp2 = [-1] * 1000005
(last1, last2) = (0, 0)
(row, col) = (n, m)
sums = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(1, row + 1):
	for j in range(1, col + 1):
		sums[i][j] = arr1[i - 1][j - 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1]
for l in range(2, max_poss + 1):
	mini = 1000005
	for i in range(n - l + 1):
		for j in range(m - l + 1):
			inversions = sum_up(i, j, i + l - 1, j + l - 1)
			if inversions < mini:
				mini = inversions
	dp1[mini] = l
	last1 = max(last1, mini)
sums = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(1, row + 1):
	for j in range(1, col + 1):
		sums[i][j] = arr2[i - 1][j - 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1]
for l in range(2, max_poss + 1):
	mini = 1000005
	for i in range(n - l + 1):
		for j in range(m - l + 1):
			inversions = sum_up(i, j, i + l - 1, j + l - 1)
			if inversions < mini:
				mini = inversions
	dp2[mini] = l
	last2 = max(last2, mini)
pre = 0
for i in range(last1 + 1):
	if dp1[i] == -1 and i == 0:
		while dp[i] == -1:
			dp1[i] = 1
			i += 1
	elif dp1[i] == -1:
		while i <= last1 and dp1[i] == -1:
			dp1[i] = pre
			i += 1
	else:
		pre = dp1[i]
		i += 1
for i in range(last2 + 1):
	if dp2[i] == -1 and i == 0:
		while dp2[i] == -1:
			dp2[i] = 1
			i += 1
	elif dp2[i] == -1:
		while i <= last2 and dp2[i] == -1:
			dp2[i] = pre
			i += 1
	else:
		pre = dp2[i]
		i += 1
q = int(input())
query = list(map(int, input().strip().split()))
for i in query:
	if n == 1 or m == 1:
		print(1)
	elif i <= min(last1, last2):
		if dp1[i] == 0 and dp2[i] == 0:
			print(1)
		else:
			print(max(dp1[i], dp2[i]))
	else:
		print(max_poss)


import math

def compute_horizontal_diff(chessboard, N, M):
	horizontal_diff = [[0 for j in range(M)] for i in range(N)]
	compare_str = '10' * math.floor(M / 2) + '1' * (M % 2)
	compare_str = list((int(bit) for bit in compare_str))
	for i in range(N):
		if chessboard[i][M - 1] != compare_str[M - 1]:
			horizontal_diff[i][M - 1] = 1
		for j in reversed(range(M - 1)):
			if chessboard[i][j] != compare_str[j]:
				horizontal_diff[i][j] = horizontal_diff[i][j + 1] + 1
			else:
				horizontal_diff[i][j] = horizontal_diff[i][j + 1]
	return horizontal_diff

def compute_vertical_diff(chessboard, N, M):
	vertical_diff = [[0 for j in range(M)] for i in range(N)]
	compare_str = '10' * math.floor(N / 2) + '1' * (N % 2)
	compare_str = list((int(bit) for bit in compare_str))
	for j in range(M):
		if chessboard[N - 1][j] != compare_str[N - 1]:
			vertical_diff[N - 1][j] = 1
		for i in reversed(range(N - 1)):
			if chessboard[i][j] != compare_str[i]:
				vertical_diff[i][j] = vertical_diff[i + 1][j] + 1
			else:
				vertical_diff[i][j] = vertical_diff[i + 1][j]
	return vertical_diff

def get_horizontal_bit_string_diff(horizontal_diff, N, M, i, j, length):
	if j + length == M:
		return horizontal_diff[i][j]
	else:
		return horizontal_diff[i][j] - horizontal_diff[i][j + length]

def get_vertical_bit_string_diff(vertical_diff, N, M, i, j, length):
	if i + length == N:
		return vertical_diff[i][j]
	else:
		return vertical_diff[i][j] - vertical_diff[i + length][j]

def get_num_of_diff(chessboard, horizontal_diff, vertical_diff, N, M, i, j, length, flag):
	diff = 0
	if flag == True and chessboard[i][j] == 0 or (flag == False and chessboard[i][j] == 1):
		diff += 1
	expected_bit = 1 if j % 2 == 0 else 0
	if flag == True and expected_bit == 1 or (flag == False and expected_bit == 0):
		diff += get_horizontal_bit_string_diff(horizontal_diff, N, M, i, j + 1, length - 1)
	else:
		diff += length - 1 - get_horizontal_bit_string_diff(horizontal_diff, N, M, i, j + 1, length - 1)
	expected_bit = 1 if i % 2 == 0 else 0
	if flag == True and expected_bit == 1 or (flag == False and expected_bit == 0):
		diff += get_vertical_bit_string_diff(vertical_diff, N, M, i + 1, j, length - 1)
	else:
		diff += length - 1 - get_vertical_bit_string_diff(vertical_diff, N, M, i + 1, j, length - 1)
	return diff
(N, M) = list(map(int, input().split()))
i = 0
chessboard = []
while i < N:
	row = list(map(int, input()))
	chessboard.append(row)
	i += 1
horizontal_diff = compute_horizontal_diff(chessboard, N, M)
vertical_diff = compute_vertical_diff(chessboard, N, M)
min_inverts = [(k + 1) ** 2 for k in range(min(N, M))]
min_inverts[0] = 0
for i in range(N):
	for j in range(M):
		prev_1 = 0
		prev_2 = 1
		if chessboard[i][j] == 1:
			flag = True
		else:
			flag = False
		for k in range(1, min(i, j) + 1):
			diff = get_num_of_diff(chessboard, horizontal_diff, vertical_diff, N, M, i - k, j - k, k + 1, flag)
			curr_1 = prev_1 + diff
			curr_2 = prev_2 + (2 * k + 1 - diff)
			min_inverts[k] = min(min_inverts[k], min(curr_1, curr_2))
			(prev_1, prev_2) = (curr_1, curr_2)
max_correct_chessboard = []
i = 0
j = 0
while i < len(min_inverts):
	while i < len(min_inverts) and min_inverts[i] == j:
		i += 1
	max_correct_chessboard.append(i)
	j += 1
Q = int(input())
c = list(map(int, input().split()))
i = 0
max_required_inverts = len(max_correct_chessboard) - 1
while i < Q:
	if c[i] >= max_required_inverts:
		print(max_correct_chessboard[max_required_inverts])
	else:
		print(max_correct_chessboard[c[i]])
	i += 1


(n, m) = map(int, input().split())
chs = []
for i in range(n):
	chs.append(list(input()))
test = []
for i in range(n):
	if i % 2 == 0:
		test.append(list('01' * (m // 2 + 1)))
	else:
		test.append(list('10' * (m // 2 + 1)))
inv = [[0] * (m + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(m):
		if chs[i][j] != test[i][j]:
			inv[i + 1][j + 1] = inv[i + 1][j] + 1
		else:
			inv[i + 1][j + 1] = inv[i + 1][j]
col_sum = [[0] * (m + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(m):
		if chs[i][j] != test[i][j]:
			col_sum[i + 1][j + 1] = col_sum[i][j + 1] + 1
		else:
			col_sum[i + 1][j + 1] = col_sum[i][j + 1]
min_req = [1000000000] * min(n + 1, m + 1)
min_req[1] = min_req[0] = 0
for i in range(2, n + 1):
	for j in range(2, m + 1):
		dim = min(i, j)
		s = inv[i][j] - inv[i][j - 1]
		for k in range(2, dim + 1):
			s += inv[i - k + 1][j] - inv[i - k + 1][j - k] + col_sum[i][j - k + 1] - col_sum[i - k + 1][j - k + 1]
			min_req[k] = min(s, k * k - s, min_req[k])
Q = int(input())
q = list(map(int, input().split()))
for i in q:
	ans = 0
	for j in range(len(min_req)):
		if i >= min_req[j]:
			ans = j
	print(ans)


(n, m) = map(int, input().split())
C = []
for i in range(n):
	R_ = list(map(int, list(input().strip())))
	C.append(R_)
vo = [[0 for _ in range(m)] for _ in range(n)]
ve = [[0 for _ in range(m)] for _ in range(n)]
vo[0][0] = C[0][0]
ve[0][0] = (C[0][0] + 1) % 2
for i in range(1, m):
	if C[0][i] == i % 2:
		vo[0][i] = vo[0][i - 1]
		ve[0][i] = ve[0][i - 1] + 1
	else:
		vo[0][i] = vo[0][i - 1] + 1
		ve[0][i] = ve[0][i - 1]
for i in range(1, n):
	if C[i][0] == i % 2:
		vo[i][0] = vo[i - 1][0]
		ve[i][0] = ve[i - 1][0] + 1
	else:
		vo[i][0] = vo[i - 1][0] + 1
		ve[i][0] = ve[i - 1][0]
for i in range(1, n):
	for j in range(1, m):
		if C[i][j] == (i + j) % 2:
			vo[i][j] = vo[i - 1][j] + vo[i][j - 1] - vo[i - 1][j - 1]
			ve[i][j] = ve[i - 1][j] + ve[i][j - 1] - ve[i - 1][j - 1] + 1
		else:
			vo[i][j] = vo[i - 1][j] + vo[i][j - 1] - vo[i - 1][j - 1] + 1
			ve[i][j] = ve[i - 1][j] + ve[i][j - 1] - ve[i - 1][j - 1]
vv = [100000 for _ in range(min(n, m) + 1)]
vv[1] = 0
for i in range(2, min(n, m) + 1):
	for j in range(n - i + 1):
		for k in range(m - i + 1):
			oo = vo[j + i - 1][k + i - 1]
			ee = ve[j + i - 1][k + i - 1]
			if j - 1 >= 0:
				oo = oo - vo[j - 1][k + i - 1]
				ee = ee - ve[j - 1][k + i - 1]
			if k - 1 >= 0:
				oo = oo - vo[j + i - 1][k - 1]
				ee = ee - ve[j + i - 1][k - 1]
			if k - 1 >= 0 and j - 1 >= 0:
				oo = oo + vo[j - 1][k - 1]
				ee = ee + ve[j - 1][k - 1]
			vv[i] = min(vv[i], oo, ee)
q = int(input())
quer = list(map(int, list(input().split())))
for j in quer:
	for i in range(min(n, m), 0, -1):
		if vv[i] <= j:
			print(i)
			break


def toggle_elem(elem):
	if elem == '0':
		return '1'
	else:
		return '0'

def printGrid(grid, n, m):
	for i in range(n):
		for j in range(m):
			print(grid[i][j], end=' ')
		print()
_input = input().split()
N = int(_input[0])
M = int(_input[1])
dp_data = [[0] * M for i in range(N)]
grid = []
for i in range(N):
	_input = input()
	grid.append(_input)
elem = '1'
for i in range(N):
	elem2 = elem
	prev = 0
	for j in range(M):
		if elem2 != grid[i][j]:
			dp_data[i][j] = prev + 1
		else:
			dp_data[i][j] = prev
		prev = dp_data[i][j]
		elem2 = toggle_elem(elem2)
	elem = toggle_elem(elem)
for i in range(1, N):
	for j in range(M):
		dp_data[i][j] += dp_data[i - 1][j]
max_size = min(N, M)
min_for_size_list = [0] * (max_size + 1)
for size in range(1, max_size + 1):
	min_for_size = -1
	for i in range(N + 1 - size):
		for j in range(M + 1 - size):
			l_corner = (i, j)
			r_corner = (i + size - 1, j + size - 1)
			ABCD = dp_data[r_corner[0]][r_corner[1]]
			if l_corner[0] - 1 >= 0 and l_corner[1] - 1 >= 0:
				A = dp_data[l_corner[0] - 1][l_corner[1] - 1]
			else:
				A = 0
			if l_corner[0] - 1 >= 0:
				AB = dp_data[l_corner[0] - 1][r_corner[1]]
			else:
				AB = 0
			if l_corner[1] - 1 >= 0:
				AC = dp_data[r_corner[0]][l_corner[1] - 1]
			else:
				AC = 0
			D = ABCD - (AB - A) - (AC - A) - A
			min_shuffle = min(D, size * size - D)
			if min_shuffle < min_for_size or min_for_size == -1:
				min_for_size = min_shuffle
				min_for_size_list[size] = min_for_size
Q = int(input())
_input = input().split()
for i in range(Q):
	query = int(_input[i])
	for j in range(len(min_for_size_list) - 1, 0, -1):
		if min_for_size_list[j] <= query:
			print(j)
			break


(n, m) = map(int, input().split())
grid = []
for i in range(n):
	grid.append(list(map(int, input())))
inf = int(1000000000.0)
auxArr = [[0 for k in range(m + 1)] for i in range(n + 1)]
minInvArr = [inf for i in range(min(n, m) + 1)]

def invGrid(nflips=0):
	for i in range(n):
		for j in range(m):
			auxArr[i + 1][j + 1] = 0
			if i + j & 1:
				if grid[i][j] == nflips:
					auxArr[i + 1][j + 1] += 1
			elif grid[i][j] == (not nflips):
				auxArr[i + 1][j + 1] += 1
			auxArr[i + 1][j + 1] += auxArr[i + 1][j]
		for j in range(m):
			auxArr[i + 1][j + 1] += auxArr[i][j + 1]

def get_inv_sq(x, y, p, q):
	return auxArr[p + 1][q + 1] - auxArr[x][q + 1] - auxArr[p + 1][y] + auxArr[x][y]

def minInv():
	for curSize in range(0, min(n, m)):
		for i in range(0, n - curSize):
			for j in range(0, m - curSize):
				minInvArr[curSize + 1] = min(minInvArr[curSize + 1], get_inv_sq(i, j, i + curSize, j + curSize))
invGrid()
minInv()
invGrid(nflips=1)
minInv()
q = int(input())
qArr = map(int, input().split(' '))
for c in qArr:
	for j in range(len(minInvArr) - 1, 0, -1):
		if minInvArr[j] <= c:
			print(j)
			break


def preProcess(mat, aux):
	for i in range(M):
		aux[0][i] = mat[0][i]
	for i in range(1, N):
		for j in range(M):
			aux[i][j] = mat[i][j] + aux[i - 1][j]
	for i in range(N):
		for j in range(1, M):
			aux[i][j] += aux[i][j - 1]

def sumQuery(aux, li, lj, ri, rj):
	res = aux[ri][rj]
	if li > 0:
		res = res - aux[li - 1][rj]
	if lj > 0:
		res = res - aux[ri][lj - 1]
	if li > 0 and lj > 0:
		res = res + aux[li - 1][lj - 1]
	return res

def solve():
	min_size = min(M, N)
	board = [[0 for _ in range(M)] for _ in range(N)]
	aux = [[0 for _ in range(M)] for _ in range(N)]
	cell = 1
	for i in range(N):
		col = [int(k) for k in input().strip()]
		if M % 2 == 0:
			cell = not cell
		for j in range(M):
			board[i][j] = 1 if col[j] == cell else 0
			cell = not cell
	preProcess(board, aux)
	prev = sumQuery(aux, 0, 0, N - 1, M - 1)
	prev = min(prev, min_size ** 2 - prev)
	flips = [0] * (N * M + 1)
	flips[prev:] = [min_size for _ in range(len(flips[prev:]))]
	cont = True
	for size in range(min(N, M) - 1, 1, -1):
		flips_needed = 10 ** 10
		for i in range(N - size + 1):
			for j in range(M - size + 1):
				val = sumQuery(aux, i, j, i + size - 1, j + size - 1)
				flips_needed = min(flips_needed, val, size * size - val)
				if val == 0:
					flips[0:prev] = [size for _ in range(len(flips[0:prev]))]
					cont = False
					break
			if not cont:
				break
		if not cont:
			break
		flips[flips_needed:prev] = [size for _ in range(len(flips[flips_needed:prev]))]
		prev = flips_needed
	Q = int(input())
	buff = []
	for q in input().split():
		q = int(q)
		if q >= N * M - flips[0]:
			buff.append(min_size)
			continue
		buff.append(flips[q])
	print('\n'.join((str(q) for q in buff)))
(N, M) = map(int, input().split())
solve()


(n, m) = map(int, input().split(' '))
CZM = 0
COM = 0
IVM0 = [[0] * m for i in range(n)]
IVM1 = [[0] * m for i in range(n)]
PSA0 = [[0] * m for i in range(n)]
PSA1 = [[0] * m for i in range(n)]

def findsum(PSA, i, j, k):
	(x, y) = (i - k, j - k)
	if x < 0 and y < 0:
		return PSA[i][j]
	if x < 0 and y >= 0:
		return PSA[i][j] - PSA[i][j - k]
	if x >= 0 and y < 0:
		return PSA[i][j] - PSA[i - k][j]
	if x >= 0 and y >= 0:
		return PSA[i][j] - PSA[i][j - k] - PSA[i - k][j] + PSA[i - k][j - k]

def calPAS(PSA, IVM, n, m):
	PSA[0][0] = IVM[0][0]
	for i in range(1, m):
		PSA[0][i] = PSA[0][i - 1] + IVM[0][i]
	for i in range(0, n):
		PSA[i][0] = PSA[i - 1][0] + IVM[i][0]
	for i in range(1, n):
		for j in range(1, m):
			PSA[i][j] = PSA[i - 1][j] + PSA[i][j - 1] - PSA[i - 1][j - 1] + IVM[i][j]
ans = 1
for i in range(n):
	x = input()
	for j in range(m):
		b = int(x[j])
		if (i + j) % 2 == 0:
			p = ans
			q = 1 - ans
		else:
			p = 1 - ans
			q = ans
		if b != p:
			IVM1[i][j] = 1
		if b != q:
			IVM0[i][j] = 1
calPAS(PSA0, IVM0, n, m)
calPAS(PSA1, IVM1, n, m)
ans0 = [-1] * (n * m + 1)
ans1 = [-1] * (n * m + 1)
(p, q) = (0, 0)
v = min(m, n)
for k in range(2, v + 1):
	p = q = k - 1
	for i in range(p, n):
		for j in range(q, m):
			x0 = findsum(PSA0, i, j, k)
			x1 = findsum(PSA1, i, j, k)
			ans0[x0] = max(k, ans0[x0])
			ans1[x1] = max(k, ans1[x1])
if ans0[0] == -1:
	ans0[0] = 1
if ans1[0] == -1:
	ans1[0] = 1
for i in range(1, n * m + 1):
	if ans0[i] == -1:
		ans0[i] = ans0[i - 1]
	elif ans0[i] < ans0[i - 1]:
		ans0[i] = ans0[i - 1]
	if ans1[i] == -1:
		ans1[i] = ans1[i - 1]
	elif ans1[i] < ans1[i - 1]:
		ans1[i] = ans1[i - 1]
q = int(input())
for q in input().split(' '):
	p = int(q)
	if p > n * m:
		print(max(ans0[n * m], ans1[n * m]))
	else:
		print(max(ans1[p], ans0[p]))


from bisect import bisect
(n, m) = map(int, input().split())
grid = []
for i in range(n):
	string = input()
	row = []
	for (j, ch) in enumerate(string):
		if int(ch) == (i + j) % 2:
			row.append(0)
		else:
			row.append(1)
	grid.append(row)
for i in range(1, n):
	grid[i][0] += grid[i - 1][0]
for j in range(1, m):
	grid[0][j] += grid[0][j - 1]
for i in range(1, n):
	for j in range(1, m):
		grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1]
flips = []
for l in range(min(n, m), 0, -1):
	f = l * l
	for i in range(n - l + 1):
		for j in range(m - l + 1):
			total = grid[i + l - 1][j + l - 1]
			if i > 0:
				total -= grid[i - 1][j + l - 1]
			if j > 0:
				total -= grid[i + l - 1][j - 1]
			if i > 0 and j > 0:
				total += grid[i - 1][j - 1]
			f = min(f, l * l - total, total)
	flips.append(f)
flips.reverse()
q = int(input())
qs = list(map(int, input().split()))
for i in qs:
	print(bisect(flips, i))


(n, m) = input().split(' ')
n = int(n)
m = int(m)
lst = [None] * n
for i in range(0, n):
	lst[i] = input()
c1 = [[0 for x in range(m + 2)] for y in range(n + 2)]
c2 = [[0 for x in range(m + 2)] for y in range(n + 2)]
c3 = [[0 for x in range(m + 2)] for y in range(n + 2)]
c4 = [[0 for x in range(m + 2)] for y in range(n + 2)]
a = 1
b = 0
cn1 = 0
cn2 = 0
cn3 = 0
for i in range(n):
	if i % 2 == 0:
		a = 1
	else:
		a = 0
	if i % 2 == 0:
		b = 0
	else:
		b = 1
	for j in range(m):
		x = int(lst[i][j])
		if x != a:
			if j == 0:
				c1[i][j] = 1
			else:
				c1[i][j] = c1[i][j - 1] + 1
		elif j != 0:
			c1[i][j] = c1[i][j - 1]
		if x != b:
			if j == 0:
				c2[i][j] = 1
			else:
				c2[i][j] = c2[i][j - 1] + 1
		elif j != 0:
			c2[i][j] = c2[i][j - 1]
		if a == 0:
			a = 1
		else:
			a = 0
		if b == 0:
			b = 1
		else:
			b = 0
for i in range(m):
	c3[0][i] = c1[0][i]
	c4[0][i] = c2[0][i]
for i in range(1, n):
	for j in range(m):
		c3[i][j] = c3[i - 1][j] + c1[i][j]
		c4[i][j] = c4[i - 1][j] + c2[i][j]
query = [99999999] * 2000
query[0] = 0
for x in range(1, min(m, n)):
	for i in range(x, n):
		for j in range(x, m):
			query[x] = min(query[x], c3[i][j] - c3[i - x - 1][j] - (c3[i][j - x - 1] - c3[i - x - 1][j - x - 1]), c4[i][j] - c4[i - x - 1][j] - (c4[i][j - x - 1] - c4[i - x - 1][j - x - 1]))
q = input()
q = int(q)
arr = [int(x) for x in input().split(' ')]
for i in range(0, q):
	if arr[i] >= query[min(m, n) - 1]:
		print(min(m, n))
	else:
		for j in range(min(m, n) - 1, -1, -1):
			if arr[i] >= query[j]:
				break
		print(j + 1)


import sys, time, bisect
try:
	sys.stdin = open('inp', 'r')
except:
	pass

class prefix_sum:

	def __init__(self, a):
		(R, C) = (len(a), len(a[0]))
		td = [[0 for x in range(C)] for y in range(R)]
		td[0][0] = a[0][0]
		for i in range(1, C):
			td[0][i] = td[0][i - 1] + a[0][i]
		for i in range(1, R):
			td[i][0] = td[i - 1][0] + a[i][0]
		for i in range(1, R):
			for j in range(1, C):
				td[i][j] = td[i - 1][j] + td[i][j - 1] - td[i - 1][j - 1] + a[i][j]
		self.td = td

	def query(self, x1, y1, x2, y2):
		(x1, y1) = (x1 - 1, y1 - 1)
		left = self.td[x2][y1] if y1 >= 0 else 0
		top = self.td[x1][y2] if x1 >= 0 else 0
		incl = self.td[x1][y1] if x1 >= 0 and y1 >= 0 else 0
		return self.td[x2][y2] - left - top + incl

	def __str__(self):
		return '\n'.join((' '.join(map(str, i)) for i in self.td))
(n, m) = map(int, input().split())
board = []
for _ in range(n):
	board.append([int(x) for x in input()])
(r, c) = (n, m)
(bw, wb) = ([[0 for i in range(c)] for j in range(r)], [[0 for i in range(c)] for j in range(r)])
for i in range(r):
	for j in range(c):
		loc = i + j
		if loc & 1 == 0:
			wb[i][j] = 0 if board[i][j] == 0 else 1
			bw[i][j] = 1 ^ wb[i][j]
		else:
			wb[i][j] = 0 if board[i][j] == 1 else 1
			bw[i][j] = 1 ^ wb[i][j]
pwb = prefix_sum(wb)
pbw = prefix_sum(bw)
res = {}
mx = min(r, c)
for i in range(r):
	for j in range(c):
		for k in range(mx):
			if i + k >= r or j + k >= c:
				break
			res[k] = min(res.get(k, 50000), pwb.query(i, j, i + k, j + k), pbw.query(i, j, i + k, j + k))
ans = {}
for (k, v) in res.items():
	ans[v] = max(ans.get(v, 0), k + 1)
moves = [k for k in ans.keys()]
moves.sort()
input()
for q in map(int, input().split()):
	try:
		ind = bisect.bisect_left(moves, q)
		if ind >= len(moves) or moves[ind] > q:
			ind -= 1
		print(ans[moves[ind]])
	except:
		print('1')