human
Convenience store Deven Eleven is planning to open its first store in Aizuwakamatsu City to expand its business. There are already many other convenience stores in Aizuwakamatsu, so the place to open a new store is likely to be the key to success. Under the premise that "customers use the convenience store closest to the area where they live," Seven Eleven has decided to open a store at "a point that many customers will use."

| 
--- | ---

Seven Eleven has divided the map of Aizuwakamatsu City using a congruent regular hexagon (hereinafter referred to as "block") in order to grasp the range covered by each existing convenience store. At this time, each block was divided so that there was at most one existing convenience store. On this map, the distance to the convenience store is calculated based on the number of blocks that go through from each block to the convenience store. We believe that each block is covered by the convenience store with the shortest distance. The problem is to look for "a block without an existing convenience store that covers as many blocks as possible" based on this map.

As a Deven-Eleven programmer, you have decided to develop a program that calculates the number of blocks that can be covered most widely from the block-divided map information and the information on the candidate sites for new stores.

The map divided into m x n is shown as shown in Fig. 1. There are m hexagonal blocks horizontally and n vertically, each represented by one coordinate (x, y). The left edge of the odd row is located at the bottom left of the left edge of the row above it, and the left edge of the even row is located at the bottom right of the left edge of the row above it. For example, the coordinates (1, 1) indicate the upper left block in Figure 1. Also, the coordinates (1, 2) are located at the lower right of the coordinates (1, 1), and the coordinates (1, 3) are located at the lower left of the coordinates (1, 2).



Figure 2 shows an example of the case where there are 6 existing...
The above is tricky. Write me a correct solution in PYTHON.
assistant
#Here is the Python code you requested.

#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min_cover[y][x]:
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)
 
while True:
    try:
        data = raw_input()
        if data == "0":
            break
        m, n = map(int, data.split())
        s = input()
        spos = [map(int, raw_input().split()) for _ in xrange(s)]
        t = input()
        tpos = [map(int, raw_input().split()) for _ in xrange(t)]
        print solve()
    except:
        break