Kompresja

Dawniej wyszukiwanie wzorca w tekście było takie łatwe. A teraz teksty są bardzo długie i przechowywane są w postaci skompresowanej. I jak tu wyszukiwać łatwo wzorzec w tekście?

Skompresowanym tekstem długości n (po kompresji) jest ciąg n par (liczba całkowita dodatnia X, litera C) która oznacza "teraz następuje X liter C". Innymi słowy, ciąg (2,a) (3,b) (2,a) (4,c) reprezentuje słowo aabbbaacccc.

Wyszukaj skompresowany wzorzec w skompresowanym tekście! Innymi słowy, dla podanych dwóch słów - wzorca i tekstu (oba w postaci skompresowanej) wypisz: ile razy pierwsze słowo występuje w drugim jako podsłowo, oraz pozycję gdzie występuje pierwszy raz i ostatni raz.

Wejście

Wejście składa się z czterech linijek, pierwsze dwa to skompresowany wzorzec, drugie dwa to skompresowany tekst. Każde skompresowane słowo zapisane jest w taki sam sposób: w pierwszej linijce jest liczba 1 <= n <= 200 000 oznaczająca liczbę par w skompresowanej formie, w drugiej linijce jest ciąg par: liczby 1 <= X <= 1 000 000 000 i małej litery alfabetu angielskiego C.

Wyjście

W pierwszym wierszu wyjścia wypisz jedną liczbę całkowitą, będącą liczbą wystąpień pierwszego słowa w drugim. Jeśli ta liczba jest dodatnia, w drugim wieszu wypisz dwie liczby oddzielone spacją: miejsce, gdzie pierwszy raz wzorzec wystąpił w tekście i miejsce, gdzie po raz ostatni to zrobił. Przez miejsce wystąpienia rozumiemy indeks w nieskompresowanym słowie pierwszej litery wystąpienia wzorca. Pierwsza litera tekstu ma numer 1.

Przykład

Dla danych:

5 
2 a 3 b 3 a 3 b 3 a
14
4 a 3 b 3 a 3 b 5 a 3 b 3 a 3 b 3 a 3 b 3 a 3 b 2 a 1 d

poprawną odpowiedzią jest:

3
3 23