Maximum Magic Walk

Given is an undirected weighted graph with n vertices and m edges.

A u-v walk is defined as a sequence of vertices starting at u and ending at v, where
consecutive vertices in the sequence are adjacent vertices in the graph i.e. consecutive vertices are connected by some edge.

An arbitary walk of length k+1 is,
where Vi and V(i+1) are connected by edge Ei with weigth Ci.

For such walk we define magic to be,

magic(walk) = (C1 & C2) ^ (C2 & C3) ^ … ^ (C(k-1) & C(k)) if k >= 2

magic(walk) = 0 if k < 2

Here, ’ & ’ is Binary AND Operator, ’ ^ ’ is Binary XOR Operator.

We love magic. Hence we always want to maximize it.

Here there are few queries. Each query has three integers (l,r,c). It means following:

a) Add one edge between vertices l and r with weight c

b) Print the maximum value of magic for any walk in the graph.

c) Remove one edge between vertices l and r with weight c.

Note: Self-loops and multiple edges are allowed at any time.


First line contains two integers n and m.

Next m lines, each contain three space separated integers u,v and c denoting an edge in graph between vertices u and v with weight c.

Next line contains q, number of queries.

Next q lines contain, three integers l,r, and c denoting to process query (l,r,c).


For each query, print required answer in a single line as explained


1 <= n <= 100

1 <= m <= 200

0 <= c <= 100

1 <= q <= 100

1 <= u,v <= n

1 <= l,r <= n

Time Limit : 3 sec