#include <bits/stdc++.h>
using namespace std;

#define llong long long 
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#ifdef testing
mt19937 rng(177013);
#else
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
#endif
#define rand() (int)(rng() >> 1)
#define CONCAT_(x, y) x##y/*{{{*/
#define CONCAT(x, y) CONCAT_(x, y)
#define SPEC(name) CONCAT(name, __LINE__)
#ifdef LOCAL_DEBUG   
int __db_level = 0;
#define clog cerr << string(__db_level * 2, ' ')
struct debug_block {
    string msg;
    debug_block(const string& s): msg(s) { clog << "{ " << msg << endl; ++__db_level; }
    ~debug_block() { --__db_level; clog << "} " << msg << endl; }
};
#define DB(args...) stringstream SPEC(ss); SPEC(ss)<< args; debug_block SPEC(dbbl)(SPEC(ss).str())
#else
#define clog if (0) cerr
#define DB(...)
#endif
#define db(val) "[" #val " = " << val << "]; "
template<class U, class V> ostream& operator<<(ostream& out, const pair<U, V>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")";
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup);
}
template<class ...U>
ostream& operator<<(ostream& out, const tuple<U...>& tup) { return print_tuple_utils<0, tuple<U...>>(out, tup); }
template<class, typename = void> struct has_const_iterator : false_type {};
template<class T> struct has_const_iterator<T, void_t<typename T::const_iterator>> : true_type {};
template<class T>
typename enable_if<has_const_iterator<T>::value && !is_same<T, string>::value, ostream&>::type
operator<<(ostream& out, const T& container) { 
    auto beg = container.begin(), end = container.end();
    out << "(" << container.size() << ") {";
    if (beg != end) out << *(beg++);
    while (beg != end) out << ", " << *(beg++);
    return out << "}";
}
#define ptrtype(x) typename iterator_traits<x>::value_type
template<class u> vector<ptrtype(u)> $v(u a, u b) { return vector<ptrtype(u)>(a, b); }/*}}}*/
// ACTUAL SOLUTION START HERE ////////////////////////////////////////////////////////////////

int getnum() {
    int ch;
    while (!isdigit(ch = getchar()) and ch != '-') {
        if (ch == -1) return 0;
    }
    int sign = ch == '-' ? -1 : 1;
    int ans = ch == '-' ? 0 : ch - '0';
    while (isdigit(ch = getchar())) ans = ans * 10 + ch - '0';
    // clog << ans << endl; 
    return ans * sign;
}

struct Point {
    int x, y;
    Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}
    friend ostream& operator<<(ostream& out, const Point& u) {
        return out << "(" << u.x << ", " << u.y << ")";
    }
};

struct PointI {
    int x, y, id;
    PointI(int x_ = 0, int y_ = 0, int i = -1) : x(x_), y(y_), id(i) {}
    friend ostream& operator<<(ostream& out, const PointI& u) {
        return out << "(" << u.x << ", " << u.y << ", " << u.id << ")";
    }
};
int n, m;
vector<Point> poly; 
vector<PointI> queries;
bool read() {
    n = getnum();
    if (feof(stdin)) return false;
    m = getnum();
    poly.resize(n);
    queries.resize(m);
    for (auto& [x, y]: poly) {
        x = getnum();
        y = getnum();
    }
    int id = 0;
    for (auto& [x, y, i]: queries) {
        x = getnum();
        y = getnum();
        i = id++;
    }
    return true;
}

int l2(int num) {
    return 31 - __builtin_clz(num);
}

void tle_assert(bool x) {
#ifndef LOCAL
    while (!x);
#endif
}

vector<llong> combine(vector<llong> u, const vector<llong>& v) {
    rep(i, len(u)) u[i] = min(u[i], v[i]);
    return u;
}

vector<llong> min_hor() {
    vector<pair<llong, llong>> upd;
    vector<PointI> qr;
    auto prev = poly.back();
    for (auto cur: poly) {
        if (cur.y == prev.y) {
            upd.emplace_back(cur.y, cur.x);
            upd.emplace_back(prev.y, prev.x);
        }
        prev = cur;
    }
    
    for (auto [x, y, id]: queries) qr.emplace_back(y, x, id);
    sort(upd.begin(), upd.end());
    sort(qr.begin(), qr.end(), [&](const PointI& u, const PointI& v) { return u.x < v.x; });
    vector<llong> ans(m);
    set<llong> ranges;
    int ptr = 0;
    for (auto [qpos, qpoint, id]: qr) {
        while (ptr < len(upd)) {
            auto [upos, endpoint] = upd[ptr];
            if (upos > qpos) break;
            ++ptr;
            if (ranges.count(endpoint)) ranges.erase(endpoint);
            else ranges.insert(endpoint);
        }
        ans[id] = *ranges.upper_bound(qpoint) - qpoint;
    }
    return ans;
}

vector<llong> min_hor_diag() {
    vector<llong> y_vals;
    for (auto& [x, y, id]: queries) y_vals.push_back(y);
    sort(y_vals.begin(), y_vals.end());
    y_vals.erase(unique(y_vals.begin(), y_vals.end()), y_vals.end());
    auto index = [&](llong val) {
        return (int)(lower_bound(y_vals.begin(), y_vals.end(), val) - y_vals.begin());
    };
    vector<vector<PointI>> qr(2 * m);
    vector<vector<pair<llong, llong>>> upd(2 * m);
    
    sort(queries.rbegin(), queries.rend(), [](const PointI& u, const PointI& v) {
            return u.x - u.y < v.x - v.y;
            });
    for (auto p: queries) {
        int i = index(p.y);
        for (i += m; i > 0; i >>= 1) 
            qr[i].push_back(p);
    }
    
    vector<Point> precal_upd;
    auto prev = poly.back();
    for (auto cur: poly) {
        if (prev.y != cur.y) {
            precal_upd.emplace_back(prev.x, prev.y);
        }
        prev = cur;
    }
    sort(precal_upd.rbegin(), precal_upd.rend(), [&](const auto& u, const auto& v) {
            return u.x - u.y < v.x - v.y;
            });
    
    for (auto [x, y]: precal_upd) {
        llong diff = x - y;
        int l = m, r = index(y + 1) + m;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) upd[l++].emplace_back(diff, x);
            if (r & 1) upd[--r].emplace_back(diff, x);
        }
    }
    
    vector<llong> ans(m, INT_MAX);
    for (int root = 1; root < 2 * m; ++root) {
        if (!len(qr[root]) or !len(upd[root])) continue;
        llong cur_min_x = INT_MAX;
        int ptr = 0;
        for (auto [x, y, id]: qr[root]) {
            llong cur_diff = x - y;
            while (ptr < len(upd[root])) {
                auto [diff, px] = upd[root][ptr];
                if (diff < cur_diff) break;
                ++ptr;
                cur_min_x = min(cur_min_x, px);
            }
            ans[id] = min(ans[id], cur_min_x - x);
        }
    }
    return ans;
}

vector<llong> solve_single_axis() {
    return combine(min_hor(), min_hor_diag());
}

vector<llong> solve() {
    auto ans = solve_single_axis();
    for (auto& [x, y]: poly) swap(x, y);
    for (auto& [x, y, id]: queries) swap(x, y);
    reverse(poly.begin(), poly.end());
    // cout << "Polygon" << endl; 
    // for (auto [x, y]: poly) { 
        // cout << x << ' ' << y << endl; 
    // } 
    // cout << endl; 
    
    return combine(ans, solve_single_axis());
}

int main(void) {
#ifdef LOCAL
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
    freopen(".log", "w", stderr);
#endif
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    while (read()) {
        auto ans = solve();
        for (auto i: ans) cout << i << '\n';
    }
    
    return 0;
}

// vim: foldmethod=marker