In Algelandia, the favorite pastime is the Word Search puzzles. One of these has the following characteristics:
- The words occur only in the direction of the main diagonal;
- Words can occur with uppercase and/or lowercase;
- If a given word exists, it occurs only once and at any position on the diagonal;
- 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.
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].
Depending on the existence of each N-word, inform:
- 1 Palavra "X" na diagonal principal
- 2 Palavra "X" acima da diagonal principal
- 3 Palavra "X" abaixo da diagonal principal
- 4 Palavra "X" inexistente
Where X is the searched word, moreover, X must be in lower case.
3 20 20
4 Palavra "google" inexistente
1 Palavra "morosidade" na diagonal principal
2 Palavra "coragem" acima da diagonal principal