P3280 [SCOI2013] 摩托车交易

mzry1992 在打完吊针出院之后，买了辆新摩托车，开始了在周边城市的黄金运送生意。在 mzry1992 生活的地方，城市之间是用双向高速公路连接的。另外，每条高速公路有一个载重上限，即在不考虑驾驶员和摩托车重量的情况下，如果所载货物的量超过某个值，则不能驶上该条高速公路。 今年，mzry1992 一共收到了来自 $n$ 个不同城市的 $n$ 份定订单，每个订单要求卖出上限为一定量的黄金，或是要求买入上限为一定量的黄金。由于订单并不是同时发来的，为了维护生意上的名声，mzry1992 不得不按照订单发来的顺序与客户进行交易。他与第i 个客户进行交易的具体步骤是： 1. 前往第 $i$ 个客户所在城市。当然，中途是完全允许经过其他城市的。 2. 与第 $i$ 个客户进行交易，在此过程中他希望有限制的让交易额尽量大。具体的限制有两个： (a) 他希望与最后一个客户完成交易后，手上没有剩余黄金。 (b) 由于黄金是很贵重的物品，不能出现因为买入过多黄金而造成在以后的运送过程中不得不丢弃黄金的情况。 一开始，mzry1992 位于第一个订单客户所在的城市。现在有一个好消息，有人提供了 mzry1992 免费试用周边城市的列车系统的资格。具体来讲，如果mzry1992希望从 $A$ 城市到达 $B$ 城市，且 $A$、$B$ 城市均有列车站的话，他可以携带着黄金与摩托车从 $A$ 城市乘坐列车到 $B$ 城市，这里假定乘坐列车没有载重限制。 现在已知城市间的交通系统情况和订单情况，请帮助 mzry1992 计算每个向 mzry1992 购买黄金的客户的购买量。

无

无

### 样例解释 第一组样例：其中一种合法的方案是最初从 $2$ 号城市买入 $5$ 单位的黄金，先走第三条高速公路到 $1$ 号城市，然后再坐列车到 $3$ 号城市，在 $3$ 号城市卖出 $3$ 单位的黄金，然后乘坐列车到 $1$ 城市，在 $1$ 号城市卖出 $2$ 单位的黄金。 第二组样例：其中一种合法的方案是最初从 $1$ 号城市买入 $4$ 单位的黄金，走第一条高速公路，在 $2$ 号城市买入 $3$ 单位的黄金，走第二条高速公路，在三城市点卖出 $6$ 单位的黄金，走第三条高速公路，在 $4$ 号城市卖出 $1$ 单位的黄金。 ### 数据范围与约定 - 对于 $20\%$ 数据，$n \le 100$，$m \le 200$。 - 对于 $50\%$ 数据，$n \le 3000$，$m \le 6000$。 - 对于 $100\%$ 数据，$1 \le n \le 10^5$，$n - 1 \le m \le 2\times 10^5$，$0 \le q \le n$，$0 < |b_i| < 10^9$，$0 < w < 10^9$，保证任意两个城市之间是通过高速公路连通的。