SPOJ.com - Problem PROG0332

PROG0332 - Bodyguards

no tags

Each position of a rectangular grid is either filled with an uppercase or a lowercase letter. Your task is to discover the hidden word that can be found by traversing the grid from left to right, and from top to bottom and only retaining the letters that are protected. We say that a letter is protected if it is a lowercase letter that is surrounded above, below, to the left and to the right by exactly three uppercase letters (the bodyguards). Note that lowercase letters at the edges of the grid can also be protected, except for those that are at each of the four corners of the grid.

Input

The first line of the input contains a number $t \in \mathbb{N}_0$ that indicates the number of rows of the rectangular grid. This is followed by another $t$ lines, each containing the same number of letters. Each letter can be written as an uppercase or a lowercase letter. All these letters form the grid into which a secret word was hidden.

Output

The word that is hidden into the grid.

Example

Input:

42
STxJCNWwaVzWKLLJylrhHVbFLliySjgobFXKfTKcgREbirLqsfRkhQcfuwVeMCAoepESTsJfNxivgS
AWuqASpwCXmsbmVasQliopiBizzmJakyktwbuNcLfvQsuKxVgnMWTraeVhzavKGuIEScqfDupXHemH
DQacnzwDESSiTdbsjGfvYvsJaNipDKcuszZZIAxuCeppamCfdvtUymYxdpCreZSkrpLqIitseTagJd
ewzNYkcPBqfhmxkCQFAyaldUuTqOLVaTrkjodWqwhDiCCqtisRzkwPVBxCdxLbllXlrgjrikjEcexg
fZWqHvmhgqdVnasDYVzBDYdOrayNYViIQtkYmrkOpdkOxpkWfgCSyRuPmRkIFoUDwknAobpkahKCyo
RFQTuqtqaCnkSUkMODYycSbFpzkwiBlHHcGdwpGHibzqoYTUWkFkxkRLhxiAJhrtxQcpgQkdPzhmog
KBVOwBHAcCLefpaNziaontjwfBCMpVdkkzRaELylneuKxqqqEcAzfxPaklwLHibKyYrKPQeUZiFVOw
nstBdiLNlNfzkVJKrSdYdfKBCvhbuNueMtmqtIkasAEooLYzkqGvBPBwaFXunmVUlxvappySIuuaEM
JYntfqzWeFrtYdaHfewTvoODQjEwLLhuZzUQhsuIVLSvwhvBNTvcBrwRtzHzPXHanlSULEFOvwWwek
ksxhyXtnzwcTrmUEezwJvGNnudIqNIZMcmcNPhjAYNtSwnijggveofkcjqCjjINmvHfnQahrvLTnBC
rAkMVYPsVJxqWvkKVFhMesEpqPvgdjeuqvukeIrHFYpazmMvQyxkGWXrujUgpeEHEKgbbbGocvmjHD
JZtoovxxXQOfZZzVIyqjmiuwgdoGZCyxNuGuxwrAuqfLPgraGLnrBmMTbdcJsbubXIioHZMNcmCjtL
rEanVeizMoHeqOglSqKSoqBpRUSHTlbRiteWipkdlNNothnTRWdeiHOdfClEaWtzbwXnrlpzrfZZlv
xFPotANBSrtGxcWhGeWVgFPnNYuiYsauqKnueIznxvcqsmwsctIChdutEHzziLXTOoHNiglhGKDluO
vLCKcmyrLKcXUoNbWkqnfqjfVluzeYYKbdAhLUFmlDgCnEwzkoTFGNzaPFZgZZuHJmIdmTCEBYShmZ
lATNWSggFIxgquKbsrMrKQjkUboygbeqjlAmtqflghfmeKHsGSiqkzamxiMygfLwKjqeZRLvTvfSqF
nmNgqZhtSxtRbDmIThkbjYciDQGnKLwLKejMBYGsRCiepUBnDyzQCilFKuIvYqkTxqgxmCHHJaiozf
ubIVjdrNoykJjHGAGlHOweemEfurBolKancQDhRaCSjZammaabSUcqtSTkeynExjpXTXaOAwigYvgL
uBHFHTqVsIDjfuazedsgLVCXzlZuTsuRzatTrEDbjAhcGkDhhfoNqdEanrdDrnmodnZPkyKsjlCcal
zaMiqosjxIfwhZCffnccoqibwStaOemWkXRhjivakcDjjkPaoqodfpyqQMFraSUeEdRuzeCbByQaoQ
nczaiXVEzqdGAcHPUAPZrLzwOVyRuBOiqCpbpqjbipwTstmUdtAoNFlKStfbihskZgazWlkdpvmpBa
dnOSpTUmcAudFSubwmyTkniFLTczMJXslRgIrseDdodrBbnimSElyAjjjmXujpvnczfhpUyodjHstz
NeqguTDxrundHOaJeIgduRKIfvtowyjIFytHhaOSBfuwgyDjthMSdlPyzMBHiqJtZglrzxqoUcuULV
EciavmYFhCSvZniceMJXDTfmqIFgdQzJluJalchODIJcexbpKdburhDZDCirtsfnKtwZMGkDTpqkDY
qqjPSqCBqptfJgvudFmfefiZentdmMumqAYOhBmZyzFlkAggURzlvTPAMdhrhxBVLPXZWrzGRTOryD
tJFDdvFVNizwqiBOZnwtnTimfuMnjrctUYvVxFpqphytGSMyevnJlFRTxmPsIbMudotpilhidiCguO
aLHNfRwDjeKJHEWgevVSzDlduyYbdlPbtJAcgbfHbNWkIewfBITUdtchvejuWvqxuKGTQIwuKnBbWo
AcoqwyZKcYokarRgNzvqmZDXdbDHzlpcskqrQvsrlSnxJxtQXHybUZJMRiwekqtKhyhtcYWJgcheth
laDpnfPYlKqgnmInvzfSZJlswntRxlGBtgMIEghwmkjqsskjnZgbrTTkpwhsJceRtcvirumgjuaVba
UVHSrBwAvEAmtsIhieFQRAkPdzmAAFdrXklphFCJyVDPWzxZtlhGyxLjCwPZgjiIMgTSkoAraXmvHm
PUKNfUInpEMsqIWJimbcNGkRPiHHVaabhBeRwxAvxunpclGbBlhpXxklRnDLoAWIumwgOCmuxrjozY
fpfglcloumObAbwsqDBbqatONahwoibRnAfOGoWtNdqNZipRvijlbiLSnjrfcEtgyeUcoxfxJOKayt
bpKABqvoYxVwTwgcAAlttrTWnjttvaPeaGliwpaeemMsxeQhrFIZnbeftUqolNjXXnIsvdBcjidvRm
bTUUWpvmSwtjOmmlkbzciQvBzviwAyzlIidogRgEFBLyaoDOMMcsVHHKafwqEQyqetjwxszOsTkjzD
uQCVjDXYGxrmxlCLbfBhkeDZRvjMLtswhlsqcZkoniXiQycpudogUVnBnLtMczyteAVuvvxcvIGcpC
RpMADWqrOeOkQWDhxnIRcrsilnHZTFuxuSyWdkXxrdafytMiHVwxxEFfjnfAnDZIpwGcpOSYJUFPpV
sDaScyxcOdHbkAFexoZeSTeRwfJucWUXSmrMhlhgpvvebgrgMbLvrtSmpiSxoQVINhYakxactRVqyW
kCLnnlXVDrXXrSGiOThmVLnSxytdvssnXdesLwGRAKHJigvupYPDjfseaTdiWStrgbWynTBexaNmxU
YxsgvzGHIerMXfQdqhjZbBwVAeWlssraEtmfNdbhtbxsWutPcbZsqnmZKjffafnvCofFtXFOmpnfBH
nayerrFAAljgMYGypDwoFNxcbyssnDsQVocYogRLMIUlDyYSevJrzLiaSbnBBopdBKywzNmHLPVUHM
DzRIvBiIKFMgnxAIQyZeyvavdovklxoPASWLreVnnZMyAwVSCaoQZJUxdgTUULoinmpSMFElKjztsY
qkMSdIXbryLRfqtvNWLdKYAVLYwNTZoOxrRokmddrVnofychTienmtYhMsrckppQuiZbfHUWhtbpjW

Output:

cartographer

We geven je een rechthoekig rooster waarin op elke positie een hoofdletter of een kleine letter staat. Je vindt op basis van dit rooster een verborgen woord door het rooster van links naar rechts en van boven naar onder te doorlopen, en alle beschermde letters die je daarbij tegenkomt achter elkaar te zetten. Een letter is beschermd als het een kleine letter is die boven, onder, links en rechts omgeven wordt door exact drie hoofdletters (de bodyguards). Merk op dat kleine letters op de rand van het rooster dus evengoed beschermd kunnen zijn, tenzij ze in één van de vier hoekpunten van het rooster gelegen zijn.

Invoer

De eerste regel van de invoer bevat een getal $t \in \mathbb{N}_0$ dat het aantal rijen van het rechthoekig rooster aangeeft. Daarna volgen $t$ regels die telkens een vast aantal letters bevatten. Elke letter kan zowel als hoofdletter als als kleine letter geschreven zijn. Alle letters samen vormen het rooster waarin een woord verborgen zit.

Uitvoer

Het woord dat in het rooster verborgen zit.

Voorbeeld

Invoer:

42
STxJCNWwaVzWKLLJylrhHVbFLliySjgobFXKfTKcgREbirLqsfRkhQcfuwVeMCAoepESTsJfNxivgS
AWuqASpwCXmsbmVasQliopiBizzmJakyktwbuNcLfvQsuKxVgnMWTraeVhzavKGuIEScqfDupXHemH
DQacnzwDESSiTdbsjGfvYvsJaNipDKcuszZZIAxuCeppamCfdvtUymYxdpCreZSkrpLqIitseTagJd
ewzNYkcPBqfhmxkCQFAyaldUuTqOLVaTrkjodWqwhDiCCqtisRzkwPVBxCdxLbllXlrgjrikjEcexg
fZWqHvmhgqdVnasDYVzBDYdOrayNYViIQtkYmrkOpdkOxpkWfgCSyRuPmRkIFoUDwknAobpkahKCyo
RFQTuqtqaCnkSUkMODYycSbFpzkwiBlHHcGdwpGHibzqoYTUWkFkxkRLhxiAJhrtxQcpgQkdPzhmog
KBVOwBHAcCLefpaNziaontjwfBCMpVdkkzRaELylneuKxqqqEcAzfxPaklwLHibKyYrKPQeUZiFVOw
nstBdiLNlNfzkVJKrSdYdfKBCvhbuNueMtmqtIkasAEooLYzkqGvBPBwaFXunmVUlxvappySIuuaEM
JYntfqzWeFrtYdaHfewTvoODQjEwLLhuZzUQhsuIVLSvwhvBNTvcBrwRtzHzPXHanlSULEFOvwWwek
ksxhyXtnzwcTrmUEezwJvGNnudIqNIZMcmcNPhjAYNtSwnijggveofkcjqCjjINmvHfnQahrvLTnBC
rAkMVYPsVJxqWvkKVFhMesEpqPvgdjeuqvukeIrHFYpazmMvQyxkGWXrujUgpeEHEKgbbbGocvmjHD
JZtoovxxXQOfZZzVIyqjmiuwgdoGZCyxNuGuxwrAuqfLPgraGLnrBmMTbdcJsbubXIioHZMNcmCjtL
rEanVeizMoHeqOglSqKSoqBpRUSHTlbRiteWipkdlNNothnTRWdeiHOdfClEaWtzbwXnrlpzrfZZlv
xFPotANBSrtGxcWhGeWVgFPnNYuiYsauqKnueIznxvcqsmwsctIChdutEHzziLXTOoHNiglhGKDluO
vLCKcmyrLKcXUoNbWkqnfqjfVluzeYYKbdAhLUFmlDgCnEwzkoTFGNzaPFZgZZuHJmIdmTCEBYShmZ
lATNWSggFIxgquKbsrMrKQjkUboygbeqjlAmtqflghfmeKHsGSiqkzamxiMygfLwKjqeZRLvTvfSqF
nmNgqZhtSxtRbDmIThkbjYciDQGnKLwLKejMBYGsRCiepUBnDyzQCilFKuIvYqkTxqgxmCHHJaiozf
ubIVjdrNoykJjHGAGlHOweemEfurBolKancQDhRaCSjZammaabSUcqtSTkeynExjpXTXaOAwigYvgL
uBHFHTqVsIDjfuazedsgLVCXzlZuTsuRzatTrEDbjAhcGkDhhfoNqdEanrdDrnmodnZPkyKsjlCcal
zaMiqosjxIfwhZCffnccoqibwStaOemWkXRhjivakcDjjkPaoqodfpyqQMFraSUeEdRuzeCbByQaoQ
nczaiXVEzqdGAcHPUAPZrLzwOVyRuBOiqCpbpqjbipwTstmUdtAoNFlKStfbihskZgazWlkdpvmpBa
dnOSpTUmcAudFSubwmyTkniFLTczMJXslRgIrseDdodrBbnimSElyAjjjmXujpvnczfhpUyodjHstz
NeqguTDxrundHOaJeIgduRKIfvtowyjIFytHhaOSBfuwgyDjthMSdlPyzMBHiqJtZglrzxqoUcuULV
EciavmYFhCSvZniceMJXDTfmqIFgdQzJluJalchODIJcexbpKdburhDZDCirtsfnKtwZMGkDTpqkDY
qqjPSqCBqptfJgvudFmfefiZentdmMumqAYOhBmZyzFlkAggURzlvTPAMdhrhxBVLPXZWrzGRTOryD
tJFDdvFVNizwqiBOZnwtnTimfuMnjrctUYvVxFpqphytGSMyevnJlFRTxmPsIbMudotpilhidiCguO
aLHNfRwDjeKJHEWgevVSzDlduyYbdlPbtJAcgbfHbNWkIewfBITUdtchvejuWvqxuKGTQIwuKnBbWo
AcoqwyZKcYokarRgNzvqmZDXdbDHzlpcskqrQvsrlSnxJxtQXHybUZJMRiwekqtKhyhtcYWJgcheth
laDpnfPYlKqgnmInvzfSZJlswntRxlGBtgMIEghwmkjqsskjnZgbrTTkpwhsJceRtcvirumgjuaVba
UVHSrBwAvEAmtsIhieFQRAkPdzmAAFdrXklphFCJyVDPWzxZtlhGyxLjCwPZgjiIMgTSkoAraXmvHm
PUKNfUInpEMsqIWJimbcNGkRPiHHVaabhBeRwxAvxunpclGbBlhpXxklRnDLoAWIumwgOCmuxrjozY
fpfglcloumObAbwsqDBbqatONahwoibRnAfOGoWtNdqNZipRvijlbiLSnjrfcEtgyeUcoxfxJOKayt
bpKABqvoYxVwTwgcAAlttrTWnjttvaPeaGliwpaeemMsxeQhrFIZnbeftUqolNjXXnIsvdBcjidvRm
bTUUWpvmSwtjOmmlkbzciQvBzviwAyzlIidogRgEFBLyaoDOMMcsVHHKafwqEQyqetjwxszOsTkjzD
uQCVjDXYGxrmxlCLbfBhkeDZRvjMLtswhlsqcZkoniXiQycpudogUVnBnLtMczyteAVuvvxcvIGcpC
RpMADWqrOeOkQWDhxnIRcrsilnHZTFuxuSyWdkXxrdafytMiHVwxxEFfjnfAnDZIpwGcpOSYJUFPpV
sDaScyxcOdHbkAFexoZeSTeRwfJucWUXSmrMhlhgpvvebgrgMbLvrtSmpiSxoQVINhYakxactRVqyW
kCLnnlXVDrXXrSGiOThmVLnSxytdvssnXdesLwGRAKHJigvupYPDjfseaTdiWStrgbWynTBexaNmxU
YxsgvzGHIerMXfQdqhjZbBwVAeWlssraEtmfNdbhtbxsWutPcbZsqnmZKjffafnvCofFtXFOmpnfBH
nayerrFAAljgMYGypDwoFNxcbyssnDsQVocYogRLMIUlDyYSevJrzLiaSbnBBopdBKywzNmHLPVUHM
DzRIvBiIKFMgnxAIQyZeyvavdovklxoPASWLreVnnZMyAwVSCaoQZJUxdgTUULoinmpSMFElKjztsY
qkMSdIXbryLRfqtvNWLdKYAVLYwNTZoOxrRokmddrVnofychTienmtYhMsrckppQuiZbfHUWhtbpjW

Uitvoer:

cartographer

Submit solution!

Added by:	Peter Dawyndt
Date:	2013-02-16
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC
Resource:	None