#include <iostream>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

struct coordinates {
	int x = 0;
	int y = 0;
};

struct Compare {
    bool operator()( const coordinates & a, const coordinates & b) const {
    	int distA = a.x * a.x + a.y * a.y;
    	int distB = b.x * b.x + b.y * b.y;
    	return distA < distB;
    /*
    	if ( a.x == b.x )
    		return a.y < b.y;   	
    	else
    		return a.x < b.x;
    		*/
    }
};
struct Compare2 {
    bool operator()( const coordinates & a, const coordinates & b) const {
    	int distA = a.x * a.x + a.y * a.y;
    	int distB = b.x * b.x + b.y * b.y;
    	return distA > distB;
    /*
    	if ( a.x == b.x )
    		return a.y < b.y;   	
    	else
    		return a.x < b.x;
    		*/
    }
};

int main ( void )
{
	// cout << "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<" << endl;
	int num_guards, num_incidents;
	cin >> num_guards >> num_incidents;
	
	set<coordinates, Compare> guards1;
	set<coordinates, Compare2> guards2;
	for ( int i = 0; i < num_guards; ++i ) {
		coordinates guard;
		cin >> guard.x >> guard.y;	
		// int max = std::max (guard.x, guard.y);
		guards1.insert(guard);
		guards2.insert(guard);
	}	
	/*
	for ( auto i = guards.begin(); i != guards.cend(); ++i )
		cout << "[" << i -> x << ", " << i -> y << "]\n";
	cout << endl;
	*/
	for ( int i = 0; i < num_incidents; ++i ) {
		coordinates incident;
		cin >> incident.x >> incident.y;	
		// int max = std::max (incident.x, incident.y);
		// cout << "Incident: [" << incident.x << ", " << incident.y << "]\n";
		//auto lower = std::lower_bound(guards.begin(), guards.end(), incident, Compare());
    	//auto upper = std::lower_bound(guards.begin(), guards.end(), incident, Compare2());
    	auto lower = guards1.lower_bound(incident);
    	auto upper = guards2.upper_bound(incident);
    	/*
    	auto upper = std::set.lower_bound(guards.begin(), guards.end(), incident, Compare());
		if ( lower == guards.cend() ) {
			--lower;
			upper = lower;
		}	else {
			--upper;
		}
		*/
		if ( upper == guards2.cend() )
			--upper;
		if ( lower == guards1.cend() )
			--lower;
    	// cout << "Lower: [" << lower -> x << ", " << lower -> y << "]\n";
    	// cout << "Upper: [" << upper -> x << ", " << upper -> y << "]\n";
    	// cout << endl;
    	
    	pair<int, int> res1 = make_pair(abs((lower -> x) - incident.x), abs((lower -> y) - incident.y));
    	pair<int, int> res2 = make_pair(abs((upper -> x) - incident.x), abs((upper -> y) - incident.y));
    	int max1 = std::max(res1.first, res1.second);
    	int max2 = std::max(res2.first, res2.second);
    	int result = std::min(max1, max2);
    	cout << result << endl;
	}
	
	
	
	
	
	return 0;
}