Wstęp do programowania w C++

Tym razem zrobimy symulacje poruszania się po drzewie binarnym. Oto symulacja:

1. Na początku jesteś w korzeniu drzewa (na szczycie drzewa binarnego). Jest to najwyższe miejsce w drzewie.
2. Jeśli otrzymasz komendę left - powinieneś iść do lewego syna, jeśli otrzymasz komendę right - powinieneś iść do prawego syna, jeśli otrzymasz komendę up - powinieneś przejść do ojca.
3. Zliczasz każde odwiedzenia danego węzła i wypisujesz je na wyjściu.
4. Jeśli jest komenda up i jesteś w korzeniu, nie idziesz wyżej, ale zliczasz jako kolejne odwiedzenie korzenia.

Wejście

W pierwszym wierszu jedna liczba n określająca ilość komend (nie więcej niż milion).

W kolejnych n wierszach komendy. Komendy zawierają się w zbiorze: {left, right, up}

Wyjście

Dla danej komendy wypisz który raz odwiedzasz dany węzeł drzewa. Na starcie jesteś w korzeniu i tam odznaczasz już jako jedno odwiedzenie.

Przykład

Wejście:
10
left
left
up
right
up
left
right
left
right
right

Wyjście:
1 1 2 1 3 2 1 1 1 1