URI Online Judge | 3167

Finding Words on Secondary Diagonal

By Elder Sobrinho, UFTM BR Brazil

Timelimit: 3

In Algelandia, the favorite pastime is the Word Search puzzles. One of these has the following characteristics:

  1. The words occur only in the direction of the secondary diagonal;
  2. Words can occur with uppercase and/or lowercase;
  3. If a given word exists, it occurs only once and at any position on the diagonal;
  4. Words can exist in both normal and inverted form, that is, the diagonal reading could be top-down or bottom-up form.

In this context, the figure below demonstrates how the words “workshop”, “videogame” and “scanner” can occur in the game.

Input

The first line contains three integers: 1) N that represents the number of words that we will check if there are in the game, limited by [1,100]; 2) M that represents the number of lines in the matrix, limited by [10,1000]; 3) P that represents the number of columns in the matrix, limited by [10,1000]. In addition, each N-words follows the limit: [6,100].

Output

Depending on the existence of each N-word, inform:

Where X is the searched word, moreover, X must be in lower case.

Input Sample Output Sample

7 20 20
equivocado
maturidade
prescindir
insight
designer
efemero
feeling
SkCaBhRgVjAsDsHeJcEk
FuNmHdIkWiJsOaRmStPm
RwOuHsGOLcHtWtRvBeAf
MaHuQnRwJbIoAbJrXjXt
IoUjIEVgDdJeAvEpTbAv
IuAlmvBresDppdEmRnSh
QreEUrTSRcOraQAuJgNl
BEfpQaitBnEdUdLqMpWp
FeXgMgWoAsIiAnIpIfAm
AfGqnvBkCrVkNnKgXmKj
XoNeIoKIuoRxSsUqOsFn
NirsItntCcCiXfWsDnMq
SmGlEdAAVgGvCiSeEpKb
VeNlIMDjMhMgBmHgGrLw
OmBrIoGateVcXgTbPfXo
HaAjAfKiEdRuMgXgQwFv
VtWrWsSuNvFwGlWrLuWi
BeJbRqGuXkHrJsMnGlCc
RwXbViXmUdMeIpQgKvOe
GvTmJjWfRmJkVcVgVrCr

1 Palavra "equivocado" na diagonal secundaria
2 Palavra "maturidade" acima da diagonal secundaria
2 Palavra "prescindir" acima da diagonal secundaria
3 Palavra "insight" abaixo da diagonal secundaria
2 Palavra "designer" acima da diagonal secundaria
2 Palavra "efemero" acima da diagonal secundaria
2 Palavra "feeling" acima da diagonal secundaria