18472번 - 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 edgesimple 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 ai 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, . . . , i.

입력

The first line contains two integers n and q: the number of vertices in the graph and the number of queries (2 ≤ n ≤ 64, 1 ≤ q ≤ 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 ≤ u_i, v_i ≤ n, u_i ≠ v_i , 0 ≤ a_i < 2⁶⁰ , 1 ≤ w_i ≤ 10⁹).

출력

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, . . . , i.

제한

힌트