Description

Initially, xht has $N$ variables, denoted by $x_1,x_2,\cdots,x_n$. There is also a constant $K$, and $M$ equations, each of the form $x_a-x_b≡c\pmod K$.

Since the problem may change, xht sometimes needs to add a new equation or delete an existing one.

At the same time, xht will give you some queries: set the variable $x_a=c$, and find the value of another variable $x_b \bmod K$. Of course, sometimes $x_b$ cannot be determined due to insufficient conditions; in that case, output $-1$.

The testdata guarantees that at any time there is at most one equation between any two variables. It is guaranteed that no contradictory systems will appear, and no redundant conditions will appear (no equation can be derived from some others).

Description

Input Format

The first line contains four integers $N,M,K,Q$, as described above. $Q$ is the number of operations.

The next $M$ lines each contain three integers $a,b,c$, representing the equation $x_a-x_b≡c\pmod K$.

The next $Q$ lines, each starting with an integer $t$ indicating the type of operation:

• $t=1$: followed by $a,b,c$, meaning to add an equation $x_a-x_b≡c\pmod K$;
• $t=2$: followed by $a,b$, meaning to delete the equation between $a$ and $b$. If this equation does not exist, do nothing;
• $t=3$: followed by $a,b,c$, meaning a query: set $x_a=c$, and ask for the value of $x_b \bmod K$.

Output Format

For each operation of type $3$ (query), output one integer $x$ ($0\le x<K$), representing $x_b \bmod K$. If the conditions are insufficient, output $-1$.

3 2 100 3
1 2 1
2 3 2
3 1 3 0
2 1 2
3 1 3 0

97
-1

Hint

Explanation of the sample:

Initially there are two equations: $x_1-x_2=1$, $x_2-x_3=2$.

In the first query, set $x_1=0$, and obtain $x_3=(-3)\bmod100=97$.

In the second query, the second equation has been deleted, leading to insufficient conditions, so $x_3$ cannot be determined. Output $-1$.

For $40\%$ of the testdata, there are only query operations.

For $100\%$ of the testdata, $1\le M<N\le10^5$, $1\le Q\le10^5$, $2\le K\le10^3$, $1\le a,b\le N$, $0\le c<K$.

It is guaranteed that all $a\ne b$.

Translated by ChatGPT 5