After hard work Igor decided to have some rest.

He decided to have a snail. He bought an aquarium with a slippery tree trunk in the center, and put a snail named Julia into the aquarium.

Igor noticed that sometimes Julia wants to climb onto the trunk, but can't do it because the trunk is too slippery. To help the snail Igor put some ropes on the tree, fixing the lower end of the i-th rope on the trunk on the height li above the ground, and the higher end on the height ri above the ground.

For some reason no two ropes share the same position of the higher end, i.e. all ri are distinct. Now Julia can move down at any place of the trunk, and also move up from the lower end of some rope to its higher end. Igor is proud of his work, and sometimes think about possible movements of the snail. Namely, he is interested in the following questions: «Suppose the snail is on the trunk at height x now. What is the highest position on the trunk the snail can get on if it would never be lower than x or higher than y?» Please note that Julia can't move from a rope to the trunk before it reaches the higher end of the rope, and Igor is interested in the highest position on the tree trunk.

Igor is interested in many questions, and not always can answer them. Help him, write a program that answers these questions.

Input

The first line contains single integer n (1 ≤ n ≤ 100000) — the height of the trunk.

The second line contains single integer m (1 ≤ m ≤ 100000) — the number of ropes.

The next m lines contain information about the ropes.

The i-th of these lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n) — the heights on which the lower and the higher ends of the i-th rope are fixed, respectively. It is guaranteed that all ri are distinct.

The next line contains single integer q (1 ≤ q ≤ 100000) — the number of questions.

The next q lines contain information about the questions.

Each of these lines contain two integers x and y (1 ≤ x ≤ y ≤ n), where x is the height where Julia starts (and the height Julia can't get lower than), and y is the height Julia can't get higher than.

Output

For each question print the maximum reachable for Julia height.

Examples

Input

8
4
1 2
3 4
2 5
6 7
5
1 2
1 4
1 6
2 7
6 8


Output

2
2
5
5
7


Input

10
10
3 7
1 4
1 6
5 5
1 1
3 9
7 8
1 2
3 3
7 10
10
2 4
1 7
3 4
3 5
2 8
2 5
5 5
3 5
7 7
3 10


Output

2
7
3
3
2
2
5
3
7
10

Note

The picture of the first sample is on the left, the picture of the second sample is on the right. Ropes' colors are just for clarity, they don't mean anything.

<image>
10
10
8 10
1 1
1 6
4 7
4 9
8 8
1 4
2 3
4 5
2 2
10
1 1
1 2
1 3
1 4
1 5
6 10
7 10
8 10
9 10
10 10
 1
1
1 1
1
1 1
 10
10
1 3
1 4
1 1
1 2
3 8
5 9
5 5
5 10
2 6
2 7
10
2 5
3 7
3 8
1 5
8 8
1 4
6 10
4 6
2 7
7 10
 5
5
1 3
1 4
2 2
3 5
1 1
5
1 3
3 5
4 5
1 4
4 5

1
1
1
4
5
6
7
10
9
10
 1
 2
3
8
4
8
4
6
4
7
7
 3
5
4
4
4

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios {
    fast_ios() { cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); };
} fast_ios_;
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
//
template <typename T, typename V>
void ndarray(vector<T>& vec, const V& val, int len) { vec.assign(len, val); }
template <typename T, typename V, typename... Args>
void ndarray(vector<T>& vec, const V& val, int len, Args... args)
{
    vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); });
}
template <typename T>
bool chmax(T& m, const T q) { return m < q ? (m = q, true) : false; }
template <typename T>
bool chmin(T& m, const T q) { return m > q ? (m = q, true) : false; }
template <typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first - r.first, l.second - r.second); }
template <typename T>
vector<T> srtunq(vector<T> vec) { return sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()), vec; }
template <typename T>
istream& operator>>(istream& is, vector<T>& vec)
{
    return for_each(begin(vec), end(vec), [&](T& v) { is >> v; }), is;
}

// output
template <typename T, typename V>
ostream& dmpseq(ostream&, const T&, const string&, const string&, const string&);
#if __cplusplus >= 201703L
template <typename... T>
ostream& operator<<(ostream& os, const tuple<T...>& tpl)
{
    return apply([&os](auto&&... args) { ((os << args << ','), ...); }, tpl), os;
}
#endif
//
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << '(' << p.first << ',' << p.second << ')'; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& x) { return dmpseq<vector<T>, T>(os, x, "[", ",", "]"); }
template <typename T>
ostream& operator<<(ostream& os, const deque<T>& x) { return dmpseq<deque<T>, T>(os, x, "deq[", ",", "]"); }
template <typename T>
ostream& operator<<(ostream& os, const set<T>& x) { return dmpseq<set<T>, T>(os, x, "{", ",", "}"); }
template <typename T, typename TH>
ostream& operator<<(ostream& os, const unordered_set<T, TH>& x) { return dmpseq<unordered_set<T, TH>, T>(os, x, "{", ",", "}"); }
template <typename T>
ostream& operator<<(ostream& os, const multiset<T>& x) { return dmpseq<multiset<T>, T>(os, x, "{", ",", "}"); }
template <typename TK, typename T>
ostream& operator<<(ostream& os, const map<TK, T>& x) { return dmpseq<map<TK, T>, pair<TK, T>>(os, x, "{", ",", "}"); }
template <typename TK, typename T, typename TH>
ostream& operator<<(ostream& os, const unordered_map<TK, T, TH>& x) { return dmpseq<unordered_map<TK, T, TH>, pair<TK, T>>(os, x, "{", ",", "}"); }
template <typename T, typename V>
ostream& dmpseq(ostream& os, const T& seq, const string& pre, const string& sp, const string& suf)
{
    return os << pre, for_each(begin(seq), end(seq), [&](V x) { os << x << sp; }), os << suf;
}
template <typename T>
void print(const vector<T>& x) { dmpseq<vector<T>, T>(cout, x, "", " ", "\n"); }
#ifdef HITONANODE_LOCAL
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl
#else
#define dbg(x)
#endif

// Nonrecursive Segment Tree (point-update, range-get)
// - Conditions for operations:
//   - merge_data: [TDATA, TDATA] -> TDATA, e(x, y) == e(y, x)
//   - data2ret: [TDATA, TQUERY] -> TRET
//   - merge_ret: [TRET, TRET] -> TRET, g(defaultRET, x) == x, g(x, y) = g(y, x)
//   - commutability f(e(x, y), q) == g(f(x, q), f(y, q))
template <typename TDATA, typename TRET, typename TQUERY>
struct NonrecursiveSegmentTree {
    int N;
    TRET defaultRET;
    virtual TDATA merge_data(const TDATA&, const TDATA&) = 0;
    virtual TRET data2ret(const TDATA&, const TQUERY&) = 0;
    virtual TRET merge_ret(const TRET&, const TRET&) = 0;
    std::vector<TDATA> data;
    inline TDATA& at(int i) { return data[i]; }

    inline void _merge(int i) { at(i) = merge_data(at(i << 1), at((i << 1) + 1)); }
    void initialize(const std::vector<TDATA>& seq, TRET RET_ZERO)
    {
        N = seq.size();
        defaultRET = RET_ZERO;
        data = seq;
        data.insert(data.end(), seq.begin(), seq.end());
        for (int i = N - 1; i; i--)
            _merge(i);
    }
    NonrecursiveSegmentTree() = default;
    void update(int pos, const TDATA& x)
    {
        assert(pos >= 0 and pos < N);
        at(pos + N) = x;
        for (int i = pos + N; i > 1;)
            i >>= 1, _merge(i);
    }

    // [l, r), 0-indexed
    TRET get(int l, int r, TQUERY query = NULL)
    {
        assert(l >= 0 and r <= N);
        TRET retl = defaultRET, retr = defaultRET;
        l += N, r += N;
        while (l < r) {
            if (l & 1)
                retl = merge_ret(retl, data2ret(data[l++], query));
            if (r & 1)
                retr = merge_ret(data2ret(data[--r], query), retr);
            l >>= 1, r >>= 1;
        }
        return merge_ret(retl, retr);
    }

    // Calculate smallest r that satisfies condition(g(f(x_l, q), ..., f(x_{r - 1}, q)) == true
    // Assumption: Monotonicity of g(x_l, ..., x_r) about r (l: fixed)
    // Complexity: O(log N)
    int binary_search(int l, auto condition, TQUERY query = NULL)
    {
        std::stack<int> rs;
        l += N;
        int r = N * 2;
        TRET retl = defaultRET;
        if (condition(retl))
            return l - N;
        while (l < r) {
            if (l & 1) {
                TRET ret_tmp = merge_ret(retl, data2ret(data[l], query));
                if (condition(ret_tmp)) {
                    while (l * 2 < N * 2) {
                        ret_tmp = merge_ret(retl, data2ret(data[l * 2], query));
                        if (condition(ret_tmp))
                            l *= 2;
                        else
                            retl = ret_tmp, l = l * 2 + 1;
                    }
                    return l - N;
                }
                l++;
                retl = ret_tmp;
            }
            if (r & 1)
                rs.push(--r);
            l >>= 1, r >>= 1;
        }
        while (!rs.empty()) {
            l = rs.top();
            rs.pop();
            TRET ret_tmp = merge_ret(retl, data2ret(data[l], query));
            if (condition(ret_tmp)) {
                while (l * 2 < N * 2) {
                    ret_tmp = merge_ret(retl, data2ret(data[l * 2], query));
                    if (condition(ret_tmp))
                        l *= 2;
                    else
                        retl = ret_tmp, l = l * 2 + 1;
                }
                return l - N;
            }
            retl = ret_tmp;
        }
        return N;
    }

    template <typename T1, typename T2, typename T3>
    friend std::ostream& operator<<(std::ostream& os, NonrecursiveSegmentTree<T1, T2, T3> s)
    {
        os << "[SegmentTree (len: " << s.N << ')';
        for (int i = 0; i < s.N; i++)
            os << s.at(i + s.N) << ',';
        os << "]";
        return os;
    }
};

// Range Maximum Query
// - get: return max(x_l, ..., x_{r - 1})
template <typename T>
struct RangeMaximumQuery : public NonrecursiveSegmentTree<T, T, bool> {
    using SegTree = NonrecursiveSegmentTree<T, T, bool>;
    T merge_data(const T& vl, const T& vr) override { return std::max(vl, vr); };
    T data2ret(const T& v, const bool& q) override { return v; }
    T merge_ret(const T& vl, const T& vr) override { return std::max(vl, vr); };
    RangeMaximumQuery(const std::vector<T>& seq, T defaultmax)
        : SegTree::NonrecursiveSegmentTree()
    {
        SegTree::initialize(seq, defaultmax);
    };
};

#ifdef HITONANODE_LOCAL
constexpr int B = 2;
#else
constexpr int B = 300;
#endif

int MAX = 100010 + B * 2;
int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> r2l(MAX, -1);
    REP(_, M)
    {
        int l, r;
        cin >> l >> r;
        r2l[r] = l;
    }
    int Q;
    cin >> Q;

    vector<vector<pint>> b2lr(MAX / B);
    vector<pint> queries;
    vector<pair<pint, int>> rets;
    REP(q, Q)
    {
        int x, y;
        cin >> x >> y;
        queries.emplace_back(x, y);
        if (y - x > B * 2) {
            b2lr[y / B].emplace_back(x, y);
        } else {
            vector<int> dp(y - x + 1);
            iota(ALL(dp), x);
            IFOR(i, x, y + 1)
            if (r2l[i] >= x) {
                chmax(dp[r2l[i] - x], i);
            }
            int arr = x;
            FOR(i, x, y + 1)
            if (i <= arr) {
                chmax(arr, dp[i - x]);
            }
            rets.emplace_back(pint(x, y), arr);
        }
    }
    REP(t, b2lr.size())
    {
        sort(ALL(b2lr[t]));
        const vector<pint>& qlrs = b2lr[t];
        if (qlrs.empty())
            continue;
        const int T = t * B;

        vector<int> hinit(T + B + 10, 0);
        iota(ALL(hinit), 0);
        RangeMaximumQuery<int> rmq(hinit, -1);

        int hnow = T;

        vector<pint> lastl2rs;
        FOR(i, T, T + B)
        if (r2l[i] != -1)
            lastl2rs.emplace_back(r2l[i], i);
        sort(ALL(lastl2rs));
        priority_queue<pint> pqlr;
        dbg(hnow);
        dbg(lastl2rs);
        for (auto [x, y] : qlrs) {
            
            while (hnow >= x) {
                if (r2l[hnow] != -1) {
                    pqlr.emplace(r2l[hnow], hnow);
                }
                while (pqlr.size() and pqlr.top().first == hnow) {
                    auto [l, r] = pqlr.top();
                    pqlr.pop();
                    if (chmax(hinit[l], rmq.get(l, r + 1))) rmq.update(l, hinit[l]);
                }
                hnow--;
            }

            int ret = rmq.get(x, x + 1);
            for (auto [l, r] : lastl2rs)
                if (ret >= l)
                    chmax(ret, r);
            rets.emplace_back(pint(x, y), ret);
            if (x == 3 and y == 10)
            {
                dbg((rmq.get(1, 2)));
                dbg((rmq.get(2, 3)));
                dbg((rmq.get(3, 4)));
                dbg((rmq.get(4, 5)));
                dbg((rmq.get(5, 6)));
                dbg((rmq.get(6, 7)));
                dbg((rmq.get(7, 8)));
                dbg((rmq.get(8, 9)));
                dbg((rmq.get(9, 10)));
            }
        }
    }
    REP(i, r2l.size()) if (r2l[i] !=-1) dbg((pint(i, r2l[i])));

    sort(ALL(rets));
    dbg(rets);
    for (auto p : queries) {
        int ret = lower_bound(ALL(rets), make_pair(p, -1000000))->second;
        cout << ret << '\n';
    }
}
