cho.sh

가장 좋은 자리

아직 제출이 없습니다시간 제한10초메모리 제한256 MB

문제

한 농부가 넓은 밭에 새 농장을 지으려고 한다. 밭은 RR행 CC열 격자이고, 각 칸에서는 곡물(G)과 가축(L) 중 한 가지 먹거리를 생산한다. 다음은 R=5R = 5, C=8C = 8인 밭이다.

  12345678
1 GLGGLGLG
2 GGLGGLGL
3 GGLLLGGG
4 LLGLLGLG
5 LGGGLGLL

농부에게는 설계도도 있다. 설계도는 HH행 WW열 격자이며 H≤RH \le R, W≤CW \le C이다. 설계도의 각 칸에는 농부가 그 자리에서 얻고 싶은 먹거리인 곡물(G) 또는 가축(L)이 적혀 있다. 다음은 H=2H = 2, W=3W = 3인 설계도이다.

  123
1 GLL
2 LGG

농부는 설계도를 밭 위에 얹어 농장을 짓는다. 놓는 자리는 왼쪽 위 모서리의 좌표 (r,c)(r, c)로 나타내고, 이때 설계도는 밭의 rr행부터 r+H−1r + H - 1행까지, cc열부터 c+W−1c + W - 1열까지를 덮는다. 설계도 전체가 밭 안에 들어가야 하므로 r+H−1≤Rr + H - 1 \le R이고 c+W−1≤Cc + W - 1 \le C이다. 0≤i<H0 \le i < H, 0≤j<W0 \le j < W에 대해 밭의 (r+i,c+j)(r + i, c + j) 칸에 있는 먹거리가 설계도의 (i+1,j+1)(i + 1, j + 1) 칸에 적힌 먹거리와 같으면 그 칸에서 먹거리를 생산한다.

농부는 곡물과 가축을 합한 생산량이 가장 많은 자리를 고르려고 한다. 생산량이 같은 자리가 여럿이면 rr이 가장 작은 자리를 고르고, 그래도 여럿이면 cc가 가장 작은 자리를 고른다.

위의 밭과 설계도에서 가장 좋은 자리는 (1,3)(1, 3)이다. 설계도는 1행부터 2행까지, 3열부터 5열까지를 덮고, 그 자리의 밭은 위가 GGL, 아래가 LGG이다. 설계도의 첫 줄 GLL은 첫째 칸과 셋째 칸이 밭과 같아 곡물 1개와 가축 1개를 생산한다. 둘째 줄 LGG는 세 칸이 모두 같아 곡물 2개와 가축 1개를 생산한다. 그래서 이 자리는 곡물 3개와 가축 2개, 모두 5개를 생산한다. (2,5)(2, 5)와 (3,2)(3, 2)에 지어도 5개를 생산하지만 (1,3)(1, 3)이 행 번호가 더 작고, 나머지 자리는 모두 5개보다 적게 생산한다.

입력

입력에는 밭이 하나 주어진다. 첫째 줄에 두 정수 RR과 CC가 주어진다. (1≤R,C≤5001 \le R, C \le 500) 다음 RR개 줄에는 각각 CC개의 문자가 주어지며, 밭의 한 행을 나타낸다.

그다음 줄에는 농부가 가진 설계도의 개수 BB가 주어진다. (1≤B≤51 \le B \le 5) 이어서 설계도 BB개가 주어진다. 각 설계도는 두 정수 HH와 WW가 적힌 줄로 시작하고 (1≤H≤R1 \le H \le R, 1≤W≤C1 \le W \le C), 그 뒤에 각각 WW개의 문자로 이루어진 HH개 줄이 온다.

밭과 설계도의 모든 문자는 G 또는 L이다.

출력

설계도마다 입력에 주어진 순서대로 한 줄씩 출력한다. XX번째 설계도에 대해서는 (XX는 1부터 센다) Case #X: 를 출력한 다음, 공백 하나로 구분한 네 정수를 출력한다. 앞의 두 정수는 농장을 짓기 가장 좋은 자리의 행 번호와 열 번호이고, 뒤의 두 정수는 그 자리에서 생산하는 곡물의 개수와 가축의 개수다.