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

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


    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)
                {
                    steps.push_back(pomX);
                }
                else
                {
                    if(pomX<steps[j])
                    {
                        steps[j]=pomX;
                    }
                }
            }
            else if(pomY>pomX)
            {
                if(i==0)
                {
                    steps.push_back(pomY);
                }
                else
                {
                    if(pomY<steps[j])
                    {
                        steps[j]=pomY;
                    }
                }
            }
            else if(pomY==pomX)
            {
                if(i==0)
                {
                    steps.push_back(pomY);
                }
                else
                {
                    if(pomY<steps[j])
                    {
                        steps[j]=pomY;
                    }
                }
            }
        }
    }

    for(int i=0;i<steps.size();i++)
    {
        cout << steps[i] << endl;
    }



    return 0;
}