Задана ориентированная сеть, с которой производят два вида операций. Первая операция увеличивает на \textbf{1 }пропускную способность ребра из \textbf{x} в \textbf{y}, а вторая операция уменьшает на \textbf{1} пропускную способность ребра из \textbf{x} в \textbf{y}. Ваша задача выводить значение максимального потока в сети из вершины \textbf{1} в вершину \textbf{n} после каждой из операций. \InputFile В первой строке записаны целые числа \textbf{n}, \textbf{m} (\textbf{2} ≤ \textbf{n} ≤ \textbf{150}, \textbf{0} ≤ \textbf{m} ≤ \textbf{2000}), где \textbf{n} --- это количество вершин в сети, а \textbf{m} --- количество рёбер. Далее в \textbf{m} строках перечислены сами рёбра (\textbf{x}, \textbf{y}) с пропускной способностью \textbf{c} по одному в строке тройками чисел \textbf{x}, \textbf{y}, \textbf{c} (\textbf{1} ≤ \textbf{x}, \textbf{y} ≤ \textbf{n}, \textbf{1} ≤ \textbf{c} ≤ \textbf{1000}). Далее входные данные содержат число \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{500}), где \textbf{t} --- количество операций производимых над сетью. Затем \textbf{t} строк содержат каждую из операций. Операции задаются последовательностями "\textbf{1 x y}" и "\textbf{2 x y}" в зависимости от типа. Сеть в любой момент времени не содержит кратных рёбер и петель. Пропускная способность любого ребра в сети в любой момент времени --- неотрицательна. \OutputFile Выведите \textbf{t+1} число. В качестве первого числа выведите значение максимального потока в заданной сети до произведения всех операций. Далее выведите \textbf{t} чисел --- значения максимального потока после каждой операции.