Given a weighted directed graph with $n$ vertices and $m$ edges, the two endpoints of each edge are generated uniformly and independently at random from the $n$ vertices, and the edge weights are generated uniformly and independently at random from $[0, 2^{32})$.

You are also given $q$ queries, each consisting of two endpoints $s_i$ and $t_i$. You need to find the minimum path weight sum from $s_i$ to $t_i$. If no such path exists, output $-1$.

It is guaranteed that the $s_i$ and $t_i$ for the $q$ queries are chosen uniformly and independently at random from all vertices, and are independent of the graph generation.

Note that the vertices are numbered $1 \sim n$, and the graph may contain multiple edges and self-loops.

Input

The first line contains four integers $n, m, q, seed$, where $seed$ is an integer chosen uniformly at random from $[0, 2^{32})$ used to generate the graph. Participants can generate the required graph using the code provided at the end of the problem.

The next $q$ lines each contain two positive integers $s_i$ and $t_i$, representing a query.

It is guaranteed that the $s_i$ and $t_i$ for the $q$ queries are chosen uniformly and independently at random from all vertices, and are independent of the graph generation.

Output

Output $q$ lines, each containing an integer representing the answer.

Examples

Input 1

4 8 5 1112792816
2 3
4 3
4 3
3 2
1 4

Output 1

3419197189
1798364963
1798364963
3986398077
2337967903

Note

The following is the graph corresponding to the sample:

For all data: $1 \leq n \leq 2 \times 10^5, 1 \leq m \leq 3\times 10^6, 1 \leq q \leq 10^4$.

Graph generator:

#include<tuple>
#include<vector>
#include<random>
std::vector<std::tuple<int, int, long long>> generate_edges(int n, int m, unsigned seed) {
    std::mt19937 gen(seed);
    std::vector<std::tuple<int, int, long long>> edges(m);
    unsigned max = -1u / n * n;
    auto sample = [&]() {
        unsigned x;
        do { x = gen(); } while(x >= max);
        return x % n + 1;
    };
    for(auto & [u, v, w] : edges) {
        u = sample();
        v = sample();
        w = gen();
    } // Edge from u to v with weight w
    return edges;
}

If you do not understand this code, you can assume that mt19937 is a relatively strong pseudo-random number generator. The graph generated by this code can be considered an independently and uniformly generated random graph under normal circumstances. It stores an edge as a tuple and returns a vector containing $m$ edges.