Pociągi

Limit pamięci: 128 MB

W Bajtocji odbędzie się Parada Kolorowych Pociągów. Na torach technicznych bajtockiego dworca trwają intensywne przygotowania. Na dworcu jest równoległych torów, ponumerowanych od do . Na -tym torze ustawiono pociąg o numerze . Każdy pociąg składa się z wagonów, z których każdy jest pomalowany na jeden z 26 kolorów (oznaczonych małymi literami alfabetu angielskiego). Mówimy, że dwa pociągi wyglądają identycznie, jeśli ich kolejne wagony są tego samego koloru.

Parada będzie polegać na tym, że co minutę stacyjny dźwig zamieni miejscami pewną parę wagonów. Prawdziwa parada odbędzie się jednak dopiero jutro. Dziś dyżurny ruchu Bajtazar bacznie przyglądał się próbie generalnej. Dokładnie zapisał sobie ciąg kolejno zamienianych par wagonów.

Bajtazar nie lubi, gdy zbyt wiele pociągów wygląda identycznie. Chciałby, żebyś dla każdego pociągu policzył maksymalną liczbę pociągów, które w pewnym momencie wyglądają identycznie jak pociąg w owym momencie.

Zadanie

Napisz program, który:

• wczyta opisy pociągów stojących na torach oraz ciąg wykonywanych zamian wagonów,
• dla każdego pociągu wyznaczy maksymalną liczbę pociągów, które w pewnym momencie wyglądają tak samo jak on,
• wypisze wynik.

Wejście

Pierwszy wiersz wejścia zawiera trzy liczby naturalne , oraz (, , ), oznaczające odpowiednio liczbę pociągów, ich długość oraz liczbę wykonywanych zamian wagonów. W kolejnych wierszach znajdują się opisy kolejnych pociągów stojących na torach. -ty z tych wierszy składa się z małych liter alfabetu angielskiego reprezentujących kolory kolejnych wagonów -tego pociągu. Za opisami pociągów znajduje się wierszy zawierających opisy kolejnych zamian, w kolejności ich wykonywania. W -tym z tych wierszy znajdują się cztery liczby całkowite , , , (, , lub ) i opisują one -tą operację wykonywaną przez dźwig - zamianę wagonu numer z pociągu z wagonem pociągu .

Wyjście

Twój program powinien wypisać dokładnie wierszy. -ty wiersz powinien zawierać jedną liczbę całkowitą - liczbę pociągów wyglądających tak samo jak pociąg numer w pewnym momencie czasu.

Przykład

Dla danych wejściowych:

5 6 7
ababbd
abbbbd
aaabad
caabbd
cabaad
2 3 5 4
5 3 5 5
3 5 2 2
1 2 4 3
2 2 5 1
1 1 3 3
4 1 5 6

poprawną odpowiedzią jest:

3
3
3
2
3

Oto wygląd pociągów w kolejnych fazach próby generalnej:

tor 1:  ababbd    ababbd    ababbd    ababbd    aaabbd    aaabbd    aaabbd    aaabbd
tor 2:  abbbbd    ababbd    ababbd    aaabbd    aaabbd    acabbd    acabbd    acabbd
tor 3:  aaabad -> aaabad -> aaabad -> aaabbd -> aaabbd -> aaabbd -> aaabbd -> aaabbd
tor 4:  caabbd    caabbd    caabbd    caabbd    cabbbd    cabbbd    cabbbd    dabbbd
tor 5:  cabaad    cabbad    caabbd    caabbd    caabbd    aaabbd    aaabbd    aaabbc
         (0)       (1)       (2)       (3)       (4)       (5)       (6)       (7)

Dla pociągów 1, 2 i 3 najwięcej podobnych było np. w momencie (4) (były one nawzajem do siebie podobne). Dla pociągu 5 najwięcej mu podobnych było w momentach (5) i (6). Dla pociągu 4 najwięcej podobnych było np. w momencie (2).

Autor zadania: Piotr Stańczyk.