Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Special Edges

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputKoa 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.

Examples

Input

2 1 1 3 1 2 0 0 1 2

Output

0 1 2

Input

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

Output

0 1 5 6 7

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.

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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/18/2020 22:51:54 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|