POLSKI SPOJ

Zadaniem programu jest zarządzanie zbiorem słów (słownikiem), poprzez realizację podawanych na wejściu poleceń aktualizacji oraz zapytań.

Wejście i wyjście

Wejście rozpoczyna się od liczby całkowitej t (t<=10⁶ ), określającej liczbę poleceń otrzymywanych przez program. Każda z kolejnych t linii zawiera jedno z następujących poleceń:

• add word - polecenie dodania do słownika słowa word ,
• add [n] suffix - jak wyżej, przy czym podana jest tylko końcówka suffix dodawanego słowa; pierwsze n liter słowa (poprzedzających końcówkę) należy przyjąć takich samych, jak w przypadku poprzednio wykonywanej operacji "add",
• delete word - polecenie usunięcia ze słownika słowa word ,
• count word1 word2 - żądanie wypisania jednej linii, zawierającej liczbę słów ze słownika, które w porządku leksykograficznym występują pomiędzy word1 a word2,
• list word1 word2 - żądanie wypisania w oddzielnych liniach wszystkich słów ze słownika, które w porządku leksykograficznym występują pomiędzy word1 a word2; wyjście powinno być uporządkowane leksykograficznie (jeżeli word1 <= word2) bądź antyleksykograficznie (jeżeli word1 > word2),
• show n - polecenie wypisania n-tego w porządku leksykograficznym słowa w słowniku.

Uwagi:

• Na początku działania programu słownik jest pusty.
• Słowa należy rozumieć jako łańcuchy znaków o długości między 1 a 10⁷, złożone wyłącznie z czterech możliwych znaków (zgodnie ze zwyczajem przyjmujemy alfabet: {'c', 'g', 't', 'a'}). Porządek leksykograficzny liter jest następujący: 'c' < 'g' < 't' < 'a'.
• W wymienionych sytuacjach przetwarzane polecenie sterujące nie powinno wpłynąć na zawartość słownika: 1) próba dodania słowa już występującego w słowniku, 2) operacja "add [n] suffix" z błędną (zbyt dużą) wartością parametru n, 3) próba usunięcia słowa nie występującego w słowniku. Polecenie "show n" z błędną (zbyt dużą) wartością parametru n powinno zostać zignorowane.
• Granice zakresów dla poleceń "count" i "list" należy traktować ,,włącznie".
• Rozmiary pliku wejściowego oraz poprawnego pliku wyjściowego nie przekraczają 32MB.

Przykład

Wejście:
14
add cta
add [1] tga
add [4] aa
list c a
add [2] aa
add [2] a
count cta ct
delete cta
count c cta
list g ctgaa
delete cta
add c
show 1
count c ctg

Wyjście:
ctga
ctgaaa
cta
3
2
ctaa
ctgaaa
c
1

Dane testowe

Do 4pkt.: wyłącznie polecenia "add word", "list".
Do 6pkt.: wyłącznie polecenia "add word", "delete", "list".
Do 8pkt.: wyłącznie polecenia "add" (dwie wersje), "delete", "list".
Do 10.5pkt.: wszystkie polecenia.