n, q = map(int, input().split())

coords = []
for _ in range(n):
    x, y = map(int, input().split())
    coords.append((x, y))

zone = []
for _ in range(q):
    a, b = map(int, input().split())
    zone.append((a, b))


def f(a, b, lst):
    if b - a <= 1:
        return 0

    # minimum of the first 3
    aXmin = min(lst[a][0], lst[a+1][0])
    aXmax = max(lst[a][0], lst[a+1][0])
    aYmin = min(lst[a][1], lst[a+1][1])
    aYmax = max(lst[a][1], lst[a+1][1])
    aLen = max(abs(aXmax-aXmin), abs(aYmax-aYmin))

    bXmin = min(lst[a + 2][0], lst[a + 1][0])
    bXmax = max(lst[a + 2][0], lst[a + 1][0])
    bYmin = min(lst[a + 2][1], lst[a + 1][1])
    bYmax = max(lst[a + 2][1], lst[a + 1][1])
    bLen = max(abs(bXmax - bXmin), abs(bYmax - bYmin))

    cXmin = min(lst[a][0], lst[a + 2][0])
    cXmax = max(lst[a][0], lst[a + 2][0])
    cYmin = min(lst[a][1], lst[a + 2][1])
    cYmax = max(lst[a][1], lst[a + 2][1])
    cLen = max(abs(cXmax - cXmin), abs(cYmax - cYmin))

    if(aLen < bLen):
        if(aLen < cLen):
            osXmin = aXmin
            osXmax = aXmax
            osYmin = aYmin
            osYmax = aYmax
            osLen = aLen
        else:
            osXmin = cXmin
            osXmax = cXmax
            osYmin = cYmin
            osYmax = cYmax
            osLen = cLen
    else:
        if (bLen < cLen):
            osXmin = bXmin
            osXmax = bXmax
            osYmin = bYmin
            osYmax = bYmax
            osLen = bLen
        else:
            osXmin = cXmin
            osXmax = cXmax
            osYmin = cYmin
            osYmax = cYmax
            osLen = cLen

    nsLen = osLen
    allXmin = min(aXmin, lst[a+2][0])
    allXmax = max(aXmax, lst[a+2][0])
    allYmin = min(aYmin, lst[a+2][1])
    allYmax = max(aYmax, lst[a+2][1])
    allLen = max(abs(allXmax-allXmin), abs(allYmax-allYmin))
    # print(f"nsLen={nsLen}, osLen={osLen}, allLen={allLen}")

    for i in lst[a + 3:b + 1]:
        osXmin = min(osXmin, i[0])
        osXmax = max(osXmax, i[0])
        osYmin = min(osYmin, i[1])
        osYmax = max(osYmax, i[1])
        osLen = max(abs(osXmax - osXmin), abs(osYmax - osYmin))

        nsXmin = allXmin
        nsXmax = allXmax
        nsYmin = allYmin
        nsYmax = allYmax
        nsLen = allLen
        # print(f"nsLen={nsLen}, osLen={osLen}, allLen={allLen}")

        allXmin = min(allXmin, i[0])
        allXmax = max(allXmax, i[0])
        allYmin = min(allYmin, i[0])
        allYmax = max(allYmax, i[0])
        allLen = max(abs(allXmax - allXmin), abs(allYmax - allYmin))

        # print(f"nsLen={nsLen}, osLen={osLen}, allLen={allLen}")
        if (nsLen < osLen):
            osXmin = nsXmin
            osXmax = nsXmax
            osYmin = nsYmin
            osYmax = nsYmax

    return nsLen


for a, b in zone:
    print(f(a-1, b-1, coords))