白云给定一张图，要求你支持以下操作：

加边

删边

判断在一段时间内，两个点是否始终连通。

输入格式

第一行$n,m,T,Q$

接下来$m$行，每行两个整数描述一条初始边

接下来$T$行，每行三个整数$op,a,b$。其中$op=0$表示删边，$op=1$表示加边。

接下来$Q$行，每行一组$L_i,R_i,A_i,B_i$表示询问在第$L_i$次操作到第$R_i$次操作之后，$A_i$和$B_i$是否始终连通。

输出格式

输出$Q$行，$1$表示始终连通，$0$表示不始终连通。

样例一

input

3 1 4 1
1 2
1 1 3
1 2 3
0 1 3
0 2 3
1 3 1 3

output

1

限制与约定

对于20%的数据：$n,m，T，Q \le 3000$。

对于另30%的数据：$n,m,T，Q \le 50000$。

对于另30%的数据：$n,m,T，Q \le 100000$。

对于全部测试数据：$n，m,T，Q \le 300000$。

时间限制：6s

空间限制：512MB