#include <bits/stdc++.h>
#include <vector>
#include <algorithm>

const int MAXCOORD = 5001;

struct Coord
{
    int x;
    int y;
};

int main()
{
    int guardCount;
    int enemyCount;
    std::vector<int> YsByX[MAXCOORD];
    std::vector<int> XsByY[MAXCOORD];


    scanf("%d %d", &guardCount, &enemyCount);

    for(int i = 0; i < guardCount; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);

        YsByX[x].push_back(y);
        XsByY[y].push_back(x);
    }

    for(int i = 0; i < MAXCOORD; i++)
    {
        std::vector<int>& v = YsByX[i];
        if(v.size() > 1)
        {
            sort(v.begin(), v.end());
        }
    }
    for(int i = 0; i < MAXCOORD; i++)
    {
        std::vector<int>& v = XsByY[i];
        if(v.size() > 1)
        {
            sort(v.begin(), v.end());
        }
    }

    for(int e = 0; e < enemyCount; e++)
    {
        int x, y;
        scanf("%d %d", &x, &y);

        std::vector<int> v;
        std::vector<int>::iterator it;
        int dist = 0;
        v = YsByX[x];
        if(!binary_search(v.begin(), v.end(), y)) // kdyz neni na tom samem miste, hledam dal
        {
            while(true)
            {
                dist++;

                if(x + dist < MAXCOORD)
                {
                    v = YsByX[x + dist];
                    if(v.size() > 0)
                    {
                        it = std::lower_bound(v.begin(), v.end(), y - dist);
                        if(it != v.end() && *it <= y + dist)
                        {
                            //printf("A\n");
                            break;
                        }
                    }
                }
                if(x - dist >= 0)
                {
                    v = YsByX[x - dist];
                    if(v.size() > 0)
                    {
                        it = std::lower_bound(v.begin(), v.end(), y - dist);
                        if(it != v.end() && *it <= y + dist)
                        {
                            //printf("B\n");
                            break;
                        }
                    }
                }
                if(y + dist < MAXCOORD)
                {
                    v = XsByY[y + dist];
                    if(v.size() > 0)
                    {
                        it = std::lower_bound(v.begin(), v.end(), x - dist);
                        if(it != v.end() && *it <= x + dist)
                        {
                            //printf("C\n");
                            break;
                        }
                    }
                }
                if(y - dist >= 0)
                {
                    v = XsByY[y - dist];
                    if(v.size() > 0)
                    {
                        it = std::lower_bound(v.begin(), v.end(), x - dist);
                        if(it != v.end() && *it <= x + dist)
                        {
                            //printf("D\n");
                            break;
                        }
                    }
                }
            }
        }

        printf("%d\n", dist);
    }




    return 0;
}