题目描述

波托科兰迪亚有 $n$ 栋房子，第 $i$ 栋房子中住着 $a_i$ 名居民。这些房子之间有 $m$ 条道路，每条道路连接房子 $v_i$ 与 $u_i$。我们定义每个居民的幸福值为他能够见到的居民数量（包括他自己）。一名居民可以见到另一名居民，当且仅当对方与他在同一栋房子，或者可以沿着波托科兰迪亚的道路从他的房子到达对方所在的房子。

在最近的 $d$ 天中，每天发生以下两类事件之一：

1. 房子 $g_i$ 与 $h_i$ 之间的道路被雪堵住，因此之后不能再通过；
2. 第 $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\le a_i\le 10^9$），表示第 $i$ 栋房子中的居民数量。

接下来 $m$ 行，每行包含两个整数 $v_i,u_i$（$1\le v_i,u_i\le n$，$u_i\ne v_i$），表示一条道路连接的两栋房子。保证没有重边。

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

• 1 g_i h_i（$1\le g_i,h_i\le n$）：表示被雪堵住的道路。保证这条道路存在，且之前没有被堵住过。
• 2 w_i k_i（$1\le w_i\le n$，$1\le k_i\le 10^9$）：表示房子编号以及离开该房子的居民数。保证任意时刻每栋房子中至少有一名居民。

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

输出格式

输出 $s$ 行，每行表示对应询问的答案。若在第一天之前，两个居民幸福值之和就小于 $z$，输出 $-1$。

样例

样例 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

样例 2

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$。其他询问可同理解释。

计分方式

原题计分表如下图所示：

文字化整理如下：