F. 特殊边

每测试点时间限制：5 秒
内存限制：256 MB

考拉 Koa 有一张有向图 $G$，包含 $n$ 个节点和 $m$ 条边。每条边都有一个容量。其中恰好有 $k$ 条边是特殊的，编号为 $1$ 到 $k$，这些特殊边的初始容量为 $0$。

Koa 会向你提出 $q$ 个查询。在每个查询中，她会给你 $k$ 个整数 $w_1, w_2, \dots, 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$ 的有向边及其容量。

边按输入顺序从 $1$ 开始编号。前 $k$ 条边是特殊边。保证对所有 $1 \le i \le k$ 有 $w_i = 0$。

接下来的 $q$ 行，每行包含 $k$ 个整数 $w_1, w_2, \dots, 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$。