To zadanie jest interaktywne. Po wypisaniu każdej linii należy opróżnić bufor wyjścia (flush). Możesz użyć cout << flush w C++, System.out.flush() w Javie oraz sys.stdout.flush() w Pythonie. Musisz ściśle przestrzegać instrukcji w sekcji Interakcja; w przeciwnym razie możesz otrzymać werdykt taki jak błędna odpowiedź (wrong answer), przekroczenie limitu czasu (time limit exceeded) lub inny.

Ponieważ praca w kopalni jest ciężka i czasochłonna, krasnoludy postanowiły poszukać pomocy w zautomatyzowaniu niektórych swoich zadań. Ich obecnym zadaniem jest sklasyfikowanie $N$ minerałów (oznaczonych liczbami od $1$ do $N$) do różnych klas. Aby w tym pomóc, Krasnolud Robotnik zainstalował nowy taśmociąg. Krasnoludy mogą dokładać próbki minerałów na początek taśmociągu i zdejmować je z jego końca (tj. zdejmować minerały, które zostały dołożone najwcześniej).

Niestety, ten taśmociąg nie posiada bazy wiedzy, więc nie potrafi rozpoznać klasy żadnego znajdującego się na nim minerału. Posiada jednak inną przydatną funkcję: wyświetla, ile różnych klas minerałów znajduje się obecnie na taśmociągu. Okazuje się, że to wystarczy dla kopalni, ponieważ krasnoludy nie muszą znać klasy każdego minerału: muszą jedynie posegregować minerały na stosy tej samej klasy.

Czy pomożesz krasnoludom rozwiązać to zadanie za pomocą taśmociągu?

Interakcja

Klasy minerałów są ustalone na początku i nie zależą od zadawanych zapytań.

Najpierw wczytaj linię zawierającą jedną liczbę całkowitą $N$, oznaczającą liczbę minerałów do sklasyfikowania. Następnie możesz wykonywać operacje następujących dwóch typów:

• + id — minerał o identyfikatorze id zostaje dołożony na początek taśmociągu.
• - — minerał znajdujący się na końcu taśmociągu zostaje zdjęty. Jeśli taśmociąg jest pusty, nic się nie dzieje.

Po każdej operacji taśmociąg wypisuje jedną linię zawierającą liczbę różnych klas znajdujących się obecnie na nim.

Aby wypisać odpowiedź, najpierw wypisz linię zawierającą !, a po niej liczbę $k$ będącą liczbą różnych klas w kopalni. Następnie wypisz $k$ linii, z których każda opisuje jedną klasę. Każda linia powinna zawierać liczbę $c_i$, a po niej $c_i$ identyfikatorów minerałów należących do tej klasy. Każdy z $N$ minerałów musi pojawić się w dokładnie jednej klasie. Możesz wypisać klasy oraz minerały wewnątrz każdej klasy w dowolnej kolejności.

Pamiętaj o opróżnianiu bufora wyjścia (flush) po każdej operacji oraz po wypisaniu odpowiedzi. Pamiętaj o oddzielaniu spacjami liczb oraz symboli +, -, !. Musisz wczytać wszystkie dane od interaktora.

Ograniczenia

$1 \le N \le 500$, możesz wykonać co najwyżej $35\,000$ operacji.

Przykłady

Wejście 1

3
1
2
2
2

Wyjście 1

+ 1
+ 2
+ 3
-
! 2
2 1 3
1 2

Uwaga

W pierwszym teście przykładowym $N = 3$, a klasy minerałów $1, 2, 3$ to odpowiednio $1, 2, 1$.

Testowanie lokalne

W sekcji Files znajdziesz plik A.zip zawierający testy przykładowe oraz oceniaszkę grader.cpp. Aby przetestować swoje rozwiązanie, skompiluj je, a następnie przekaż nazwę testu oraz swój plik wykonywalny do skompilowanego programu ./grader:

./grader [test] [executable]

Na przykład: ./grader 0b.in ./abc

Przykładowa oceniaszka nie musi działać identycznie jak oficjalna. Żadna z nich nie jest jednak adaptacyjna.