A terrible word search: find the word DREAM in this grid.

woordzoeker
Vind het woord DREAM in dit rooster.
woordzoeker
Vind het woord DREAM in dit rooster.

Input

The first line contains a word $$w$$ that only consists of letters.

The second line contains a number $$n \in \mathbb{N}_0$$. This is followed by another $$n$$ lines, each containing a fixed number of letters (at least as much as there are letters in the word $$w$$). These $$n$$ lines make up the grid of a word search in which the word $$w$$ can be read just once from left to right or from right to left. When reading the word, no distinction is made between uppercase and lowercase letters.

Output

The lines that make up the grid of the word search, where only the letters that spell the word are in uppercase and all other letters in lowercase.

Example

Input:

Dream
4
AEaArAeAae
mmDddaarra
mmaeMAerDR
RraMeEmMEA

Output:

aeaaraeaae
mmdddaarra
mmaeMAERDr
rrameemmea

Example

Input:

DREAM
30
EAEEDEDEMDREAERRMERRREDMEAMAMADRAARR
ADARMEARREREREARMEDRMEMREMRRAEEAEMMM
AEARERDMRADADDERRRRRAMDADRRADEMARRMD
MEEEMMMRREERMEDAEEMDRDDMMAEEDEEADMEA
DRARRDEEAERREDEARAAAREDRDERADMRMRERA
DMRMEMRARRDEEEADDMDRAAAEAAARRARRMRAD
AEAEDDEREDRADADEAREAMRRARRRDDAREADER
RDMMDERAEAMERARRREEMAADEMDARAMDDDEAA
EDAMMADAMMEEEEMDRARRDAAMERMRDDREMRAE
MMDARDEEEDEEAMEDDAAREAEAMDRAAAEDAMER
EEADDEMRAMMRADERMRRADEDEADEMMAARAAAM
ERDEDDRMEAMADARMEMRRDRMAEADADEMRMEMD
DDRADARMREDMRMDDEARRDMRRAMDEADERDDRE
MEMEAMAADEEERMDRADMDEEMAEDAADARERMAA
DADEEDAEDERADMERAEREEEMEEEMRDDDMAMED
RDEMMDRMRARMRDREMEEAARMRAARAERRDMDED
DDDMMMEREMAEEDDDEEADREEEMAMEDERRRAMM
RDMEMMDRREAAAMRREDEEMMMEMRDARDDDDEDD
RAAADDAEDDRARMDRRMAARRADAAMREERREDAM
EDRAEEAMRREADAEAMMMERDAMADAEDRRMDMER
EADMDREEDDEAERRDDEADDDARDAERERRDRAMD
EMRRARDMDMEERDERRRERMADRMREMREDREERR
DEDMEDRAEMDRRDERMMMEMARAAAMRRDDRAMAA
DADRRDEADEREDEEDDEMMEMDDAMMDDDRARARA
EAAMEARDEMEEMEDAREMRRRDEEEEAARAEEEDM
AMRDDAEDARARAEEADMMMDARMEARDAAREEDEM
RRRMRADEMRAAEEMEEADREAMAAMEMRAMRDEEM
EDRADMDMMMDDAMAMREDAEAMMARMADMEDRARE
ADDARMEMARDAMADEDAARAEREADRRAERAMMRR
ADAMDAMADMMRREDAMRDDAAADMEEAAEAAAERM

Output:

eaeededemdreaerrmerrredmeamamadraarr
adarmearrererearmedrmemremrraeeaemmm
aearerdmradadderrrrramdadrrademarrmd
meeemmmrreermedaeemdrddmmaeedeeadmea
drarrdeeaerredearaaaredrderadmrmrera
dmrmemrarrdeeeaddmdraaaeaaarrarrmrad
aeaedderedradadeareamrrarrrddareader
rdmmderaeamerarrreemaademdaramdddeaa
edammadammeeeemdrarrdaamermrddremrae
mmdardeeedeeameddaareaeamdraaaedamer
eeaddemrammradermrradedeademmaaraaam
erdeddrmeamadarmemrrdrmaeadademrmemd
ddradarmredmrmddearrdmrramdeaderddre
memeamaadeeermdradmdeemaedaadarermaa
dadeedaederadmeraereeemeeemrdddmamed
rdemmdrmrarmrdremeeaarmraaraerrdmded
dddmmmeremaeedddeeadreeemamederrramm
rdmemmdrreaaamrredeemmmemrdarddddedd
raaaddaeddrarmdrrmaarradaamreerredam
edraeeamrreadaeammmerdamadaedrrmdmer
eadmdreeddeaerrddeadddardaererrdramd
emrrardmdmeerderrrermadrmremredreerr
dedmedraemdrrdermmmemaraaamrrddramaa
dadrrdeaderedeeddemmemddammdddrarara
eaameardemeemedaremrrrdeeeeaaraeeedm
amrddaedararaeeadmmmdarmeardaareedem
rrrmrademraaeemeeaDREAMaamemramrdeem
edradmdmmmddamamredaeammarmadmedrare
addarmemardamadedaaraereadrraerammrr
adamdamadmmrredamrddaaadmeeaaeaaaerm

Epilogue

"The Impossible Dream (The Quest)" is a song composed by Mitch Leigh1, with lyrics written by Joe Darion2. It is the most popular song from the 1965 Broadway musical Man of La Mancha3 and is also featured in the 1972 film4 of the same name starring Peter O'Toole5.

The complete song is first sung by Don Quixote6 as he stands vigil over his armor, in response to Aldonza's (Dulcinea7) question about what he means by "following the quest". It is reprised partially three more times — the last by prisoners in a dungeon as Miguel de Cervantes8 and his manservant mount the drawbridge-like prison staircase to face trial by the Spanish Inquisition9.