题目描述

波托科兰迪亚有 $n$ 栋房屋，其中第 $i$ 栋居住着 $a_i$ 位居民。这些房屋之间有 $m$ 条道路，每条道路连接房屋 $v_i$ 和 $u_i$。我们定义每位居民的 幸福值 为他能够遇到的居民数量（包括自己）。一名房屋的居民能够遇到另一名居民，如果该居民来自他的房屋，或者来自可以通过波托科兰迪亚的道路网络到达的房屋。

在过去的 $d$ 天里，每天都会发生以下两种事件之一：

• 连接房屋 $g_i$ 和 $h_i$ 的道路被大雪掩埋，因此现在无法通行。
• $w_i$ 号房屋的 $k_i$ 位居民乘坐直升机前往波托科兰迪亚境外拜访远亲。

波托科兰迪亚的居民写信给哥萨克胡子，请求他告知最后一个满足以下条件的日子：从 $x_i$ 号房屋任选一位居民与从 $y_i$ 号房屋任选一位居民，他们两人的幸福值之和至少为 $z_i$。

可以认为，所有事件都在每天的第一瞬间立即完成。如果在所有事件开始之前，幸福值之和就已经小于 $z_i$，则需要输出 $-1$。如果幸福值之和仅在第一个事件之前不低于 $z_i$，则需要输出 $0$。如果在第 $i$ 个事件之后，幸福值之和变得小于所需值，则需要输出 $i - 1$。如果在所有事件之后，幸福值之和仍然至少为 $z_i$，则需要输出 $d$。

由于哥萨克胡子是个相当忙碌的人，而波托科兰迪亚的居民众多，他请求您帮助他回复所有的信件。

输入格式

第一行包含四个整数 $n$、$m$、$d$ 和 $s$（$1 \le n, m, d, s \le 2 \cdot 10^5$）—— 分别表示房屋数量、道路数量、天数和消息数量。

下一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）—— 第 $i$ 栋房屋的居民数量。

接下来的 $m$ 行，每行包含两个整数 $v_i$ 和 $u_i$（$1 \leq v_i, u_i \leq n$，$u_i \neq v_i$）—— 表示存在道路连接的房屋。保证没有重边。

接下来的 $d$ 行，每行描述一个事件，格式为以下两种之一：

• $1~g_i~h_i$（$1 \leq g_i, h_i \leq n$）—— 被大雪掩埋的道路。保证该道路存在，且之前未被掩埋。
• $2~w_i~k_i$（$1 \leq w_i \leq n$，$1 \leq k_i \leq 10^9$）—— 房屋编号以及离开该房屋的人数。保证在任何时刻，每栋房屋至少有一位居民。

接下来的 $s$ 行，每行包含三个整数 $x_i$、$y_i$ 和 $z_i$（$1 \leq x_i, y_i \leq n$，$1 \leq z_i \leq 10^9$）。

输出格式

输出 $s$ 行，每行包含对相应查询的答案。如果两位居民的幸福值之和在第一天之前就小于 $z$，则输出 $-1$。

3 3 5 4
2 9 4
1 2
2 3
1 3
2 2 1
1 2 3
2 3 3
1 1 2
1 1 3
1 2 11
3 2 20
1 3 15
2 3 10

4
3
3
4

4 5 3 4
1 2 3 4
1 2
2 3
1 3
3 4
2 4
1 2 4
1 3 4
2 3 2
1 4 21
1 4 20
1 3 9
2 2 2

-1
1
2
3

提示

第二个样例的解释：

对于第一个查询，两位居民的幸福值之和始终小于 $21$（初始时为 $20$）。对于第二个查询，在第二天之后，他们的幸福值之和将减少到 $6 + 4 = 10$。其他查询的解释类似。

$$\begin{array}{|c|c|c|c|c|c|} \hline \rule{0pt}{1.5em} \textbf{子任务编号} & \textbf{n, m} & \textbf{d} & \textbf{s} & \textbf{额外限制} & \textbf{分值} \\ \hline \rule{0pt}{1.5em} 1 & 1 \le n, m \le 200 & 1 \le d \le 200 & 1 \le s \le 200 & - & 4 \\ \hline \rule{0pt}{1.5em} 2 & 1 \le n, m \le 2000 & 1 \le d \le 2000 & 1 \le s \le 2000 & - & 7 \\ \hline \rule{0pt}{1.5em} 3 & 1 \le n, m \le 2 \cdot 10^5 & 1 \le d \le 2000 & 1 \le s \le 2000 & - & 13 \\ \hline \rule{0pt}{1.5em} 4 & 1 \le n, m \le 5000 & 1 \le d \le 5000 & 1 \le s \le 2 \cdot 10^5 & - & 14 \\ \hline \rule{0pt}{1.5em} 5 & 1 \le n, m \le 2 \cdot 10^5 & 1 \le d \le 2 \cdot 10^5 & 1 \le s \le 2 \cdot 10^5 & x_i = y_i & 27 \\ \hline \rule{0pt}{1.5em} 6 & 1 \le n, m \le 2 \cdot 10^5 & 1 \le d \le 2 \cdot 10^5 & 1 \le s \le 2 \cdot 10^5 & - & 35 \\ \hline \end{array}$$