#include <iostream>
#include <vector>
#include <algorithm>
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;

  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() );

  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;
}