시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 17 5 2 50.000%

문제

영선이는 야매 점술사이다. 영선이는 아주 간단한 방법으로 점을 봐서, 운의 양을 결정한다. n x m 격자판에 각 칸마다 알파벳이 쓰여 있다. 그리고 점을 보러온 사람이 k길이의 단어를 임의로 작성한다. 그러면 영선이는 그 단어의 연속된 일부분이 최대한 일치하게 격자판의 문자와 겹치게 만들고, 그 길이를 통하여 운의 양을 결정한다. 겹치게 만들 때는 가로나 세로에 평행하게 두며, 문자의 순서는 위,아래,왼쪽,오른쪽 4방향 중 어느 방향이여도 상관없다. 또한, 일치하지 않은 문자는 격자판을 벗어나도 상관없다.

예를 들어 아래와 같은 상황에서 AHMRVP 라는 단어를 찾는다면, (2,3) 부터 (4,3)까지 연속된 일부분인 HMR을 겹치게 둘 수 있다.

그리고 JEHGFP의 경우도 (2,3)부터 (2,1)까지 연속된 일부분인 HGF를 찾을 수 있다. ,


영선이는 야매 점술사인데 반해, 우연을 통하여 점괘를 잘 맞추기 때문에 의외로 인기가 많다. 오늘도 p명의 사람의 점괘를 봐줘야 한다. 하지만 영선이는 점괘로 번 돈으로 놀고 있기 때문에, 영선이를 대신하여 각 단어별로 격자판에서 단어를 찾아주자.

입력

첫쨰줄에는 점괘를 보는 격자판의 크기 n,m이 주어진다.(1≤n,m≤100)

다음 n줄에는 격자판의 문자 m개가 주어진다.

다음줄에는 점괘를 보러 온 사람의 수 p, 단어의 길이 k가 주어진다. (1≤p≤100,000 , 1≤k≤30)

다음 p줄에는 점괘를 보러 온 사람이 적은 단어의 문자 k개가 주어진다.

점괘에 사용되는 모든 문자는 알파벳 대문자를 사용한다.

출력

각 단어별로 가장 긴 연속된 일부분 문자의 길이를 출력하시오.

예제 입력 1

5 5
ABCDE
FGHIJ
KLMNO
PQRST
UVWXY
3 6
AHMRVP
JEHGFP
ZZZZZZ

예제 출력 1

3
3
0