Shortest Path Queries
Contest: Educational Codeforces Round 38 (Rated for Div. 2)
Difficulty rating: 2900
Tags: bitmasks, data structures, dsu, graphs

You are given an undirected connected graph with weighted edges. The length of some path between two vertices is the bitwise xor of weights of all edges belonging to this path (if some edge is traversed more than once, then it is included in bitwise xor the same number of times).

There are three types of queries you have to process:

- 1 x y d — add an edge connecting vertex x to vertex y with weight d. It is guaranteed that there is no edge connecting x to y before this query;
- 2 x y — remove an edge connecting vertex x to vertex y. It is guaranteed that there was such edge in the graph, and the graph stays connected after this query;
- 3 x y — calculate the length of the shortest path (possibly non-simple) from vertex x to vertex y.

Print the answers for all queries of type 3.

Input format:
The first line contains two numbers n and m (1 ≤ n, m ≤ 200000) — the number of vertices and the number of edges in the graph, respectively.

Then m lines follow denoting the edges of the graph. Each line contains three integers x, y and d (1 ≤ x < y ≤ n, 0 ≤ d ≤ 230 - 1). Each pair (x, y) is listed at most once. The initial graph is connected.

Then one line follows, containing an integer q (1 ≤ q ≤ 200000) — the number of queries you have to process.

Then q lines follow, denoting queries in the following form:

- 1 x y d (1 ≤ x < y ≤ n, 0 ≤ d ≤ 230 - 1) — add an edge connecting vertex x to vertex y with weight d. It is guaranteed that there is no edge connecting x to y before this query;
- 2 x y (1 ≤ x < y ≤ n) — remove an edge connecting vertex x to vertex y. It is guaranteed that there was such edge in the graph, and the graph stays connected after this query;
- 3 x y (1 ≤ x < y ≤ n) — calculate the length of the shortest path (possibly non-simple) from vertex x to vertex y.

It is guaranteed that at least one query has type 3.

Output format:
Print the answers for all queries of type 3 in the order they appear in input.

Constraints:
Time limit: 3.5 s
Memory limit: 512.0 MB

Example input:
5 5
1 2 3
2 3 4
3 4 5
4 5 6
1 5 1
5
3 1 5
1 1 3 1
3 1 5
2 1 5
3 1 5

Example output:
1
1
2

Editorial:
This is a more complex version of problem G from Educational Round 27. You can find its editorial here: http://codeforces.com/blog/entry/53986
To solve the problem we consider now, you have to use a technique known as dynamic connectivity. Let's build a segment tree over queries: each vertex of the segment tree will contain a list of all edges existing in the graph on the corresponding segment of queries. If some edge exists from query l to query r, then it's like an addition operation on segment [l, r] in segment tree (but instead of addition, we insert this edge into the list of edges on a segment, and we make no pushes). Then if we write some data structure that will allow to add an edge and rollback operations we applied to the structure, then we will be able to solve the problem by DFS on segment tree: when we enter a vertex, we add all edges in the list of this vertex; when we are in a leaf, we calculate the required answer for the corresponding moment of time; and when we leave a vertex, we rollback all changes we made there.
What data structure do we need? Firstly, we will have to use DSU maintaining the distance to the leader (to maintain the length of some path between two vertices). Don't use path compression, this won't work well since we have to do rollbacks.
Secondly, we have to maintain the base of all cycles in the graph (since the graph is always connected, it doesn't matter that some cycles may be unreachable: by the time we get to leaves of the segment tree, these cycles will become reachable, so there's no need to store a separate base for each component). A convenient way to store the base is to make an array of 30 elements, initially filled with zeroes (we denote this array as a). i-th element of the array will denote some number in a base such that i-th bit is largest in the number. Adding some number x to this base is really easy: we iterate on bits from 29-th to 0-th, and if some bit j is equal to 1 in x, and a[j] ≠ 0, then we just set $$x := x \oplus a[j]$$ (let's call this process reduction, we will need it later). If we get 0 after doing these operations, then the number we tried to add won't affect the base, and we don't need to do anything; otherwise, let k be the highmost bit equal to 1 in x, and then we set a[k]:  = x.
This method of handling the base of cycles also allows us to answer queries of type 3 easily: firstly, we pick the length of some path from DSU (let it be p), and secondly, we just apply reduction to p, and this will be our answer.
Model solution: https://pastebin.com/C8v3YiEM