#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

struct Point
{
public:
	Point(int x = 0, int y = 0) : x(x), y(y)
	{
	}

	bool IsInRange(int x_min, int x_max, int y_min, int y_max) const
	{
		return (x >= x_min) && (x <= x_max) && (y >= y_min) && (y <= y_max);
	}

	int x;
	int y;
};

class Node
{
public:
	Node(int x_min = 0, int x_max = 0, int y_min = 0, int y_max = 0) :
		x_min(x_min), x_max(x_max), y_min(y_min), y_max(y_max),
		nodes(4, NULL)
	{
	}

	~Node()
	{
		for (Node* p : nodes)
			delete p;
	}

	void Insert(int x, int y)
	{
		if (IsTerminal()) {
			points_.emplace_back(x, y);
			return;
		}

		auto x_mid = (x_min + x_max) / 2;
		auto y_mid = (y_min + y_max) / 2;

		if (x < x_mid) {
			if (y < y_mid)
				InsertIntoRegion(0, x_min, x_mid - 1, y_min, y_mid - 1, x, y);
			else
				InsertIntoRegion(1, x_min, x_mid - 1, y_mid, y_max, x, y);
		}
		else {
			if (y < y_mid)
				InsertIntoRegion(2, x_mid, x_max, y_min, y_mid - 1, x, y);
			else
				InsertIntoRegion(3, x_mid, x_max, y_mid, y_max, x, y);
		}
	}

	void RangeQuery(int q_x_min, int q_x_max, int q_y_min, int q_y_max,
		vector<Point>& points)
	{
		if (q_x_max < x_min)
			return;
		if (q_x_min > x_max)
			return;
		if (q_y_max < y_min)
			return;
		if (q_y_min > y_max)
			return;

		if (IsTerminal()) {
			for (const auto& p : points_) {
				if (p.IsInRange(q_x_min, q_x_max, q_y_min, q_y_max))
					points.push_back(p);
			}
		}
		else {
			for (auto node : nodes) {
				if (node != NULL)
					node->RangeQuery(q_x_min, q_x_max, q_y_min, q_y_max, points);
			}
		}
	}

private:
	bool IsTerminal()
	{
		return min(abs(x_min - x_max), abs(y_min - y_max)) < 50;
	}

	void InsertIntoRegion(int reg_id,
		int min_x, int max_x, int min_y, int max_y, int x, int y)
	{
		if (nodes[reg_id] == NULL)
			nodes[reg_id] = new Node(min_x, max_x, min_y, max_y);
		nodes[reg_id]->Insert(x, y);
	}

	int x_min;
	int x_max;
	int y_min;
	int y_max;
	vector<Node*> nodes;
	vector<Point> points_;
};

class QuadTree
{
public:
	QuadTree(int x_min, int x_max, int y_min, int y_max) :
		root(x_min, x_max, y_min, y_max)
	{
	}

	void Insert(int x, int y)
	{
		root.Insert(x, y);
	}

	void RangeQuery(int q_x_min, int q_x_max, int q_y_min, int q_y_max,
		vector<Point>& points)
	{
		root.RangeQuery(q_x_min, q_y_max, q_y_min, q_y_max, points);
	}

private:
	Node root;
};

int main()
{
	ios_base::sync_with_stdio(false);

	int quards_no, fights_no;
	cin >> quards_no >> fights_no;
	QuadTree tree(0, 5000, 0, 5000);

	for (int i = 0; i < quards_no; ++i) {
		int x, y;
		cin >> x >> y;
		tree.Insert(x, y);
	}

	int range = 50;
	vector<Point> quards;
	quards.reserve(quards_no);

	for (int i = 0; i < fights_no; ++i) {
		int x, y;
		cin >> x >> y;

		while (true)
		{
			quards.clear();
			int q_x_min = x - range;
			int q_x_max = x + range;
			int q_y_min = y - range;
			int q_y_max = y + range;
			tree.RangeQuery(q_x_min, q_x_max, q_y_min, q_y_max, quards);

			int min_dist = numeric_limits<int>::max();
			for (const auto& p : quards) {
				auto d_x = abs(p.x - x);
				auto d_y = abs(p.y - y);
				auto dist = max(d_x, d_y);
				min_dist = min(min_dist, dist);
			}

			range += 50;
			if (!quards.empty()) {
				cout << min_dist << endl;
				break;
			}
		}
	}

	return 0;
}