#include <iostream>#include <cstring>#include <cstdio>#include <cmath>using namespace std;#define LL long longconst double eps = 1e-9;const double INF = 1e10;const int maxn = 310;int sum[maxn][maxn];LL squ[maxn][maxn];int mx[10][10][maxn][maxn];int m, n, a, b, x, y;double ans;void rmqinit(){ for(int r = 0; (1 << r) < m; r++){ for(int c = 0; (1 << c) < n; c++){ if(r == 0 && c == 0) continue; for(int i = m; i >= 1; i--){ for(int j = n; j >= 1; j--){ if(r == 0){ mx[r][c][i][j] = mx[r][c - 1][i][j]; if(j + (1 << (c - 1)) <= n) mx[r][c][i][j] = max(mx[r][c][i][j], mx[r][c - 1][i][j + (1 << (c - 1))]); }else { mx[r][c][i][j] = mx[r - 1][c][i][j]; if(i + (1 << (r - 1)) <= m) mx[r][c][i][j] = max(mx[r][c][i][j], mx[r - 1][c][i + (1 << (r - 1))][j]); } } } } }}int rmq(int r1, int c1, int r2, int c2){ int m1 = max((int)floor(log((double)(r2 - r1 + 1)) / log(2.0) - eps), 0); int m2 = max((int)floor(log((double)(c2 - c1 + 1)) / log(2.0) - eps), 0); return max(max(mx[m1][m2][r1][c1], mx[m1][m2][r1][c2 - (1 << m2) + 1]), max(mx[m1][m2][r2 - (1 << m1) + 1][c1], mx[m1][m2][r2 - (1 << m1) + 1][c2 - (1 << m2) + 1]));}inline void slove(int u, int i, int j){ int _sum = sum[i][j] - u; LL _squ = squ[i][j] - u * u; if(i + a <= m){ _sum -= sum[i + a][j]; _squ -= squ[i + a][j]; } if(j + b <= n){ _sum -= sum[i][j + b]; _squ -= squ[i][j + b]; } if(i + a <= m && j + b <= n){ _sum += sum[i + a][j + b]; _squ += squ[i + a][j + b]; } int c = a * b - 1; double avg = (double)_sum / c; double v = (double)_squ / c + avg * avg - 2.0 * avg * _sum / c; if(ans > v){ ans = v; x = i; y = j; }}int main(){ int q, con = 1; while(scanf("%d %d", &m, &n) == 2){ printf("Case %d:n", con++); for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) scanf("%d", &mx[0][0][i][j]); for(int j = m; j >= 1; j--){ int _sum = 0; LL _squ = 0; for(int i = n; i >= 1; i--){ if(j < m) { sum[j][i] = sum[j + 1][i]; squ[j][i] = squ[j + 1][i]; }else { sum[j][i] = 0; squ[j][i] = 0; } _sum += mx[0][0][j][i]; _squ += mx[0][0][j][i] * mx[0][0][j][i]; sum[j][i] += _sum; squ[j][i] += _squ; } } rmqinit(); scanf("%d", &q); while(q--){ scanf("%d %d", &a, &b); ans = INF; for(int i = 1; i + a - 1 <= m; i++){ for(int j = 1; j + b - 1 <= n; j++){ int u = rmq(i, j, i + a - 1, j + b - 1); slove(u, i, j); } } printf("(%d, %d), %.2lfn", x, y, ans); } } return 0;}
