У коалы Коа есть ориентированный граф \(G\) с \(n\) вершинами и \(m\) ребрами. Каждое ребро имеет пропускную способность, связанную с ним. Ровно \(k\) ребер графа, пронумерованные от \(1\) до \(k\), являются особенными, такие ребра изначально имеют пропускную способность, равную \(0\).
Коа задаст вам \(q\) запросов. В каждом запросе она даст вам \(k\) целых чисел \(w_1, w_2, \ldots, w_k\). Это означает, что пропускная способность \(i\)-го особенного ребра становится равной \(w_i\) (а другие пропускные способности остаются неизменными).
Коа задается вопросом: чему равен максимальный поток, из вершины \(1\) в вершину \(n\) после каждого такого запроса?
Помогите ей!
Выходные данные
Для \(i\)-го запроса выведите одно целое число \(res_i\) — максимальный поток из вершины \(1\) в вершину \(n\) с учетом специальных весов ребер \(i\)-го запроса.
Примечание
Для второго примера следующие изображения соответствуют первым двум запросам (слева направо соответственно). Для каждого ребра указана пара поток/пропускная способность, обозначающая поток, проталкиваемый через ребро, и пропускную способность ребра. Специальные ребра окрашены в красный цвет.
Как вы можете видеть, в первом запросе максимальный поток от вершины \(1\) к вершине \(4\) равен \(0\), а во втором запросе равен \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1 1 3
1 2 0
0
1
2
|
0
1
2
|
|
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
|