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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'n,m=list(map(int,input().split()))\r\ngrid=[ list(map(int,list(input()))) for i in range(n)]\r\nobs0=[ [ 0 for j in range(m)] for i in range(n)] \r\nobs1=[ [ 0 for j in range(m)] for i in range(n) ]\r\nmax_side=min(m,n)\r\nside_c=[ 40000 for i in range(max_side+1)]\r\nside_c[0]=0\r\nside_c[1]=0\r\n#print(grid)\r\nfor i in range(n):\r\n\tfor j in range(m):\r\n\t\tif (i+j)%2==0:\r\n\t\t\tobs0[i][j]=0\r\n\t\t\tobs1[i][j]=1\r\n\t\telse:\r\n\t\t\tobs0[i][j]=1\r\n\t\t\tobs1[i][j]=0\r\n#print(obs0)\r\n#print(obs1)\r\nfor i in range(n):\r\n\tfor j in range(m):\r\n\t\tif obs0[i][j]!=grid[i][j]:\r\n\t\t\tobs0[i][j]=1\r\n\t\telse:\r\n\t\t\tobs0[i][j]=0\r\n\t\tif obs1[i][j]!=grid[i][j]:\r\n\t\t\tobs1[i][j]=1\r\n\t\telse:\r\n\t\t\tobs1[i][j]=0\r\n#print(obs0)\r\n#print(obs1)\r\n\r\nfor i in range(n):\r\n\tfor j in range(1,m):\r\n\t\tobs0[i][j]+=obs0[i][j-1]\r\n\t\tobs1[i][j]+=obs1[i][j-1]\r\nfor j in range(m):\r\n\tfor i in  range(1,n):\r\n\t\tobs0[i][j]+=obs0[i-1][j]\r\n\t\tobs1[i][j]+=obs1[i-1][j]\r\nfor side in range(2,max_side+1):\r\n\tfor i in range(n):\r\n\t\tfor j in range(m):\r\n\t\t\tif i+side>n or j+side>m:\r\n\t\t\t\tcontinue\r\n\t\t\tcount0 = 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] \r\n\t\t\tcount1 = 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]\r\n\t\t\tside_c[side]=min(count0,count1,side_c[side])\r\ninput()\r\n#print(side_c)\r\n#print(*obs0,sep="\\n")\r\n#print(*obs1,sep="\\n")\r\nlist_c=list(map(int,input().split()))\r\nfor i in range(len(list_c)):\r\n\tc=list_c[i]\r\n\tanswer=1\r\n\tfor side in range(2,max_side+1):\r\n\t\tif c<side_c[side]:\r\n\t\t\tanswer=side-1\r\n\t\t\tbreak\r\n\tif c>=side_c[max_side]:\r\n\t\tanswer=max_side\r\n\tprint(answer)\r\n\r\n\r\n\r\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14893