B"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 <= n <= 10^4 , 1 <= m <= 10^4 , 1 <= k <= min(10, m) , 1 <= q <= 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 <= u, v <= n ; 0 <= w <= 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 <= i <= k . Each of the next q lines contains k integers w_1, w_2, ldots, w_k ( 0 <= w_i <= 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 i"...