该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

在樱花盛开的季节，西湖大学吸引了大量游客，这让胥胥非常烦恼。于是，他发明了一个神奇的按钮，按下按钮后，校园里所有的游客都会以光速从最近的大门离开学校。现在，胥胥非常好奇，游客们以光速离开学校时，每时每刻所走的距离总和是多少。

具体来说，WHU 是一个无向图，有 $n$ 个节点和 $m$ 条边。每个节点都有 $a_i$ 名游客。在 $n$ 个节点中， $k$ 个节点作为大门，每个大门的开启时间间隔为 $[l_i, r_i]$ 。问题是，从 $1$ 到 $T$ 的每个时刻，游客以光速离开校园的距离总和是多少？

注： 如果有游客无法离开学校，则距离之和应假设为 $-1$ 。

保证给定数据的图形连通、无自循环和存在多条边。

输入

第一行包含四个整数 $n$ ( $1 \le n \le 10^5$ ), $m$ ( $1 \le m \le 10^5$ ), $k$ ( $1 \le k \le 15$ ), $T$ ( $1 \le T \le 10^5$ ).

第二行包含 $n$ 个整数 $a_i$ （ $1 \le a_i \le 10^3$ ）。( $1 \le a_i \le 10^3$ )，代表 $i$ /-th 节点的游客数量。

接下来的每 $k$ 行包含三个整数 $p_i$ ( $1 \le p_i \le n$ )、 $l_i$ 、 $r_i$ 。( $1 \le l_i \le r_i \le T$ )，代表 $i$ /th 门是图中索引为 $p_i$ 的节点，门的开启时间为 $[l_i, r_i]$ 。

接下来的每行 $m$ 都包含三个整数 $u,v,w$ ( $1 \le u,v \le n,1 \le w \le 10^3$ )，代表 $u$ 和 $v$ 之间长度为 $w$ 的路径。

输出

打印 T 行，每行包含一个整数，代表 $i$ -th 时刻的距离总和。

6 8 3 3
1 2 3 4 5 6
4 1 3
5 1 2
6 2 2
1 3 1
1 2 2
2 4 2
3 4 3
5 1 4
5 2 3
1 6 5
3 6 2

47
13
72

注

在 $1$ 时刻，节点 $4$ 和 $5$ 的大门打开，而节点 $6$ 的大门关闭。节点 $1$ 的一名游客可以选择节点 $4$ 或 $5$ 离开，因此总路程为 $4$ 。位于节点 $2$ 的两名游客可以选择节点 $4$ 离开，因此总距离为 $2 \times 2=4$ 。位于节点 $3$ 的三名游客可以选择节点 $4$ 离开，因此总距离为 $3 \times 3=9$ 。位于节点 $4$ 的四名游客可以选择节点 $4$ 离开，因此总距离为 $0$ 。位于节点 $5$ 的五名游客可以选择节点 $5$ 离开，因此总距离为 $0$ 。节点 $6$ 上的六名游客可以选择节点 $4$ 离开，因此总距离为 $6 \times 5=30$ 。所有个体的距离总和为 $4+4+9+0+0+30=47$ 。