시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 0 0 0 0.000%

문제

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.

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.

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 aibilihi, które oznaczają, że kraj ai chciałby wydać na towary z kraju bi nie mniej niż li, ale i nie więcej niż hi ( 1 <= aibi <= N, 0 < li <= hi <= 150000 ). Każde dwie pary liczb spośród par (ai,bi) 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ć liczb całkowitych, każda w osobnej linii, gdzie i-ta linia oznacza, ile kraj ai powinien przeznaczyć pieniędzy na handel z krajem bi. Jeśli istnieje wiele rozwiązań, można wypisać dowolne z nich. Dane testowe gwarantują istnienie przynajmniej jednego takiego kompromisowego planu transakcji.

예제 입력 1

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

예제 출력 1

5
7
3
3
1
2

출처

Contest > Spot > HotSpot 2011 3-4번