P3637 System of Equations

Since primary school, we have been doing all kinds of word problems, most of which can be abstracted as solving systems of equations. To improve efficiency and save time to ~~play games~~ study OI, xht plans to develop an automatic problem solver. One of its core components is a program for solving systems of equations, and xht has decided to assign this task to you.

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

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$.

For each operation of type $3$ (query), output one integer $x$ ($0\le x

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