Потік у мінливій мережі

Вхідні дані

Перший рядок містить два цілих числа $n$ і $m$ (2 \leq n \leq 150, 0 \leq m \leq 2000), де $n$ — кількість вершин у мережі, а $m$ — кількість ребер. Наступні $m$ рядків описують ребра: у кожному рядку три цілих числа $x$, $y$, $c$ (1 \leq x, y \leq n, 1 \leq c \leq 1000), що позначають напрямлене ребро з $x$ у $y$ з пропускною здатністю $c$.

У наступному рядку знаходиться ціле число $t$ (1 \leq t \leq 500) — кількість операцій. Наступні $t$ рядків містять операції, кожна з яких записана у форматі "1 x y" або "2 x y" залежно від типу.

У будь-який момент у мережі не існує кількох ребер між однією й тією ж парою вершин або петель. Пропускна здатність будь-якого ребра завжди невід’ємна.

Вихідні дані

Виведіть t+1 чисел. Спочатку виведіть значення максимального потоку у мережі до виконання будь-яких операцій. Далі, після кожної операції, виводьте значення максимального потоку у поточній мережі.

Приклади