题目描述

小 B 自己一个人出去玩了一趟后，总感觉差了点意思，于是在暑假拉着小 A、小 C、小 D 一起去玩了。

他们计划去 E 国玩，E国有 $n$ 个城市，有 $m$ 条铁路和 $k$ 条公路连接着不同的城市。

小 A 四个人打算从城市 $1$ 开始，到城市 $n$ 结束，同时他们决定路程的前一部分做火车，到某一个城市 $t$ 后租一辆车，然后在后一部分行程中开车行驶，最后在城市 $n$ 还车，并按在第 $t$ 个城市租车的收费标准来缴费。

现在已知第 $i$ 条铁路连接了城市 $x_i$ 和城市 $y_i$ ，从 $x_i$ 到 $y_i$ 和从 $y_i$ 到 $x_i$ 的费用都是 $z_i$ 元，而第 $i$ 条公路连接了城市 $x_i$ 和城市 $y_i$ ，从 $x_i$ 到 $y_i$ 和从 $y_i$ 到 $x_i$ 开车都需要 $z'_i$ 天。而在第 $i$ 个城市租车一天需要 $a_i$ 元，现在他们想知道如何安排他们的行程使他们到达城市 $n$ 的总费用最少。注意：他们可以在城市 $1$ 就租车，也可以不坐车，一直通过火车到达城市 $n$ 。

注意每个城市的租车费用并不是恒定的，有 $q$ 次修改的情况，请对每一次修改后都告诉小 A 他们最少费用。

输入格式

第一行三个整数 $n,m,k,q$ 。

接下来一行 $n$ 个整数 $a_1,a_2,...,a_n$，含义如题。

接下来 $m$ 行，每行三个整数 $x_i,y_i,z_i$，表示一条铁路。

接下来 $k$ 行，每行三个整数 $x_i,y_i,z'_i$，表示一条公路。

接下来 $q$ 行，每行两个整数 $x_i,y_i$，表示将城市 $x_i$ 的租车费用改成了 $y_i$ 元每天。

输出格式

一共 $q$ 行，每行一个整数，表示答案。

样例一

输入

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

输出

4
7
8

样例解释

第一次询问小A 四人可以在城市 $1$ 租车，花 $2$ 天到城市 $4$，总花费为 $2\times 2=4$ 元。

第二次询问小A 四人可以花费 $5$ 元坐火车到城市 $2$ ，然后在城市 $2$ 租车，花 $1$ 天到城市 $4$，总花费为 $5+1\times 2=7$ 元。

第三次询问小A 四人可以花费 $8$ 元坐火车到城市 $4$。

数据范围

对于所有数据 $n,m,k,q\le 2\times 10^5,z_i\le 10^9,z'_i,a_i\le 10^6$ 。