Koa 考拉有一个有向图 $$$G$$$,具有 $$$n$$$ 节点和 $$$m$$$ 边。每条边都有与其关联的容量。图中的 $$$k$$$ 边(从 $$$1$$$ 到 $$$k$$$ 编号)是特殊的,这些边最初的容量等于 $$$0$$$。
Koa 询问您 $$$q$$$ 查询。在每个查询中,她都会给你 $$$k$$$ 整数 $$$w_1, w_2, \ldots, w_k$$$。这意味着第$$$i$$$个特殊边的容量变为$$$w_i$$$(其他容量保持不变)。
Koa 想知道:每次这样的查询之后,从节点 $$$1$$$ 到节点 $$$n$$$ 的最大流量是多少?
帮助她!
输入
输入的第一行包含四个整数 $$$n$$$, $$$m$$$, $$$k$$$, $$$q$$$ ($$$2 \le n \le 10^4$$$, $$$1 \le m \le 10^4$$$, $$$1 \le k \le \min(10, m)$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — 节点数、边数、特殊边数和查询数。
接下来的 $$$m$$$ 行包含三个整数 $$$u$$$、$$$v$$$、$$$w$$$ ($$$1 \le u, v \le n$$$; $$$0 \le w \le 25$$$) - 从节点 $$$u$$$ 到节点 $$$v$$$ 且具有容量的有向边的描述$$$w$$$。
边从 $$$1$$$ 开始编号,顺序与输入中列出的顺序相同。前 $$$k$$$ 边是特殊边。对于所有 $$$i$$$ 且 $$$1 \le i \le k$$$ 的情况,保证 $$$w_i = 0$$$。
接下来的 $$$q$$$ 行包含 $$$k$$$ 整数 $$$w_1, w_2, \ldots, w_k$$$ ($$$0 \le w_i \le 25$$$) — 查询的描述。 $$$w_i$$$表示第$$$i$$$条边的容量。
输出
对于第 $$$i$$$ 个查询,打印一个整数 $$$res_i$$$ — 给定第 $$$i$$$ 个查询的特殊边权重,从节点 $$$1$$$ 到节点 $$$n$$$ 可以获得的最大流量。
示例
输入 #1
2 1 1 3 1 2 0 0 1 2
输出 #1
0 1 2
输入 #2
4 4 2 5 1 2 0 2 3 0 2 4 5 3 4 2 0 0 1 10 10 0 7 1 7 2
输出 #2
0 1 5 6 7
注意
对于第二个示例,以下图像对应于前两个查询(分别从左到右)。对于每条边,都有一对流量/容量,表示通过该边的流量和边的容量。特殊边缘为红色。
正如您在第一个查询中看到的,从节点 $$$1$$$ 到节点 $$$4$$$ 的最大流量等于 $$$0$$$,在第二个查询中等于 $$$1$$$。