小 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 行，每行一个整数，表示答案。

样例解释

第一次询问小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 。