Coming up with legends that satisfy all the UJGOI participants is an enormous task.
That is why this legend got stolen.
You are given a directed graph with vertices that initially is empty. Starting from the first second, during each second, a directed edge is added to this graph.
Your task is to process queries.
Each query is given by two numbers and . Your task is to determine the first moment in time when there exists a path from to and from to .
If even after all edges are added and there is no path from to or from to , you should output .
Also, if x=y, you should output .
The first line contains four integers n,m,q,t (1\le n,m,q\le 3\cdot 10^5; t \in \{0,1\}).
Each of the next lines contains two integers v_i and u_i (1 \leq v_i, u_i \leq n) — the edges that are added to an initially empty graph in the order that they are added.
Each of the next lines contains two integers and (1\le x, y \le n), which denote a query.
When t=0, each query is given without encoding.
When t=1, each query is given with encoding:
initially, key=0. When you are given integers in a query, you form integers ;
x=(key-1 + a) \mod n+1;
y=(key-1 + b) \mod n+1;
after that, you answer the query; let be the answer for this query, then you update key = ans before answering the next query.
For each query, output the answer.
Example 1
Example 2
The graph for both examples. Each edge has label which denotes moment of time when it was added. Note that the second example is encrypted; after correct decryption, you are left with the same queries as in the first test case.
For nodes it is not hard to see that only when all edges up to the 6-th one are present, there exists a path from to and from to .
For nodes even when all edges are present, there is no path from to .
For nodes only when all edges are present, there exists a path from to and from to .
For nodes even when all edges are present, there is no path from to .
For nodes only when all edges are present, there exists a path from to and from to .
( points): n,m\le 80, t = 0;
( points): n,m\le 10^3, t = 0;
( points): q \le 100, t = 0;
( points): t = 0;
( points): without additional constraints.