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,
V1,E1,V2,E2,V3,…,Vk,Ek,V(k+1).
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.
Input:
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).
Output:
For each query, print required answer in a single line as explained
Constraints:
1 <= n <= 100
1 <= m <= 200
0 <= c <= 100
1 <= q <= 100
1 <= u,v <= n
1 <= l,r <= n
Time Limit : 3 sec