题目描述

PizzaHut公司使用印有单词谜题的桌布来吸引顾客。现需要编写程序在给定的字母矩阵中定位特定单词，并确定其首字母位置和方向。

输入格式

• 第一行：三个整数$L$（行数，$0<L\leq1000$）、$C$（列数，$0<C\leq1000$）和$W$（待查单词数，$0<W\leq1000$）
• 接下来$L$行：每行$C$个字符组成的字母矩阵
• 最后$W$行：每个待查找的单词（长度不超过1000）

输出格式

对每个单词输出一行，包含：

1. 首字母的行号（从0开始）
2. 首字母的列号（从0开始）
3. 方向字母（A-H对应8个顺时针方向，A表示正北方向）

方向编码

A: 北(↑)      E: 南(↓)
B: 东北(↗)    F: 西南(↙)  
C: 东(→)      G: 西(←)
D: 东南(↘)    H: 西北(↖)

样例输入

20 20 10
QWSPILAATIRAGRAMYKEI
AGTRCLQAXLPOIJLFVBUQ
TQTKAZXVMRWALEMAPKCW
LIEACNKAZXKPOTPIZCEO
FGKLSTCBTROPICALBLBC
JEWHJEEWSMLPOEKORORA
LUPQWRNJOAAGJKMUSJAE
KRQEIOLOAOQPRTVILCBZ
QOPUCAJSPPOUTMTSLPSF
LPOUYTRFGMMLKIUISXSW
WAHCPOIYTGAKLMNAHBVA
EIAKHPLBGSMCLOGNGJML
LDTIKENVCSWQAZUAOEAL
HOPLPGEJKMNUTIIORMNC
LOIUFTGSQACAXMOPBEIO
QOASDHOPEPNBUYUYOBXB
IONIAELOJHSWASMOUTRK
HPOIYTJPLNAQWDRIBITG
LPOINUYMRTEMPTMLMNBO
PAFCOPLHAVAIANALBPFS
MARGARITA
ALEMA
BARBECUE
TROPICAL
SUPREMA
LOUISIANA
CHEESEHAM
EUROPA
HAVAIANA

样例输出

0 15 G
2 11 C
7 18 A
4 8 C
16 13 B
4 15 E
10 3 D
5 1 E
19 7 C
11 11 H

题目来源

2002年西南欧地区竞赛