POLSKI SPOJ

Dany jest kod programu składający się z k linii. Program ten przyjmuje n danych wejściowych. Każda z k linii zawiera jedną z trzech instrukcji:

• for - Rozpoczęcie pętli. Instrukcje wewnątrz pętli zostaną wykonane n razy. Jeden obrót pętli dla każdej danej wejściowej.
• end - Zakończenie pętli.
• instruction - Dowolna instrukcja inna niż rozpoczęcie i zakończenie pętli.

Gwarantujemy, że pętle są poprawnie zagnieżdżone czyli dla każdej instrukcji for istnieje odpowiadająca jej instrukcja end. Gwarantujemy również, że każda pętla zawiera w sobie inną pętlę for lub instrukcję instruction.

Zdefiniujmy złożoność czasową naszego programu jako największy stopień zagnieżdżenia pętli for. Możliwe złożoności czasowe to:

• O(1) - Złożoność stała. Występuje, gdy program nie zawiera żadnej pętli for, czyli jest niezależny od liczby danych wejściowych.
• O(n) - Złożoność liniowa. Występuje, gdy program zawiera pętle for, ale nie są one zagnieżdżone.
• O(n^s) - Złożoność wielomianowa. Występuje, gdy program zawiera zagnieżdżone pętle for, a największy stopień ich zagnieżdżenia wynosi s.

Odpowiedz na pytanie, jaka jest złożoność czasowa danego programu?

Wejście

W pierwszej linii wejścia znajduje się liczba linii kodu k ∈ [1, 1000].

W kolejnych k liniach znajduje się kod programu. Każda linia zawiera jedną z instrukcji: for, end, instruction.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, jaka jest złożoność czasowa danego programu?

Przykład

Wejście:

18
instruction
for
for
instruction
end
for
instruction
instruction
instruction
for
instruction
instruction
end
instruction
end
end
instruction
instruction

Wyjście:

O(n^3)