#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
    vector <int> guardX;
    vector <int> guardY;
    vector <int> problemX;
    vector <int> problemY;

    int coGuards;
    int coProblems;
    int pom;

    cin >> coGuards;
    cin >> coProblems;

    for(int i=0;i<coGuards;i++)
    {
        cin >> pom;
        guardX.push_back(pom);
        cin >> pom;
        guardY.push_back(pom);
    }

    for(int i=0;i<coProblems;i++)
    {
        cin >> pom;
        problemX.push_back(pom);
        cin >> pom;
        problemY.push_back(pom);
    }

    int pomX;
    int pomY;
    for(int j=0;j<coProblems;j++)
    {
        for(int i=0;i<coGuards;i++)
        {
            pomX=guardX[i]-problemX[j];
            pomY=guardY[i]-problemY[j];

            if(pomX<0)
            {
                pomX=-pomX;
            }
            if(pomY<0)
            {
                pomY=-pomY;
            }

            if(pomX>pomY)
            {
                if(i==0)
                {
                    pom=pomX;
                    continue;
                }

                if(pom>pomX)
                {
                    pom=pomX;
                }
            }
            else if(pomY>=pomX)
            {
                if(i==0)
                {
                    pom=pomX;
                    continue;
                }

                if(pom>=pomY)
                {
                    pom=pomY;
                }
            }
        }

        cout << pom << "\n";
    }




    return 0;
}