@staticmethod
def d():
    n = int(sys.stdin.readline().rstrip())
    d = np.array([sys.stdin.readline().split() for _ in range(n)], np.int64)
    s = d.cumsum(axis=0).cumsum(axis=1)
    s = np.pad(s, 1)
    max_del = np.zeros(((n + 1), (n + 1)), dtype=np.int64)
    for y in range(1, (n + 1)):
        for x in range(1, (n + 1)):
            max_del[(y, x)] = np.amax((((s[y:(n + 1), x:(n + 1)] - s[0:((n - y) + 1), x:(n + 1)]) - s[y:(n + 1), 0:((n - x) + 1)]) + s[0:((n - y) + 1), 0:((n - x) + 1)]))
    res = np.arange(((n ** 2) + 1))[:, None]
    i = np.arange(1, (n + 1))
    res = max_del[(i, np.minimum((res // i), n))].max(axis=1)
    q = int(sys.stdin.readline().rstrip())
    p = np.array(sys.stdin.read().split(), dtype=np.int64)
    print(*res[p], sep='\n')
@staticmethod
def d():
    n = int(sys.stdin.readline().rstrip())
    d = np.array([sys.stdin.readline().split() for _ in range(n)], np.int64)
    s = d.cumsum(axis=0).cumsum(axis=1)
    s = np.pad(s, 1)
    max_del = np.zeros(((n + 1), (n + 1)), dtype=np.int64)
    for y in range(1, (n + 1)):
        for x in range(1, (n + 1)):
            max_del[(y, x)] = np.amax((((s[y:(n + 1), x:(n + 1)] - s[0:((n - y) + 1), x:(n + 1)]) - s[y:(n + 1), 0:((n - x) + 1)]) + s[0:((n - y) + 1), 0:((n - x) + 1)]))
    res = np.arange(((n ** 2) + 1))[:, None]
    i = np.arange(1, (n + 1))
    res = max_del[(i, np.minimum((res // i), n))].max(axis=1)
    q = int(sys.stdin.readline().rstrip())
    p = np.array(sys.stdin.read().split(), dtype=np.int64)
    print(*res[p], sep='\n')