题目背景

从小学开始，我们就一直做各种各样的应用题，其中大多数的题目都可以抽象为解方程组。

为了提高效率，省下时间打隔膜学习OI，xht 准备开发一个自动解题器。其中的一个核心组件就是解方程组的程序，xht 决定将这个任务交给你。

题目描述

一开始，xht 有 $N$ 个变量，记为 $x_1,x_2,\cdots,x_n$。另有一个常数 $K$，以及 $M$ 个方程，每个方程都形如 $x_a-x_b≡c\pmod K$。

由于题目可能会变化，xht 需要不时增加一个新的方程，或者删掉一个方程。

同时，xht 会给你一些这样的询问：令变量 $x_a=c$，求另一个变量 $x_b \bmod K$ 的值。当然，有的时候会因为条件不足，无法解出 $x_b$，那么就输出 $-1$。

数据保证任意时刻两个变量之间最多存在一个方程。保证不会出现自相矛盾的方程组，也不会出现多余的条件（某个方程可以通过其他一些方程推出来）。

输入格式

第一行四个整数 $N,M,K,Q$，含义如上。$Q$ 代表操作的条数。

接下来 $M$ 行，每行三个整数 $a,b,c$，表示方程 $x_a-x_b≡c\pmod K$。

接下来 $Q$ 行，每行第一个数 $t$ 代表操作种类，

* $t=1$，接下来输入 $a,b,c$，代表增加一条方程 $x_a-x_b≡c\pmod K$；

* $t=2$，接下来输入 $a,b$，代表删除 $a,b$ 之间的方程，如果这条方程不存在，则什么也不做；

* $t=3$，接下来输入 $a,b,c$，代表询问：令 $x_a=c$，求 $x_b \bmod K$ 的值；

输出格式

对于每一个 $3$ 操作（询问），输出一行一个数 $x$（$0\le x<K$），表示 $x_b \bmod K$，如果条件不足，则输出 $-1$。

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

97
-1

提示

样例的解释：

一开始有两条方程：$x_1-x_2=1$，$x_2-x_3=2$。

第一次询问，令$x_1=0$，解得$x_3=(-3)\bmod100=97$。

第二次询问时，删掉了第二条方程，导致条件不足，无法解出 $x_3$，输出 $-1$。

对于 $40\%$ 的数据，只有询问操作。

对于 $100\%$ 的数据，$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$。

保证所有的 $a\ne b$。