题目描述

mzry1992 在打完吊针出院之后，买了辆新摩托车，开始了在周边城市的黄金运送生意。在 mzry1992 生活的地方，城市之间是用双向高速公路连接的。另外，每条高速公路有一个载重上限，即在不考虑驾驶员和摩托车重量的情况下，如果所载货物的量超过某个值，则不能驶上该条高速公路。今年，mzry1992 一共收到了来自 $n$ 个不同城市的 $n$ 份订单，每个订单要求卖出上限为一定量的黄金，或是要求买入上限为一定量的黄金。由于订单并不是同时发来的，为了维护生意上的名声，mzry1992 不得不按照订单发来的顺序与客户进行交易。他与第 $i$ 个客户进行交易的具体步骤是：

1. 前往第 $i$ 个客户所在城市。当然，中途是完全允许经过其他城市的。
2. 与第 $i$ 个客户进行交易，在此过程中他希望有限制的让交易额尽量大。具体的限制有两个：
   • 他希望与最后一个客户完成交易后，手上没有剩余黄金。
   • 由于黄金是很贵重的物品，不能出现因为买入过多黄金而造成在以后的运送过程中不得不丢弃黄金的情况。

一开始，mzry1992 位于第一个订单客户所在的城市。现在有一个好消息，有人提供了 mzry1992 免费试用周边城市的列车系统的资格。具体来讲，如果 mzry1992 希望从 A 城市到达 B 城市，且 A、B 城市均有列车站的话，他可以携带着黄金与摩托车从 A 城市乘坐列车到 B 城市，这里假定乘坐列车没有载重限制。现在已知城市间的交通系统情况和订单情况，请帮助 mzry1992 计算每个向 mzry1992 购买黄金的客户的购买量。

输入格式

输入的第一行有三个整数 $n,m,q$，分别表示城市数，连通城市的高速公路数和有列车站的城市数。

接下来的一行有 $n$ 个数，每个数均不相同，且值介于 $1\sim n$ 之间，代表订单的顺序。

第三行有 $n$ 个数，第 $i$ 个数表示 $i$ 号城市的订单的上限额 $b_i$，$b_i$ 为正值表示该订单为买入交易（针对 mzry1992 而言），上限为 $b_i$，$b_i$ 为负值表示该订单为卖出交易（同样针对 mzry1992 而言）上限为 $-b_i$。

接下来的 $m$ 行每行有三个数 $u,v,w$，表示城市 $u$ 和城市 $v$ 之间有一条载重上限为 $w$ 的高速公路，这里假定所有高速公路都是双向的，城市的序号是从 $1\sim n$ 的。

输入的最后一行有 $q$ 个数，代表有列车站城市的序号。

输出格式

按照订单顺序对于每个卖出交易，输出一行，该行只有一个整数 $x$，表示卖出黄金的量。

3 3 2
2 3 1
-6 5 -3
1 3 5
2 3 2
2 1 6
1 3

3
2

4 4 0
1 2 3 4
5 4 -6 -1
1 2 4
2 3 100
3 4 1
4 1 4 

6
1

样例说明 1

第一组样例，其中一种合法的方案是最初从 $2$ 号城市买入 $5$ 单位的黄金，先走第三条高速公路到 $1$ 号城市，然后再坐列车到 $3$ 号城市，在 $3$ 号城市卖出 $3$ 单位的黄金，然后乘坐列车到 $1$ 城市，在 $1$ 号城市卖出 $2$ 单位的黄金。

样例说明 2

第二组样例，其中一种合法的方案是最初从 $1$ 号城市买入 $4$ 单位的黄金，走第一条高速公路，在 $2$ 号城市买入 $3$ 单位的黄金，走第二条高速公路，在三城市点卖出 $6$ 单位的黄金，走第三条高速公路，在 $4$ 号城市卖出 $1$ 单位的黄金。

数据规模与约定

对于 $20\%$ 数据，$1\leq n\leq 100$，$n-1\leq m\leq 200$。

对于 $50\%$ 数据，$1\leq n\leq 3000$，$n-1\leq m\leq 6000$。

对于 $100\%$ 数据，$1\leq n\leq 10^5$，$n-1\leq m\leq 2\times 10^5$，$0\leq q\leq n$，$0<|b_i|<10^9$，$0<w<10^9$，保证任意两个城市之间是通过高速公路连通的。

提示

应上传者要求，此系列试题不公开，如有异议，本站将删除之。