Problem description

Jasio jest zapalonym kolekcjonerem digimonów, pokemonów i innych stworów. Niektóre z nich chciałby dobrać w pary i poukładać na półeczce, a resztę schować do skrzyni. Oczywiście dobieranie w pary nie może być byle jakie, każdy stwór w różnym stopniu lubi (albo nie) każdego innego stwora.

Na potrzeby zadania założymy, że Jasio posiada N digimonów i M pokemonów. Ponadto przygotował on Q potencjalnych par stworów, wraz z ich preferencjami. Jasio może dobrać stwory zgodnie z przygotowanymi parami, jednak musi zadbać o to, aby wszystkie stwory były zadowolone.

Dla danego dobrania w pary, pewna niewybrana para stworów (znajdująca się na liście potencjalnych par) będzie niezadowolona, jeśli zajdą oba poniższe warunki:

• digimon z tej pary nie ma przyporządkowanego partnera lub bardziej lubi pokemona z tej pary, niż tego z którym obecnie jest dobrany,
• pokemon z tej pary nie ma przyporządkowanego partnera lub bardziej lubi digimona z tej pary, niż tego z którym obecnie jest dobrany.

Twoim zadaniem jest wyznaczenie minimalnej i maksymalnej liczby możliwych par.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne N, M oraz Q, będące odpowiednio liczbą digimonów, pokemonów oraz potencjalnych par. W i-tym z kolejnych Q wierszy znajdują się cztery liczby naturalne D_i, P_i, A_i oraz B_i, będące odpowiednio numerem digimona, numerem pokemona, preferencją digimona (względem pokemona) oraz preferencją pokemona (względem digimona). Im wyższa preferencja tym bardziej dany stwór lubi tego drugiego. Digimony ponumerowane są kolejnymi liczbami naturalnymi od 1 do N, a pokemony ponumerowane są kolejnymi liczbami naturalnymi od 1 do M.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinny się znaleźć dwie liczby naturalne, będące odpowiednio minimalną i maksymalną liczbą możliwych par. Jeżeli nie istnieje żadne poprawne dobranie w pary, to należy wypisać NIE.

Ograniczenia

1 ≤ N, M ≤ 100 000, 1 ≤ Q ≤ 500 000, 1 ≤ D_i ≤ N, 1 ≤ P_i ≤ M.

Zarówno ciąg A jak i ciąg B tworzą permutację.

Każda możliwa para stworów występuje co najwyżej raz.

Przykład

3 2 3
1 2 3 2
2 1 1 3
3 2 2 1

2 2