Wstęp do programowania w C++

Dane są dwa multizbiory wyrazów. Twoim zadaniem jest wybranie dokładnie po jednym wyrazie z każdego multizbioru. Z połączenia wybranych wyrazów powinien powstać palindrom o maksymalnej możliwej długości. Wyrazy możemy łączyć w dowolnej kolejności. Podczas sprawdzenia czy nowo powstałe słowo jest palindromem ignorujemy wielkość liter. Znajdź szukany palindrom.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita a ∈ [1;1000] określająca liczbę wyrazów pierwszego multizbioru. W następnych a wierszach znajdują się słowa należące do pierwszego multizbioru. W kolejnej linii znajduje się jedna liczba całkowita b ∈ [1;1000] określająca liczbę wyrazów drugiego multizbioru. W następnych b wierszach znajdują się słowa należące do drugiego multizbioru. Każdy wyraz składa się z małych lub wielkich liter alfabetu angielskiego, zaś jego długość nie przekracza 10.

Wyjście

W pierwszym wierszu wyjścia należy wypisać długość maksymalnego palindromu albo 0 w przypadku gdy nie można żadnego utworzyć. Jeżeli palindrom został znaleziony to w drugiej linii należy go wypisać zachowując oryginalną wielkość liter. W przypadku, gdy istnieje wiele palindromów o maksymalnej długości wystarczy wypisać dowolny z nich.

Przykład

Wejście:

3
Ab
xX
DE
3
Ba
Pl
xX

Wyjście:

4
AbBa

Wyjaśnienie do przykładu:

Dla podanych zbiorów maksymalna długość palindromu jaki możemy uzyskać wynosi 4. Możliwe do uzyskania palindromy to:

• AbBa
• BaAb
• xXxX