Tram travel

Input

In the first line are T, n, q, g (1\le n, q\le 2\cdot10^5, 2 \le T \le 10^9, 0 \le g \le 1) — the period of each tram, the number of points at the beginning, and the number of queries. $g$ is a number which used to calculate final vertices of the query. Read about it at the end of this section.

In the next n-1 lines are four numbers x, y, t_1, t_2 (1\le x, y\le n, 1\le t_1, t_2 \le10^9, t_1+t_2<T) — two points between which tram move and two numbers which describe schedule.

In the next $q$ lines, each query starts with a number $m$ (1 \leq m \leq 4) indicating the type of operation:

1. If m = 1, the query contains three numbers x, y, t (1 \leq t \leq 10^9, 1 \le x, y \le n + q), where $x$ and $y$ are two points between which people travel, starting at time $t$. Both $x$ and $y$ already exist in the city. $x$ is starting point.

2. If m = 2, the query contains four numbers x, y, t_1, t_2 (t_1+t_2<T, 1 \le x, y \le n + q), where $x$ and $y$ are two points between which a tram moves. The numbers t_1, t_2 describe the tram's schedule. Both $x$ and $y$ already exist in the city.

3. If m = 3, the query contains one number $x$, representing a point that already exists and has exactly one tram connected to it. This point $x$ must be deleted.

4. If m = 4, the query contains four numbers x, y, t_1, t_2 (t_1+t_2<T, 1 \le x, y \le n + q), where $x$ and $y$ are two points between which a tram moves. The numbers t_1, t_2 describe the tram's schedule. Here, $x$ already exists in the city, and $y$ is the first yet unused point in the city's numbering.

Let $ans$ be the answer to the last query of type $1$ (ans=0 if there was no query of type $1$ yet), then the real points of the current query are x'=((x-1+ans \cdot g) \mod (n + q))+ 1, y'=((y-1+ans \cdot g) \mod (n + q)) + 1.

Output

For each query of the type 1 print one number minimum amount of the minutes their trip will take.

Examples

Note

In the sample, first, at the first query of type 1 they have to move in this order 5 $\to$ 3 $\to$ 1 $\to$ 2 $\to$ 4.In the node 5 they wait till tram arrive at moment 4, than they will be in node 3 at moment 8, next moment tram from 1 to 3 will be in node 3 is 10, so they will arrive to node 1 at moment 13. At node 1 tram will be at moment 17 and they will arrive to node 2 at moment 22, then tram will be in node 2 at moment 24 and finally they will arrive to node 4 at moment 29. So the answer will be 27.

Scoring

1. ($25$ points): n, q\le 10^3, g=0;

2. ($50$ points): m=1, g=0;

3. ($50$ points): m\le2, g=0;

4. ($50$ points): points with trams form a bamboo, g=0;

5. ($75$ points): g=0;

6. ($175$ points): g=1;