406255: GYM102331 E Easy Win

V–o_o–V and LHiC are playing a game.

At first, gritukan shows them an undirected graph with $$$n$$$ vertices where each edge has a pile of stones on it.

After that, LHiC chooses some non-empty subset of edges of this graph that forms edge-disjoint edge-simple cycles (in other words, each connected component should have an Euler circuit). If he can't (in other words, if the graph is acyclic), he loses immediately.

Otherwise, LHiC and V–o_o–V play a game of Nim with the piles on the chosen edges. V–o_o–V moves first. In a single move, a player may remove an arbitrary positive number of stones from a single pile. The player who cannot make a move loses.

Let's call a graph good if LHiC can't choose a non-empty subset of edge-disjoint cycles on which he will win Nim.

Gritukan asks $$$q$$$ queries, can you help him?

There is a set of possible edges which can be picked by gritukan to form a good graph. Initially, this set is empty. In query $$$i$$$, first, an edge $$$i$$$ connecting vertices $$$u_i$$$ and $$$v_i$$$, with a pile of $$$a_i$$$ stones on it and weight $$$w_i$$$, is added to the set of possible edges. After that, you should find the largest sum of weights of a good graph that gritukan can form using a subset of edges $$$1,2,\ldots,i$$$.

The first line contains two integers $$$n$$$ and $$$q$$$: the number of vertices in the graph and the number of queries ($$$2 \leq n \leq 64$$$, $$$1 \leq q \leq 200\,000$$$).

Each of the next $$$q$$$ lines contains four integers $$$u_i$$$, $$$v_i$$$, $$$a_i$$$, $$$w_i$$$, describing the edge added during $$$i$$$-th query ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$, $$$0 \leq a_i < 2^{60}$$$, $$$1 \leq w_i \leq 10^9$$$).

Print $$$q$$$ lines. For the $$$i$$$-th query, you should print the largest sum of weights of a good graph that you can form using a subset of edges $$$1,2,\ldots,i$$$.

3 3
1 2 0 1
2 3 0 1
3 1 0 2

1
2
3

6 6
1 2 1 1
2 3 1 2
3 4 1 3
4 1 1 4
5 6 1 2
6 5 1 1

1
3
6
9
11
11

5 5
1 2 0 1
2 3 1 1
3 4 2 3
4 5 4 9
5 1 7 29

1
2
5
14
42

5 1
3 5 35 35

35