V–o_o–V 和 LHiC 正在玩一个游戏。

首先，gritukan 向他们展示了一个包含 $n$ 个顶点的无向图，每条边上都有一堆石子。

之后，LHiC 选择该图的一个非空边子集，这些边构成边不交的简单环（换句话说，每个连通分量都应有一个欧拉回路）。如果他无法做到（即图是无环的），他立即输掉比赛。

否则，LHiC 和 V–o_o–V 在所选边的石子堆上玩 Nim 游戏。V–o_o–V 先手。在每一轮中，玩家可以从单个石子堆中移除任意正整数个石子。无法进行移动的玩家输掉比赛。

如果 LHiC 无法选择一个非空边不交环子集使得他在 Nim 游戏中获胜，我们称该图为“好图”（good）。

gritukan 提出了 $q$ 个询问，你能帮帮他吗？

有一组可供 gritukan 选择以构成“好图”的边。初始时，该集合为空。在第 $i$ 次询问中，首先将一条连接顶点 $u_i$ 和 $v_i$、石子堆大小为 $a_i$、权重为 $w_i$ 的边加入到可选边集中。之后，你需要找出 gritukan 使用边 $1, 2, \dots, i$ 的子集所能构成的“好图”的最大权重和。

输入格式

第一行包含两个整数 $n$ 和 $q$：图的顶点数和询问次数（$2 \le n \le 64$，$1 \le q \le 200\,000$）。

接下来的 $q$ 行，每行包含四个整数 $u_i, v_i, a_i, w_i$，描述第 $i$ 次询问中加入的边（$1 \le u_i, v_i \le n$，$u_i \neq v_i$，$0 \le a_i < 2^{60}$，$1 \le w_i \le 10^9$）。

输出格式

输出 $q$ 行。对于第 $i$ 次询问，输出使用边 $1, 2, \dots, i$ 的子集所能构成的“好图”的最大权重和。

样例

样例输入 1

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

样例输出 1

1
2
3

样例输入 2

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

样例输出 2

1
3
6
9
11
11

样例输入 3

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

样例输出 3

1
2
5
14
42

样例输入 4

5 1
3 5 35 35

样例输出 4

35