Archiwum zadań programistycznych WWSI

Twoi przeciwnicy rozsiewają plotki, że jesteś kiepskim programistą, którego programy nawet się nie uruchamiają nie mówiąc już o poprawnym działaniu. Udowodnij im wszystkim, że są w błędzie i napisz interpreter języka D.O.M. (Dodawanie – Odejmowanie – Mnożenie).

Język D.O.M. Składa się z poleceń pooddzielanych pojedynczymi spacjami. Każde polecenie może być liczbą naturalną albo jedną z liter D, O, M. W przypadku napotkania liczby należy odłożyć ją na szczyt stosu. Po wczytaniu litery D należy zdjąć ze stosu dwie liczby a oraz b i odłożyć na szczyt stosu ich sumę. Analogicznie należy postępować po wczytaniu liter O oraz M z tym, że zamiast sumy należy obliczyć odpowiednio ich różnicę (b – a) albo iloczyn. W przypadku obliczania różnicy należy przyjąć, że liczba a jest pierwszą liczbą zdjętą ze stosu zaś liczba b drugą.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba naturalna t (1 <= t <= 1000) określająca ilość zestawów danych. W kolejnych t liniach znajdują się zestawy danych.

Każdy zestaw danych zawiera maksymalnie 1000 poleceń języka D.O.M.. Poleceniem może być liczba naturalna n (1 <= n <= 10⁹) albo jedna z 3 liter D, O albo M, których to znaczenie zostało omówione w treści powyżej. Wczytywanie poleceń należy zakończyć po wczytaniu znaku "=".

Gwarantujemy, że na stosie zawsze będzie się znajdowała wystarczająca ilość liczb do wykonania obliczeń, zaś wyniki obliczeń nigdy nie przekroczą 10¹⁸.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać liczby, które pozostały na stosie zaczynając od tych będących na jego wierzchu.

Przykład

Dla danych:

2
4 4 D 2 4 M D 1 O =
1000000000 1000000000 M =

Twój program powinien wypisać:

15 
1000000000000000000