URI Online Judge | 3166

Finding Words on Main 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 main 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

3 20 20
google
morosidade
coragem
LjUtSbDvScXhVgVrMkBh
UaOoRvArAuAmWdBcUaLb
QiNcXwIxVcVxUxAdTkJh
AfWeDwVcMfLjQwFhTuBp
MmTxerSbTjWpMcJqMfWk
WdRgMdGwUtWoNmJfRrBw
GtIaGwAaMcThVeOfQdHe
UxOdCdPDDjobGmGqJmSj
GrUsTlGwiaHRGjBoHwEt
PoPsXpGpQSGmauXkNmTa
UrVgWoFwGhOaPGLoSwAt
OaKwDxLuUrSRJiEpHaCb
DbOqOpJwMoCfonXmUmPs
EoLbKjHeTdGgAMJsQsQb
HiEbDqSxEpLiAfMhCwBu
WaIvJdPfHmHmOiUbBdDd
UtFpLbVkLcFhLmAvIkPa
WcGqFrCkBkBeBsUwHwFr
CjCsUjMeIgHkRfCtFgMm
HxThEqQsRxKkPfXgEsUk

4 Palavra "google" inexistente
1 Palavra "morosidade" na diagonal principal
2 Palavra "coragem" acima da diagonal principal