Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWP4_2C - Karta graficzna

Janek pracuje w firmie informatycznej. Na jego nieszczęście był leniwym studentem nie interesującym się niczym co wykraczało poza prześlizgnięcie się przez kolejną sesję. Jak to bywa ze studentami pokroju Janka po ukończeniu studiów ciężko jest o ambitną i pełną wyzwań pracę. To nic - pomyślał nasz bohater i rozpoczął swoją błyskotliwą karierę od skręcania komputerów.

Janek trafił na linię montażową przy której przykręca się kartę graficzną do płyty głównej. To, wydawać by się mogło, proste zajęcie przysparza Jankowi mnóstwa kłopotu. Otóż na płycie głównej znajduje się n otworów o różnych średnicach, na karcie graficznej zaś n śrub o różnych wielkościach - każdemu rozmiarowi otworu oraz śruby przypisana jest litera alfabetu. Aby móc przykręcić kartę do płyty należy dopasować wszystkie śruby do otworów - śruba A musi zostać wkręcona w otwór A, śruba B w otwór B itd. Rzecz w tym, iż bardzo często zdarza się, że karty graficzne produkowane w nielegalnych chińskich fabrykach mają śruby nieprzystosowane do otworów. Stwierdzenie czy karta pasuje do płyty jest o tyle trudne, że karty te są okrągłe i nie ma na nich żadnych oznaczeń typu "góra". Na pierwszy rzut oka można stwierdzić, że do płyty głównej o otworach ABBA nie pasuje karta o śrubach BBAA jednak kartę tą wystarczy nieco przekręcić i okazuje się że otwory są w dobrych miejscach. Stwierdzenie czy karta pasuje to tylko jeden z problemów naszego bohatera, równie trudny jest dla niego proces samego przykręcania. Przebiega on w bardzo charakterystyczny sposób - przykręca się sąsiednie śruby w kierunku zgodnym z ruchem wskazówek zegara, tak aby wyraz powstały z liter przy śrubach był jak najmniejszy leksykograficznie (dla śrub BBAA będzie to AABB). Gdyby tylko Janek umiał napisałby sobie program, który wykona "czarną" robotę za niego lecz jak już wiesz był on słabym studentem i nie ma pojęcia jak to zrobić. Pomóż mu, napisz program który wykona niezbędne obliczenia.

Wejście

W pierwszej linii wejścia znajduje się dokładnie jedna liczba całkowita Z (1 ≤ Z ≤ 105) określająca liczbę zestawów danych.

Każdy zestaw danych składa się z dwóch wyrazów umieszczonych w oddzielnych liniach. Wyraz może składać się z maksymalnie 106 znaków.

Wyjście

Na wyjściu należy w oddzielnej linii dla każdego zestawu danych wypisać 0 jeżeli karty nie da się przykręcić do płyty lub kolejność dokręcania śrub jeżeli jest inaczej.

Przykład

Wejście:

3
ABCABC
ABC
ABABBAB
BBABABA
XYZZXY
ZZXYXY

Wyjście:

0
ABABABB
XYXYZZ

Dodane przez:Maciej Boniecki
Data dodania:2012-03-18
Limit czasu wykonania programu:0.100s-0.200s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:IV Mistrzostwa WWSI w Programowaniu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.