Sopa de lletres P18660

Statement

thehtml

Feu un programa que resolgui sopes de lletres! Les paraules es poden trobar escrites horitzontalment (d’esquerra a dreta), verticalment (de dalt a baix) o diagonalment (d’esquerra a dreta i de dalt a baix).

Entrada

L’entrada consisteix de diferents jocs de proves. Cada joc de proves conté tres parts: La primer part conté tres naturals x, m i n no nuls. La segona part és una seqüència de x paraules. La tercera part és una matriu amb m files i n columnes que representa la sopa de lletres. Tots els símbols que apareixen a les paraules i a la sopa són lletres minúscules a,…,z.

Sortida

Per a cada joc de proves cal reproduir la matriu d’entrada, però canviant totes les lletres que formen part de paraules en majúscules. Separeu cada lletra de la sopa per un espai en blanc; separeu cada joc de proves per una línia en blanc.

Public test cases

Input

5 6 7

maria jordi joan pere marta

r e m a r i a 
x y a t r w q
j e r e s q s
o o t d a q d 
a v a f h w x
n i i n d a z 

5 6 8

felix jordi joan pere marta

r e m a r i a q
x y a t r w f e
j e r e s q e i
o o t d a q l o
a v a f h w i s
n i i n d a x m

Output

r e M A R I A
x y A t r w q
J e R e s q s
O O T d a q d
A v A f h w x
N i i N d a z

r e M a r i a q
x y A t r w F e
J e R e s q E i
O O T d a q L o
A v A f h w I s
N i i N d a X m

Information

Author: Jordi Petit
Language: Catalan
Other languages: English
Official solutions: C++
User solutions: C C++