Учитель Ма Баого и молодой человек готовятся к поединку на неориентированном графе с $n$ вершинами и $m$ ребрами. Поскольку молодой человек опасается, что учитель Ма Баого обвинит его в неспортивном поведении, ему необходимо улучшить место проведения поединка.

Для каждого неориентированного ребра заданы два параметра: гладкость пола $a_i$ и гладкость стен по обе стороны $b_i$. Молодому человеку нужно выбрать ровно $k$ ребер, удалив все остальные.

Чтобы учитель Ма Баого не смог легко сбежать, молодой человек требует, чтобы эти $k$ ребер не образовывали циклов. Кроме того, чтобы учитель Ма Баого не упал и не стал требовать компенсацию, молодой человек хочет минимизировать произведение суммы $a_i$ на сумму $b_i$ для выбранных $k$ ребер.

Поскольку он еще не определился с точным значением $k$, вам необходимо найти ответ для всех $k$, где $1 \le k < n$.

Входные данные

Первая строка содержит целое положительное число $T$, количество наборов входных данных.

Для каждого набора данных первая строка содержит два целых положительных числа $n$ и $m$, количество вершин и ребер соответственно.

Далее следуют $m$ строк, каждая из которых содержит четыре целых положительных числа $a_i, b_i, u_i, v_i$, обозначающих гладкость пола, гладкость стен и два соединенных ребром узла соответственно.

Выходные данные

Для каждого набора данных выведите одну строку, содержащую $n-1$ число, где $i$-е число является ответом для $k=i$.

Примеры

Пример 1

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

Выходные данные 1

2 12 40

Примечание

При $k=1$ выбрано ребро $(2,4)$.

При $k=2$ выбраны ребра $(2,4), (3,4)$.

При $k=3$ выбраны ребра $(2,4), (3,4), (1,2)$.

Подзадачи

Для всех данных гарантируется, что $n-1 \le m \le 1500$, $\sum m^2 \le 2.5\times10^6$, $1 \le u_i, v_i \le n$, $u_i \neq v_i$, $1 \le a_i, b_i \le 2\times10^6$. Входной граф является связным, и для любых $1 \le i < j \le m$ выполняется $a_i \neq a_j$ или $b_i \neq b_j$, то есть все пары $(a_i, b_i)$ различны.

• $\text{subtask1(10 баллов)}: n, m \le 20, T=1$
• $\text{subtask2(20 баллов)}: n-1=m$, то есть входные ребра образуют дерево, и $n \le 50$
• $\text{subtask3(20 баллов)}: n, m \le 50$
• $\text{subtask4(20 баллов)}: n-1=m$, то есть входные ребра образуют дерево
• $\text{subtask5(30 баллов)}:$ без дополнительных ограничений