#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int result[2];
    cin >> result[0];
    cin >> result[1];

    int guards[result[0]][2];
    int incidents[result[1]][2];

    for (int i = 0; i < result[0]; i++){
        cin >> guards[i][0];
        cin >> guards[i][1];
    }

    for (int i = 0; i < result[1]; i++){
        cin >> incidents[i][0];
        cin >> incidents[i][1];
    }

    int tmp[2] = {0,0};
    int tmpResult;
    int minimalSteps = 5500;

    for(int i = 0; i < result[1]; i++){
        for(int j = 0; j < result[0]; j++){
           tmp[0] = abs(incidents[i][0] - guards[j][0]);

           if(tmp[0] >= minimalSteps){
                continue;
           }

           tmp[1] = abs(incidents[i][1] - guards[j][1]);

           if(tmp[1] >= minimalSteps){
                continue;
            }


           if(tmp[0] > tmp[1]){
                tmpResult = tmp[0];
           }
           else tmpResult = tmp[1];

           if(minimalSteps > tmpResult){
                minimalSteps = tmpResult;
           }
        }
        cout << minimalSteps << endl;
        minimalSteps = 5500;
    }

    return 0;
}