CF1383F.Special Edges

Koa the Koala has a directed graph $G$ with $n$ nodes and $m$ edges. Each edge has a capacity associated with it. Exactly $k$ edges of the graph, numbered from $1$ to $k$ , are special, such edges initially have a capacity equal to $0$ .

Koa asks you $q$ queries. In each query she gives you $k$ integers $w_1, w_2, \ldots, w_k$ . This means that capacity of the $i$ -th special edge becomes $w_i$ (and other capacities remain the same).

Koa wonders: what is the maximum flow that goes from node $1$ to node $n$ after each such query?

Help her!

The first line of the input contains four integers $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$ ) — the number of nodes, the number of edges, the number of special edges and the number of queries.

Each of the next $m$ lines contains three integers $u$ , $v$ , $w$ ( $1 \le u, v \le n$ ; $0 \le w \le 25$ ) — the description of a directed edge from node $u$ to node $v$ with capacity $w$ .

Edges are numbered starting from $1$ in the same order they are listed in the input. The first $k$ edges are the special edges. It is guaranteed that $w_i = 0$ for all $i$ with $1 \le i \le k$ .

Each of the next $q$ lines contains $k$ integers $w_1, w_2, \ldots, w_k$ ( $0 \le w_i \le 25$ ) — the description of the query. $w_i$ denotes the capacity of $i$ -th edge.

For the $i$ -th query, print one integer $res_i$ — the maximum flow that can be obtained from node $1$ to node $n$ given the $i$ -th query's special edge weights.

For the second sample, the following images correspond to the first two queries (from left to right respectively). For each edge there is a pair flow/capacity denoting flow pushed through the edge and edge's capacity. The special edges are colored in red.

As you can see in first query maximum flow from node $1$ to node $4$ equals $0$ and in second query equals $1$ .