Flow in a Dynamic Network

In a given network, two types of operations can be performed. The first operation increases the capacity of the edge from vertex (x) to vertex (y) by (1), while the second operation decreases the capacity of the edge from vertex (x) to vertex (y) by (1).

Your task is to determine the maximum flow from vertex (1) to vertex (n) in the network after each operation.

Input

The first line contains two integers (n) and (m) ((2 $\le$ n $\le$ 150), (0 $\le$ m $\le$ 2000)), where (n) is the number of vertices and (m) is the number of edges in the network. The following (m) lines describe the edges, each with three integers (x), (y), and (c) ((1 $\le$ x, y $\le$ n), (1 $\le$ c $\le$ 1000)), representing an edge from vertex (x) to vertex (y) with capacity (c). Next, the input includes an integer (t) ((1 $\le$ t $\le$ 500)), indicating the number of operations to be performed on the network. Each of the following (t) lines specifies an operation in the format "(1 x y)" or "(2 x y)", depending on the operation type.

The network does not contain multiple edges between the same pair of vertices or loops. The capacity of any edge in the network is always non-negative.

Output

Output (t+1) numbers. First, print the maximum flow value in the initial network before any operations. Then, for each operation, output the maximum flow value after the operation is performed.

Examples