#include #include #include #include using namespace std; int AnsR[1001]; int AnsC[1001]; char AnsDir[1001]; int Trie[1000011][26]; int IsWord[1000011]; int Len[1001]; int verctr=1; int FailLink[1000011]; int SuccessLink[1000011]; int n,m; int k; char grid[1001][1001]; char word[1001]; int L; char curmarker; int ToX,ToY; int BaseX,BaseY; void AddWord(int id) { int cur=1; int i; for (i=1;i<=L;i++) { if (Trie[cur][ word[i]-'A' ]!=0) { cur=Trie[cur][ word[i]-'A' ]; } else { verctr++; Trie[cur][ word[i]-'A' ]=verctr; cur=verctr; } } IsWord[cur]=id; return; } int q[1000011]; int dad[1000011]; int branch[1000011]; int qL=0; void BuildLinks() { int i; int uk=1; int cver,cdad,cbranch; int vv; FailLink[1]=0; SuccessLink[1]=0; for (i=0;i<=25;i++) { if (Trie[1][i]!=0) { qL++; q[qL]=Trie[1][i]; dad[qL]=1; branch[qL]=i; } } while(uk<=qL) { cver=q[uk]; cdad=dad[uk]; cbranch=branch[uk]; vv=FailLink[cdad]; while(vv!=0) { if (Trie[vv][cbranch]!=0) { FailLink[cver]=Trie[vv][cbranch]; break; } vv=FailLink[vv]; } if (vv==0) { FailLink[cver]=1; } if (IsWord[ FailLink[cver] ]!=0) { SuccessLink[cver]=FailLink[cver]; } else { SuccessLink[cver]=SuccessLink[ FailLink[cver] ]; } for (i=0;i<=25;i++) { if (Trie[cver][i]!=0) { qL++; q[qL]=Trie[cver][i]; dad[qL]=cver; branch[qL]=i; } } uk++; } return; } void Scan() { int state=1; int i; int br; int suc; int strt; for (i=1;i<=L;i++) { br=word[i]-'A'; if (Trie[state][br]!=0) { state=Trie[state][br]; } else { state=FailLink[state]; while(state!=0) { if (Trie[state][br]!=0) { state=Trie[state][br]; break; } state=FailLink[state]; } if (state==0) { state=1; } } if (IsWord[state]!=0) suc=state; else suc=SuccessLink[suc]; while(suc>1) { strt=i-Len[ IsWord[suc] ]+1; AnsDir[ IsWord[suc] ]=curmarker; AnsR[ IsWord[suc] ]=BaseX+strt*ToX; AnsC[ IsWord[suc] ]=BaseY+strt*ToY; suc=SuccessLink[suc]; } } return; } int main() { freopen("crossword.in","r",stdin); freopen("crossword.out","w",stdout); int i,j; int curstate; int x,y; scanf("%d %d %d",&n,&m,&k); for (i=1;i<=n;i++) { scanf("%s",grid[i]+1); } for (i=1;i<=k;i++) { scanf("%s",word+1); L=strlen(word+1); Len[i]=L; AddWord(i); } BuildLinks(); ///C and G scan for (i=1;i<=n;i++) { for (j=1;j<=m;j++) { word[j]=grid[i][j]; } L=m; curmarker='C'; BaseX=i; BaseY=0; ToX=0; ToY=1; Scan(); reverse(word+1,word+1+L); curmarker='G'; BaseX=i; BaseY=m+1; ToX=0; ToY=-1; Scan(); } ///A and E for (i=1;i<=m;i++) { for (j=1;j<=n;j++) { word[j]=grid[j][i]; } L=n; curmarker='E'; BaseX=0; BaseY=i; ToX=1; ToY=0; Scan(); reverse(word+1,word+1+L); curmarker='A'; BaseX=n+1; BaseY=i; ToX=-1; ToY=0; Scan(); } ///D and H for (i=1;i<=n;i++) { x=i; y=1; L=0; while(x<=n && y<=m) { L++; word[L]=grid[x][y]; x++; y++; } curmarker='D'; BaseX=i-1; BaseY=0; ToX=1; ToY=1; Scan(); reverse(word+1,word+1+L); curmarker='H'; BaseX=x; BaseY=y; ToX=-1; ToY=-1; Scan(); } for (i=2;i<=n;i++) { x=1; y=i; L=0; while(x<=n && y<=m) { L++; word[L]=grid[x][y]; x++; y++; } curmarker='D'; BaseX=0; BaseY=i-1; ToX=1; ToY=1; Scan(); reverse(word+1,word+1+L); curmarker='H'; BaseX=x; BaseY=y; ToX=-1; ToY=-1; Scan(); } ///B and F for (i=1;i<=m;i++) { x=1; y=i; L=0; while(x<=n && y>=1) { L++; word[L]=grid[x][y]; x++; y--; } curmarker='F'; BaseX=0; BaseY=i+1; ToX=1; ToY=-1; Scan(); reverse(word+1,word+1+L); curmarker='B'; BaseX=x; BaseY=y; ToX=-1; ToY=1; Scan(); } for (i=2;i<=n;i++) { x=i; y=m; L=0; while(x<=n && y>=1) { L++; word[L]=grid[x][y]; x++; y--; } curmarker='F'; BaseX=i-1; BaseY=m+1; ToX=1; ToY=-1; Scan(); reverse(word+1,word+1+L); curmarker='B'; BaseX=x; BaseY=y; ToX=-1; ToY=1; Scan(); } for (i=1;i<=k;i++) { printf("%d %d %c\n",AnsR[i]-1,AnsC[i]-1,AnsDir[i]); } return 0; }