A cut is a partition of the vertices of a graph into two disjoint subsets. Any cut creates a cut-set, the set of edges that have one endpoint in each subset of the partition. Let V (cut − set) denote the XOR of all the weights on all the edges in the cut-set. In this problem you will start with an empty graph with n nodes. A number of weighted edges will be successively added to the graph. After the addition of each weighted edge, output the value of the maximum XOR cut, such that V (cut − set) is maximized! Input A number of of inputs (≤ 100) with the following format: The first two integers n, m represent the number of points in the graph and the total number of edges to be added successively. Next, we have m lines, with x, y, w where (x, y) is the undirected edge of weight w. w will be given in binary form listed from the highest binary bit to lowest binary bit. Note that 1 ≤ n ≤ 500, 1 ≤ m ≤ 1000, 0 ≤ length(w) ≤ 1000, 1 ≤ x, y ≤ n. Output For each edge, output the value of the maximum XOR cut in binary form (from high bit to low bit). Sample Input 36 1 2 11 1 2 11 3 3 1110 1 3 1011011 1 2 10111 2 3 1110110 Sample Output 11 0 0 1011011 1011011 1100001