욕심 많은 신년 운세

평화는 최근에 인터넷 커뮤니티에서 신년 운세라는 포스팅을 보았다. $N \times M$ 격자 형태로 영어 알파벳 소문자가 있고, 거기서 가장 먼저 찾은 단어가 올해에 얻게 되는 것이라는 내용이었다.

평화는 욕심이 많아서, 자신이 좋아하는 행운의 단어들을 격자판에서 최대한 많이 만들어보기로 했다.

격자판에서 단어를 만들 때에는 항상 왼쪽에서 오른쪽으로 또는 위에서 아래로 연속한 알파벳을 골라야 한다. 편의상 왼쪽에서 오른쪽으로 가는 방향을 가로 방향으로, 위에서 아래로 가는 방향을 세로 방향이라고 하자.

같은 단어를 여러 번 만드는 것은 허용되지만, 같은 방향으로 만든 두 단어가 공통의 격자 칸을 사용하면 안 된다. 가로 방향과 세로 방향의 두 단어가 공통의 격자 칸을 사용하는 것은 허용됨에 유의하라.

예를 들어서, 아래와 같이 격자가 주어지고 평화가 좋아하는 행운의 단어가 subset, set, box일 때, subset과 set를 둘 다 만들 수는 없지만, subset과 box는 함께 만들 수 있다.

평화는 단어가 길수록 더 행운이 깃들어 있다고 생각한다. 만든 단어들의 길이의 합을 행운 점수라고 할 때, 평화가 가능한 한 큰 행운 점수를 얻을 수 있도록 격자에서 단어를 만드는 프로그램을 작성하시오.

입력 형식

첫 줄에 격자판의 크기를 나타내는 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. ($4 \le N, M \le 50$)

이어지는 $N$ 개의 줄의 $i$ 번째 줄에는 격자판의 $i$ 번째 행을 구성하는 길이 $M$인 문자열이 주어진다.

그다음 줄에 평화가 좋아하는 행운의 단어의 개수 $K$가 주어진다. ($1 \le K \le 10$)

이어지는 $K$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 행운의 단어 $S_i$가 주어진다. $S_i$의 길이는 $2$ 이상이며, $\min(N, M)$을 넘지 않는다.

입력으로 주어지는 문자열은 모두 영어 알파벳 소문자로만 이루어져 있다.

출력 형식

첫 줄에 격자판에서 만든 단어의 수 $T$를 출력한다.

이어지는 $T$ 개의 줄에 하나씩 단어를 만드는 방법을 출력한다. 단어를 만드는 방법은 단어의 시작 알파벳이 위치한 격자의 행 번호와 열 번호, 단어의 마지막 알파벳이 위치한 격자의 행 번호와 열 번호를 공백으로 구분하여 출력한다.

가장 위 행과 가장 왼쪽 열의 번호는 $1$이다.

예제

6 6
zzszzz
zzuzzz
zzboxz
zzszzz
zzezzz
zztzzz
3
subset
set
box

2
1 3 6 3
3 3 3 5

채점 방식

이 문제는 풀이 소스 코드를 제출하지 않고, 각 테스트 케이스의 입력 데이터를 다운받아 알맞은 출력 파일을 만들어 출력 파일만을 제출하는 문제다.

문제 해결을 도와주는 시뮬레이터가 아래 미션에 대해 제공된다. 제공되는 시뮬레이터는 최신 버전의 크롬 브라우저에서 여는 것을 권장한다.

이 문제의 총점은 모든 미션의 점수의 합으로 계산된다. 각 미션의 점수를 계산하는 방법은 다음과 같다.

• $S$: 미션의 만점
• $P$: 미션에 대한 참가자의 점수
• $\alpha, \beta$: 미션마다 정해진 상수
• $\alpha$: 미션에서 만점을 받을 수 있는 최소 행운 점수
• $L$: 참가자의 출력에 따른 행운 점수 단, 참가자의 출력이 올바르지 않은 경우 (출력 형식을 맞추지 않았거나, 리스트에 없는 단어를 선택하는 등) $P = 0$이다.

1. $L \le \beta$인 경우: $P = 0$
2. $\beta < L < \alpha$인 경우: $\displaystyle P = S \times \frac{L-\beta}{\alpha - \beta}$
3. $\alpha \le L$인 경우: $P = S$

이후, $P$는 최종적으로 $0.1$ 단위로 버림된다.

미션마다 만점을 받을 수 있는 출력이 존재함이 보장된다.

해설