Firma "Fraktax" potrzebuje nowego wydajnego modułu do swojego najnowszego projektu - edytora tekstu, który będzie wyszukiwał liczbę wystąpień danej frazy. Firmie zależy, aby ich edytor był wydajniejszy, niż dostępne edytory na rynku. W tej chwili został ogłoszony przetarg na napisanie właśnie takiego modułu, więc jeśli chcesz do niego przystąpić, napisz swój moduł i sprawdź czy jest on wystarczająco wydajny.
W pierwszym wierszu jedna liczba t określająca liczbę zdań do przeanalizowania (nie więcej niż 10000).
W drugim wierszu t zdań. Każde zdanie składa się z nie więcej niż 10000 znaków.
Następnie jedna liczba q - liczba zapytań (nie większa niż milion).
Każde zapytanie składa się z co najwyżej 20 znaków złożonych wyłącznie z małych lub dużych liter języka łacińskiego.
(plik z danymi do analizy nie przekracza 5 MB, żaden spójny podciąg tworzący wyraz złożony wyłącznie z małych lub dużych liter języka łacińskiego nie jest dłuższy niż 20 znaków. Znaki które mogą się pojawić: małe i duże litery języka łacińskiego, białe znaki, "?", "!", "-", ":","." oraz ",")
Dla każdego zapytania liczba wystąpień szukanej frazy. Wielkość liter jest rozróżnialna.
Uwaga! Wolniejsze języki nie poradzą sobie z tym zadaniem.
Wejście: 30 Stoi na stacji lokomotywa, Ciezka, ogromna i pot z niej splywa: Tlusta oliwa. Stoi i sapie, dyszy i dmucha, zar z rozgrzanego jej brzucha bucha: Uch - jak goraco! Puff - jak goraco! Uff - jak goraco! Wagony do niej podoczepiali Wielkie i ciezkie, z zelaza, stali, I pelno ludzi w kazdym wagonie, A w jednym krowy, a w drugim konie, A w trzecim siedza same grubasy, Siedza i jedza tluste kielbasy, A czwarty wagon pelen bananow, A w piatym stoi szesd fortepianow, W szostym armata - o! jaka wielka! Pod kazdym kolem zelazna belka! W siodmym debowe stoly i szafy, W osmym sloo, niedzwiedz i dwie zyrafy, W dziewiatym - same tuczone swinie, W dziesiatym - kufry, paki i skrzynie, A tych wagonow jest ze czterdziesci, Sam nie wiem, co sie w nich jeszcze miesci. Lecz chodby przyszlo tysiac atletow I kazdy zjadlby tysiac kotletow, I kazdy nie wiem jak sie wytezal, To nie udzwigna, taki to ciezar. Nagle - gwizd! Brumbrumbrumbrum 10 wagon lokomotywa i I brumbrum brum to czterdziesci aa Sam Wyjście: 3 1 65 3 2 3 7 1 0 1
Przykładowe rozwiązanie. Rozwiązanie podzieliłem na kilka kroków.