Problem description

Back
Show PDF
Grządki
(R)
Limit pamięci: 256 MB
Limit czasu: 5.00 s

Krasnal Ogrodnik postanowił posadzić w swoim ogródku warzywa. W tym celu przygotował N grządek, a w każdej N miejsc na pojedyncze sadzonki, w których planuje posadzić marchewki, selery i pory. Udało mu się już nawet posadzić warzywa w pierwszej grządce oraz po jednym warzywie w każdej z pozostałych grządek (najbardziej z lewej strony w każdej z nich).

Niestety, pojawiły się małe komplikacje. Ogrodnik doczytał mianowicie, że nie jest najlepszym pomysłem, by warzywa tego samego rodzaju rosły obok siebie, ze względu na pojawiające się czasami w ogrodzie szkodniki.

Krasnal nie ma ochoty przesadzać już posadzonych warzyw, ale wymyślił sposób, żeby zapobiec problemowi w dalszej części ogrodu. Postanowił, że będzie sadził warzywa w kolejnych grządkach, a w każdej z nich kolejno od lewej do prawej. Rodzaj j-tego warzywa w i-tej grządce wybiera według następującej zasady:

  • jeśli ani (j−1)-sze warzywo w tej samej grządce, ani j-te warzywo w (i−1)-szej grządce nie są marchewką, wybiera marchewkę;
  • w przeciwnym przypadku, jeśli ani (j−1)-sze warzywo w tej samej grządce, ani j-te warzywo w (i−1)-szej grządce nie są selerem, wybiera selera;
  • w przeciwnym przypadku wybiera pora.

Ogrodnik zastanawia się, czy obrana taktyka jest dobra, i chciałby wiedzieć, ile warzyw każdego rodzaju będzie ostatecznie miał posadzonych. Pomóż mu to policzyć.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N, oznaczająca zarówno liczbę grządek, jak i ich długość.

W drugim wierszu znajduje się N liczb całkowitych A1, 1, A1, 2, …, A1, N, oznaczających rodzaje kolejnych warzyw w pierwszej grządce.

W kolejnych N − 1 wierszach znajduje się po jednej liczbie całkowitej; są to kolejno A2, 1, A3, 1, …, AN, 1 – rodzaje warzyw posadzonych najbardziej z lewej strony w kolejnych grządkach.

Dla wartości Ai, j stosujemy następujące oznaczenia:

  • 0 oznacza marchewkę,
  • 1 oznacza selera,
  • 2 oznacza pora.

Wyjście

Wypisz trzy liczby całkowite oznaczające kolejno liczbę posadzonych marchewek, selerów i porów po zastosowaniu techniki Ogrodnika.

Ograniczenia

1 ≤ N ≤ 500 000, Ai, j ∈ {0, 1, 2}.

Przykłady

Wejście Wyjście Wyjaśnienie 
4
1 2 0 2
0
0
0

7 4 5

Stan grządek po posadzeniu wszystkich warzyw wygląda następująco:

1 2 0 2
0 1 2 0
0 2 0 1
0 1 2 0
Wejście Wyjście Wyjaśnienie 
1
0

1 0 0

Ogródek ma rozmiar 1 × 1 i zawiera tylko jedną sadzonkę marchewki – nie ma żadnego miejsca do wyliczenia.
Wejście Wyjście Wyjaśnienie 
3
1 0 2
0
0

4 3 2

Stan grządek po wykonaniu wszystkich kroków:

1 0 2
0 1 0
0 2 1

Łącznie: 4 marchewki, 3 selery i 2 pory.