왕의 산책

체스의 왕이 봄의 들판을 산책하려고 한다. 봄의 들판은 직사각형이고, 각 칸에는 알파벳 소문자가 하나씩 적혀 있다.

왕은 들판의 아무 칸에서나 산책을 시작해서 $n-1$번 이동한다. 이동은 체스의 왕 규칙을 따른다. 즉, 지금 있는 칸과 변이나 꼭짓점을 맞대고 있는 칸으로 옮겨 간다. 제자리에 머무는 것은 이동으로 인정하지 않는다. 산책 도중에 같은 칸을 여러 번 지나가도 된다.

이렇게 왕은 칸 $n$개를 방문한다. 방문한 순서대로 칸에 적힌 글자를 이으면 길이 $n$인 문자열 $s$가 된다.

저녁이 되면 왕은 이 문자열을 왕조의 좌우명과 비교한다. 좌우명도 정확히 $n$글자다. $i$번째 자리에서 좌우명의 글자와 $s$의 글자가 같으면 왕은 $i$번째 병사를 승진시킨다.

승진하는 병사가 가장 많아지는 경로를 찾아라.

첫 줄에 들판의 크기를 나타내는 정수 $h$와 $w$가 주어진다 ($2 \le h, w \le 20$).

다음 $h$개 줄에는 각각 알파벳 소문자 $w$개가 주어진다. 들판의 모습이다.

그다음 줄에 정수 $n$이 주어진다 ($1 \le n \le 50$).

마지막 줄에 왕조의 좌우명이 주어진다. 알파벳 소문자 $n$개로 이루어진 문자열이다.

첫 줄에 승진시킬 수 있는 병사 수의 최댓값 $m$을 출력한다.

이어지는 $n$개 줄에 왕이 방문하는 칸의 좌표를 방문 순서대로 출력한다. 좌표는 행 번호와 열 번호를 공백으로 구분해서 적는다. 행은 위에서 아래로 1부터, 열은 왼쪽에서 오른쪽으로 1부터 센다.

승진 인원이 최대인 경로가 여럿이면 사전순으로 가장 작은 경로 하나만 출력한다. 경로는 방문 순서대로 좌표를 늘어놓은 수열 $r_1, c_1, r_2, c_2, \dots, r_n, c_n$으로 보고 비교한다.