Problem E
Lösenordsnoja

Agenten August har ett problem som han behöver din hjälp med. August har två mejladdresser som han använder för att kommunicera med sina agentkollegor. Men han misstänker att någon okänd person sedan en tid tillbaka övervakar varje knapptryckning han gör. Bland annat känner denna person vid det här laget till de två lösenord som August använder till mejladdresserna.

De två lösenorden $s_1$ och $s_2$ är textsträngar som består av bokstäverna “a”-“z”. De två lösenorden skrivs in i två olika textrutor, med maxlängd $l_1$ respektive $l_2$. Maxlängden hos en textruta är ett positivt heltal som avgör hur många bokstäver som kan stå i textrutan. Om man trycker på en bokstav så hamnar den bokstaven längst bak i textrutan, förutom om antalet bokstäver som står i textrutan är lika med maxlängden, för då händer ingenting.

För att orsaka förvirring skulle August vilja ha en sekvens av knapptryckningar som åstadkommer att $s_1$ hamnar i den första textrutan och $s_2$ hamnar i den andra. På så sätt kan den okända övervakaren inte veta vilken mejladdress August använder. Din uppgift är att konstruera en sådan sekvens. Det finns $27$ knappar du kan använda, bokstäverna “a”-“z” och “<” (backspace). Om backspace trycks in så försvinner den sista bokstaven i rutan (om det finns minst en bokstav i rutan, annars händer ingenting).

För att få full poäng ska du hitta en sekvens som innehåller så få tecken som möjligt. I vissa testgrupper behöver du bara hitta en sekvens som har max ${10}^6$ tecken.

Indata

Den första raden innehåller ett heltal $K\in \{0,1\}$, som indikerar om du behöver hitta en kortaste lösning. Om $K=1$ måste du hitta en kortaste lösning, annars räcker det med att den har max ${10}^6$ tecken.

Den första raden innehåller en sträng $s_1$ och ett heltal $l_1$ ($1\le |s_1|\le l_1\le 1000$).

Den andra raden innehåller en sträng $s_2$ och ett heltal $l_2$ ($1\le |s_2|\le l_2\le 1000$).

Både $s_1$ och $s_2$ innehåller bara små bokstäver från “a” till “z”.

Utdata

Om det inte finns en sekvens av knapptryckningar så som beskrivs i uppgiften, skriv ut ett utropstecken “!”.

Annars, skriv ut en sträng bestående av tecknen “a”-“z” och “<”, den sekvens du hittade. Om det finns flera lösningar kan du skriva ut vilken som helst. Om $K=1$ ska sekvensen vara så kort som möjligt, annars räcker det med att den har högst ${10}^6$ tecken. Det är garanterat att om det finns en lösning, så finns det en med högst ${10}^6$ tecken.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempel 1

När det första tecknet “<” trycks ner så händer ingenting eftersom det inte står något i rutorna. Efter de följande fyra knapptryckningarna kommer det stå “bara” i den andra rutan precis som vi vill, däremot kommer det stå “bar” i den första eftersom den har maxlängd $3$. Därefter raderas de två sista bokstäverna så att det står “b” i den första rutan och “ba” i den andra. Till slut skrivs “ra” in så att det står “bra” och “bara”. Notera att eftersom det första tecknet är helt onödigt så hade det gått att lösa med en kortaste sekvens, men det gör inget eftersom $K=0$.

0
bra 3
bara 5

<bara<<ra

0
password 10
secret 12

!

1
gg 2
ogeggig 8

ogegg<<ggig