Mały Vadim dostał pracę domową w szkole: musi opisać postacie z pewnego słynnego dzieła literackiego. Vadim z powodzeniem ukończył pracę domową i przygotował raport w formie arkusza kalkulacyjnego w swoim ulubionym edytorze tekstu.

Arkusz ma następującą strukturę. Jest to tabela o rozmiarze $3 \times 3$. Na przecięciu $i$-tego wiersza i $j$-tej kolumny umieszczony jest tekst o długości $a_{ij}$. Całkowita szerokość tabeli wynosi $w$ symboli. Edytor tekstu pozwala na dowolną zmianę szerokości każdej kolumny. Niech szerokości kolumn wynoszą $x, y, z$, przy czym $x + y + z = w$. Wtedy wysokość $i$-tego wiersza wynosi $h_i = \max(\lceil a_{i1}/x \rceil, \lceil a_{i2}/y \rceil, \lceil a_{i3}/z \rceil)$, a całkowita wysokość tabeli to $h = h_1 + h_2 + h_3$.

Vadim zauważył, że zmiana szerokości kolumn zmienia wysokość całej tabeli w nieprzewidywalny sposób. Vadim jest perfekcjonistą i chce zmienić szerokości kolumn w taki sposób, aby całkowita wysokość tabeli była minimalna.

Pomóż Vadimowi i znajdź optymalne rozwiązanie.

Wejście

Pierwsza linia zawiera liczbę całkowitą $w$ ($3 \le w \le 10^9$).

Kolejne trzy linie zawierają po trzy liczby całkowite. $j$-ta liczba w $i$-tej z tych linii to liczba całkowita $a_{ij}$ ($1 \le a_{ij} \le 10^{12}$).

Wyjście

W pierwszej linii wypisz liczbę całkowitą $h$ — minimalną możliwą wysokość całej tabeli.

W drugiej linii wypisz trzy liczby całkowite $x, y$ oraz $z$ — szerokości kolumn, które dają optymalne rozwiązanie.

Jeśli istnieje kilka rozwiązań, wypisz dowolne z nich.

Przykład

Wejście 1

17
10 11 11
13 7 14
10 11 11

Wyjście 1

7
5 6 6

Uwagi

Poniższa tabela odpowiada danym z pierwszego przykładu: