#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <climits>
using namespace std;

//#define __TESTING__

int find( const vector<pair<int,int>> & vec, const pair<int,int> & searched ){

  auto it = lower_bound( vec.begin(), vec.end(), searched );
  int minimum;

  #ifdef __TESTING__
  auto it2 = it;
  if( it2 == vec.begin() ){
    //only one value
    cout << "Found:   " << it2 -> first << " " << it2 -> second << endl;
  }
  else if( it2 == vec.end() ){
    --it2;
    //minimum = make_pair
    cout << "Found:   " << it2 -> first << " " << it2 -> second << endl;
  }
  else{
    pair<int,int> sec_val;
    cout << "Found 2: " << it2 -> first << " " << it2 -> second << endl;
    --it2;
    cout << "         " << it2 -> first << " " << it2 -> second << endl;
  }
  #endif

  if( it == vec.begin() ){
    //only one value
    minimum = max( abs(it -> first - searched.first), abs(it -> second - searched.second ) );
  }
  else if( it == vec.end() ){
    --it;
    //minimum = make_pair
    minimum = max( abs(it -> first - searched.first), abs(it -> second - searched.second ) );
  }
  else{
    minimum = max( abs(it -> first - searched.first), abs(it -> second - searched.second ) );
    --it;
    int sec_minimum = 0;
    sec_minimum = max( abs( it -> first - searched.first), abs( it -> second - searched.second ) );
    if( sec_minimum < minimum )
      	minimum = sec_minimum;
    

  }

  return minimum;

}

int main( void ){

  int n,q;
  cin >> n >> q;

  set<pair<int,int>> setik;

  for( int i = 0; i < n; ++i ){
    int x,y;
    cin >> x >> y;
    setik.insert( make_pair( x, y ) );
  }

  /*
  vector<pair<int,int>> sort_x;
  vector<pair<int,int>> sort_y;
  sort_x.resize( n );
  sort_y.resize( n );

  for( int i = 0; i < n; ++i ){
    int x,y;
    cin >> x >> y;
    sort_x[i] = make_pair( x, y );
    sort_y[i] = make_pair( y, x );
  }
  
  sort( sort_x.begin(), sort_x.end() );
  sort( sort_y.begin(), sort_y.end() );*/

  map<pair<int,int>,int> mapicka;

  for( int asdf = 0; asdf < q; ++asdf ){
    int minimum = INT_MAX;
    int x,y;
    cin >> x >> y;
    auto it = mapicka.find( make_pair(x,y) );
    if( it == mapicka.end() ){
      for( auto it = setik.begin(); it != setik.end(); ++it ){
        int min_2 = max( abs(it -> first - x), abs(it -> second - y) );
        if( min_2 < minimum )
        	minimum = min_2;
      }
      mapicka.insert( make_pair( make_pair( x,y ), minimum ) );
      cout << minimum << endl;
    }
    else
      cout << it -> second << endl;

  }
  /*
  for( int i = 0; i < q; ++i ){
    int x,y;
    cin >> x >> y;
    
    int min1 = find( sort_x, make_pair( x, y ) );
    int min2 = find( sort_y, make_pair( y, x ) );
    if( min2 < min1 )
      cout << min2 << endl;
    else
      cout << min1 << endl;
  }*/


  return 0;
}