Easy Win

V–o_o–V와 LHiC가 게임을 한다.

먼저 gritukan이 n개의 정점을 가진 무방향 그래프를 보여주는데, 각 간선 위에는 돌 더미가 하나씩 놓여 있다.

그 다음 LHiC는 이 그래프의 간선 중에서 변이 서로 겹치지 않는 단순 사이클들을 이루는 비어 있지 않은 부분집합을 고른다. 다시 말해, 각 연결 성분이 오일러 회로를 가져야 한다. 만약 그렇게 고를 수 없다면, 즉 그래프가 비순환이라면 LHiC는 즉시 진다.

그렇지 않으면 LHiC와 V–o_o–V는 고른 간선 위의 돌 더미들로 님 게임을 한다. V–o_o–V가 먼저 둔다. 한 번의 수에서 플레이어는 한 더미에서 양의 개수의 돌을 임의로 들어낼 수 있다. 수를 둘 수 없는 플레이어가 진다.

LHiC가 자신이 님 게임에서 이길 수 있는, 변이 서로 겹치지 않는 사이클들의 비어 있지 않은 부분집합을 고를 수 없는 그래프를 good이라고 하자.

gritukan은 q개의 질의를 한다. 도와줄 수 있는가?

여기서 gritukan이 good 그래프를 만들기 위해 고를 수 있는 간선 후보 집합이 있다. 처음에 이 집합은 비어 있다. i번째 질의에서 먼저 정점 ui와 vi를 잇고 돌 ai개가 놓인 간선 i가 가중치 wi와 함께 후보 집합에 추가된다. 그 다음, 간선 1, 2, . . . , i의 부분집합으로 gritukan이 만들 수 있는 good 그래프의 가중치 합의 최댓값을 구해야 한다.

첫째 줄에 두 정수 n과 q가 주어진다. 이는 그래프의 정점 수와 질의의 수이다. (2 ≤ n ≤ 64, 1 ≤ q ≤ 200 000)

다음 q개의 줄에는 각각 네 정수 ui, vi, ai, wi가 주어지며, i번째 질의에서 추가되는 간선을 나타낸다. (1 ≤ ui, vi ≤ n, ui ≠ vi, 0 ≤ ai < 2^60, 1 ≤ wi ≤ 10^9)

q개의 줄을 출력한다. i번째 질의에 대해서는 간선 1, 2, . . . , i의 부분집합으로 만들 수 있는 good 그래프의 가중치 합의 최댓값을 출력한다.