Problem: You are involved in the development of a certain game. The game is for players to explore randomly generated dungeons.

There are n rooms in the dungeon generated by this game, and they are numbered from 0 to n-1. The rooms are connected by a passage. There are m passages connecting rooms. The passage can go in either direction. In addition, a distance is set between the rooms. In the generated dungeon, it is possible to go from one room to all other rooms via several passages. Then, when the player plays the game, the 0th room is selected as the starting point and the n-1th room is selected as the goal point.

I want to set up a treasure chest in some room with items that will help users explore the dungeon. At that time, it is meaningless if it is too far from the starting point or too close to the goal point. Therefore, we would like to make a room that takes at least fg as a candidate for installing a treasure chest when we reach within the distance fs from the start and take the shortest path to reach the goal.

Given the generated dungeon and q. For q queries, count the number of candidate locations for treasure chests.



Input

The input is given in the following format.


n m
a1 b1 c1
..
..
..
am bm cm
q
fs1 fg1
..
..
..
fsq fgq


ai bi ci means that the distance of the passage connecting the rooms ai and bi is ci.

Input meets the following constraints
2 ≤ n ≤ 100,000
0 ≤ ai, bi <n
0 ≤ ci ≤ 100,000
n-1 ≤ m ≤ 100,000
1 ≤ q ≤ 100,000
0 ≤ fsi, fgi ≤ 260

Output

Print the answer value on one line for each query

Example

Input

4 4
0 1 3
1 3 4
0 2 2
2 3 1
4
0 0
2 2
2 1
3 4


Output

1
1
2
1

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#ifndef LIB_REPEAT_HPP
#define LIB_REPEAT_HPP
#define repeat(i,n) for (int i = 0; i < (n); ++i)
#define repeat_from(i,m,n) for (int i = (m); i < (n); ++i)
#define repeat_one(i,n) for (int i = 1; i <= (n); ++i)
#define repeat_rev(i,n) for (int i = (n)-1; 0 <= i; --i)
#define foreach(it, cont) for (decltype(cont.begin()) it = cont.begin(); it != cont.end(); ++it)
#endif
#ifndef LIB_GRAPH_DIJKSTRA_HPP
#define LIB_GRAPH_DIJKSTRA_HPP

#include <vector>
#include <queue>
#ifndef LIB_REPEAT_HPP
#define LIB_REPEAT_HPP
#define repeat(i,n) for (int i = 0; i < (n); ++i)
#define repeat_from(i,m,n) for (int i = (m); i < (n); ++i)
#define repeat_one(i,n) for (int i = 1; i <= (n); ++i)
#define repeat_rev(i,n) for (int i = (n)-1; 0 <= i; --i)
#define foreach(it, cont) for (decltype(cont.begin()) it = cont.begin(); it != cont.end(); ++it)
#endif
template <typename T>
std::vector<T> dijkstra(const std::vector<std::vector<std::pair<int,T> > > & g, int s) {
    int n = g.size();
    std::vector<T> result(n,-1);
    std::vector<bool> used(n, false);
    std::priority_queue<std::pair<T,int>, std::vector<std::pair<T,int> >, std::greater<std::pair<T,int> > > q;
    q.push(std::make_pair(0,s));
    while (not q.empty()) {
        T   c = q.top().first;
        int i = q.top().second;
        q.pop();
        if (not used[i]) {
            used[i] = true;
            result[i] = c;
            repeat (e,(int)g[i].size()) {
                int j = g[i][e].first;
                T   d = g[i][e].second;
                if (not used[j]) {
                    q.push(std::make_pair(c+d,j));
                }
            }
        }
    }
    return result;
}

#endif
#ifndef LIB_DATA_BINARY_INDEXED_TREE_HPP
#define LIB_DATA_BINARY_INDEXED_TREE_HPP

#include <vector>

template <typename T>
struct binary_indexed_tree {
    std::vector<T> v;
    binary_indexed_tree(int n) : v(n) {}

    void add(size_t i, T w) {
        for (size_t j = i+1; j <= v.size(); j += j & -j) v[j-1] += w;
    }
    void update(size_t i, T w) {
        add(i, w - v[i-1]);
    }
    int sum(size_t i) {
        T acc = 0;
        for (size_t j = i; 0 < j; j -= j & -j) acc += v[j-1];
        return acc;
    }
};

#endif
#ifndef LIB_TYPEDEF_LL_HPP
#define LIB_TYPEDEF_LL_HPP
typedef long long ll;
typedef unsigned long long ull;
#endif
#ifndef LIB_DEBUG_HPP
#define LIB_DEBUG_HPP
#ifdef DEBUG
#include <cassert>
#define debug(a) a
#else
#define debug(a)
#endif
#endif
using namespace std;

// a[nth(a)[i]] = sorted(a)[i]
template <typename T>
vector<int> nth(const vector<T> & g) {
    int n = g.size();
    vector<int> result(n);
    vector<pair<ll,int> > t(n);
    repeat (i,n) t[i] = make_pair(g[i],i);
    sort(t.begin(), t.end());
    repeat (i,n) result[i] = t[i].second;
    return result;
}

template <typename S, typename T>
vector<pair<S,T> > zip(const vector<S> & a, const vector<S> & b) {
    vector<pair<S,T> > c(max(a.size(),b.size()));
    repeat (i,(int)a.size()) c[i].first  = a[i];
    repeat (i,(int)b.size()) c[i].second = b[i];
    return c;
}
template <typename S, typename T>
pair<vector<S>,vector<T> > unzip(const vector<pair<S,T> > & c) {
    vector<S> a(c.size());
    vector<T> b(c.size());
    repeat (i,(int)c.size()) {
        a[i] = c[i].first;
        b[i] = c[i].second;
    }
    return make_pair(a,b);
}
template <typename S, typename T>
vector<S> firsts(const vector<pair<S,T> > & c) {
    vector<S> a(c.size());
    repeat (i,(int)c.size()) a[i] = c[i].first;
    return a;
}
template <typename S, typename T>
vector<T> seconds(const vector<pair<S,T> > & c) {
    vector<T> b(c.size());
    repeat (i,(int)c.size()) b[i] = c[i].second;
    return b;
}

template <typename T>
struct compresser {
    set<T> used;
    template <class InputIterator>
    void add(InputIterator first, InputIterator last) {
        for (; first != last; ++ first) {
            used.insert(*first);
        }
    }
    map<T,size_t> compress() const {
        typename std::map<T,size_t> result;
        int i = 0;
        auto it = used.begin();
        while (it != used.end()) result[*(it ++)] = i ++;
        return result;
    }
};

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

    int N, M; cin >> N >> M;
    vector<vector<pair<int,ll> > > g(N);
    repeat (i,M) {
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back(make_pair(b,c));
        g[b].push_back(make_pair(a,c));
    }
    int Q; cin >> Q;
    vector<pair<ll,ll> > q(Q);
    repeat (i,Q) cin >> q[i].first >> q[i].second;

    vector<ll> ds = dijkstra(g, 0);
    vector<ll> dg = dijkstra(g, N-1); {
        vector<pair<ll,ll> > d = zip<ll,ll>(ds,dg);
        sort(d.begin(), d.end());
        auto p = unzip(d);
        ds = p.first;
        dg = p.second;
    }

    map<ll,size_t> comp; {
        compresser<ll> c;
        c.add(dg.begin(), dg.end());
        vector<ll> r = unzip(q).second;
        c.add(r.begin(), r.end());
        comp = c.compress();
    }

    binary_indexed_tree<int> bit(comp.rbegin()->second+1);

    vector<int> qth = nth(unzip(q).first);
    vector<int> result(Q);

    int j = 0;
    repeat (i,Q) {
        ll fs = q[qth[i]].first;
        int fg = comp[q[qth[i]].second];
        for (; j < N and ds[j] <= fs; ++j) {
            bit.add(comp[dg[j]],1);
        }
        result[qth[i]] = j - bit.sum(fg);
    }
    repeat (query,Q) cout << result[query] << endl;
    return 0;
}