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.