Kraje zrzeszone w Unii Państw Północno-Południowo-Wschodnio-Zachodnich debatują nad swoimi wydatkami na wewnątrzunijne transakcje. W Unii znajduje się N państw (numerowanych od 1 do N), które zgłosiło łącznie M wymagań określających minimalną i maksymalną wartość wymiany handlowej między nimi.</p>

Dokładniej, każde zgłoszone żądanie jest opisywane przez cztery liczby: a,b,l,h i oznacza, że krajowi a zależy na zakupie towarów z kraju b za kwotę co najmniej l, ale nie więcej niż h.

Zgodnie z najnowszymi dyrektywami unijnymi saldo każdego kraju członkowskiego w handlu wewnętrznym musi być zerowe, tj. dla każdego kraju łączna wartość jego międzypaństwowej sprzedaży musi być dokładnie równa wartości zakupów.

Sprawdź, czy spełnienie unijnych dyrektyw i żądań wszystkich krajów jest w ogóle możliwe.

입력 형식

W pierwszej linii wejścia znajduje się liczba naturalna Z ( Z = 1 ) opisująca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.</p>

Pierwsza linia zestawu składa się z oddzielonych spacjami liczb naturalnych N oraz M ( 1 <= N <= 150, 0 <= M <= 1500 ), oznaczających kolejno liczbę krajów zrzeszonych w UPPPWZ oraz liczbę wszystkich wymagań państw członkowskich. W kolejnych M wierszach opisane są kolejne wymagania, i-te z nich składa się z czterech liczb całkowitych a_i, b_i, l_i, h_i, które oznaczają, że kraj a_i chciałby wydać na towary z kraju b_i nie mniej niż l_i, ale i nie więcej niż h_i ( 1 <= a_i, b_i <= N, 0 < l_i <= h_i <= 150000 ). Każde dwie pary liczb spośród par (a_i,b_i) są różne. Żaden kraj nie handluje z samym sobą. Handel odbywa się tylko pomiędzy wymienionymi parami krajów.

출력 형식

Na wyjście należy wypisać M liczb całkowitych, każda w osobnej linii, gdzie i-ta linia oznacza, ile kraj a_i powinien przeznaczyć pieniędzy na handel z krajem b_i. Jeśli istnieje wiele rozwiązań, można wypisać dowolne z nich. Dane testowe gwarantują istnienie przynajmniej jednego takiego kompromisowego planu transakcji.

예제 입력

1
4 6
1 2 3 6
2 1 4 7
1 3 1 8
3 4 3 10
4 1 1 2
4 2 1 4

예제 출력

5
7
3
3
1
2