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}s\_1$ och $s_{2}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}l\_1$ respektive $l_{2}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}s\_1$ hamnar i den första textrutan och $s_{2}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 $2727$ 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}10^6$ tecken.

입력

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

Den första raden innehåller en sträng $s_{1}s\_1$ och ett heltal $l_{1}l\_1$ ($1\le \mathrm{\mid }{s}_1\mathrm{\mid }\le l_1\le 10001\; \backslash leq\; |s\_1|\; \backslash leq\; l\_1\; \backslash leq\; 1000$).

Den andra raden innehåller en sträng $s_{2}s\_2$ och ett heltal $l_{2}l\_2$ ($1\le \mathrm{\mid }{s}_2\mathrm{\mid }\le l_2\le 10001\; \backslash leq\; |s\_2|\; \backslash leq\; l\_2\; \backslash leq\; 1000$).

Både $s_{1}s\_1$ och $s_{2}s\_2$ innehåller bara små bokstäver från "a" till "z".

출력

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=1K\; =\; 1$ ska sekvensen vara så kort som möjligt, annars räcker det med att den har högst ${10}^{6}10^6$ tecken. Det är garanterat att om det finns en lösning, så finns det en med högst ${10}^{6}10^6$ tecken.