Myrmecia pilosula¹ is een giftige mierensoort die inheems is in Australië, en voornamelijk voorkomt in Tasmanië. De mieren staan erom bekend dat ze ver kunnen springen. Bij mensen veroorzaakt een beet van deze springmieren doorgaans slechts een milde plaatselijke reactie, maar het is één van de weinige mieren waarvan het mierengif in zeldzame gevallen toch dodelijk kan zijn voor de mens. Tussen 1980 en 2000 waren er vier sterfgevallen ten gevolge van anafylactische shocks² — acute, ernstige allergische reacties op een lichaamsvreemde stof — allemaal in Tasmanië. Het gif veroorzaakt ongeveer 90% van de Australische mierenallergieën.

Opgave

Als mieren zich verplaatsen, dan doen ze dat doorgaans in één lange rij waarbij elke mier zijn voorganger volgt. Maar wat gebeurt er als twee rijen mieren elkaar treffen als ze in tegenovergestelde richting lopen op een rand waar ze elkaar niet kunnen passeren? Bij de Myrmecia pilosula beginnen de mieren dan gewoon over elkaar heen te springen. In deze opgave vragen we je om dit gedrag te simuleren.

Invoer

De invoer bestaat uit twee regels die enkel hoofdletters bevatten. Elke regel stelt een rij mieren voor, waarbij de twee rijen in tegenovergestelde richting lopen. Elke mier wordt voorgesteld door een unieke hoofdletter. In totaal zijn er dus nooit meer dan 26 mieren. De eerste regel bevat de mieren die vanaf links komen aanlopen. De tweede regel bevat de mieren die vanaf rechts komen aanlopen. De mieren staan telkens in de volgorde waarin ze lopen: de eerste mier loopt dus voorop!

Uitvoer

De uitvoer bestaat uit een aantal regels die telkens de volgorde van de mieren aanduiden terwijl ze elkaar aan het passeren zijn. De eerste regel omschrijft de volgorde van de mieren op het ogenblik dat de twee rijen elkaar op de rand tegenkomen. Als twee mieren elkaar in een vorige stap rechtstreeks aankijken (dus zonder dat er een andere mier tussen staat), dan wisselen die twee mieren in een volgende stap van plaats. De laatste stap die moet uitgeschreven worden, is de stap waarin er in een volgende stap geen mieren meer van plaats wisselen.

Voorbeeld

Invoer:

CBA
DEFG

Uitvoer:

ABCDEFG
ABDCEFG
ADBECFG
DAEBFCG
DEAFBGC
DEFAGBC
DEFGABC

Grafische simulatie van deze twee rijen springende mieren die elkaar stap voor stap passeren: