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!

Input

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.

Output

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.

Note

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.

$\text{[math]}$

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

Special Edges

Examples