F. Особенные ребра
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У коалы Коа есть ориентированный граф $$$G$$$ с $$$n$$$ вершинами и $$$m$$$ ребрами. Каждое ребро имеет пропускную способность, связанную с ним. Ровно $$$k$$$ ребер графа, пронумерованные от $$$1$$$ до $$$k$$$, являются особенными, такие ребра изначально имеют пропускную способность, равную $$$0$$$.

Коа задаст вам $$$q$$$ запросов. В каждом запросе она даст вам $$$k$$$ целых чисел $$$w_1, w_2, \ldots, w_k$$$. Это означает, что пропускная способность $$$i$$$-го особенного ребра становится равной $$$w_i$$$ (а другие пропускные способности остаются неизменными).

Коа задается вопросом: чему равен максимальный поток, из вершины $$$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$$$ с пропускной способностью $$$w$$$.

Ребра нумеруются начиная с $$$1$$$ в том же порядке, в котором они указаны во входных данных. Первые $$$k$$$ ребер являются специальными ребрами. Гарантируется, что $$$w_i = 0$$$ для всех $$$i$$$ с $$$1 \le i \le k$$$.

Каждая из следующих $$$q$$$ строк содержит $$$k$$$ целых чисел $$$w_1, w_2, \ldots, w_k$$$ ($$$0 \le w_i \le 25$$$)  — описание запроса. $$$w_i$$$ обозначает пропускную способность $$$i$$$-го ребра.

Выходные данные

Для $$$i$$$-го запроса выведите одно целое число $$$res_i$$$ — максимальный поток из вершины $$$1$$$ в вершину $$$n$$$ с учетом специальных весов ребер $$$i$$$-го запроса.

Примеры
Входные данные
2 1 1 3
1 2 0
0
1
2
Выходные данные
0
1
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
Выходные данные
0
1
5
6
7
Примечание

Для второго примера следующие изображения соответствуют первым двум запросам (слева направо соответственно). Для каждого ребра указана пара поток/пропускная способность, обозначающая поток, проталкиваемый через ребро, и пропускную способность ребра. Специальные ребра окрашены в красный цвет.

Как вы можете видеть, в первом запросе максимальный поток от вершины $$$1$$$ к вершине $$$4$$$ равен $$$0$$$, а во втором запросе равен $$$1$$$.