def main(): import sys input = sys.stdin.read().split() idx = 0 H = int(input[idx]); idx +=1 W = int(input[idx]); idx +=1 grid = [] for _ in range(H): s = input[idx].strip() idx +=1 grid.append(s) # Preprocess row_prefix and col_prefix # For right and left row_prefix = [] for i in range(H): pre = [0]*(W+1) for j in range(1, W+1): pre[j] = pre[j-1] + (1 if grid[i][j-1] == 'w' else 0) row_prefix.append(pre) # For right direction: cnt_c_r, sum_rf_r, sum_rf_sq_r cnt_c_r = [] sum_rf_r = [] sum_rf_sq_r = [] for i in range(H): cnt = [0]*(W+1) sum_rf = [0]*(W+1) sum_sq = [0]*(W+1) for j in range(1, W+1): cnt[j] = cnt[j-1] sum_rf[j] = sum_rf[j-1] sum_sq[j] = sum_sq[j-1] if grid[i][j-1] == 'c': cnt[j] +=1 sum_rf[j] += row_prefix[i][j] sum_sq[j] += (row_prefix[i][j])**2 cnt_c_r.append(cnt) sum_rf_r.append(sum_rf) sum_rf_sq_r.append(sum_sq) # For left direction: sum_row_prev # sum_rp_l[i][j] is sum of row_prefix[i][k-1] for k in 1..j where s[i][k-1] is 'c' sum_rp_l = [] sum_rp_sq_l = [] cnt_c_l = [] for i in range(H): cnt = [0]*(W+1) sum_rp = [0]*(W+1) sum_sq = [0]*(W+1) for j in range(1, W+1): cnt[j] = cnt[j-1] sum_rp[j] = sum_rp[j-1] sum_sq[j] = sum_sq[j-1] if grid[i][j-1] == 'c': cnt[j] +=1 rp = row_prefix[i][j-1] sum_rp[j] += rp sum_sq[j] += rp * rp cnt_c_l.append(cnt) sum_rp_l.append(sum_rp) sum_rp_sq_l.append(sum_sq) # Preprocess col_prefix for up and down col_prefix = [] for j in range(W): pre = [0]*(H+1) for i in range(1, H+1): pre[i] = pre[i-1] + (1 if grid[i-1][j] == 'w' else 0) col_prefix.append(pre) # For down direction: cnt_ccol_d, sum_cf_d, sum_cf_sq_d cnt_ccol_d = [] sum_cf_d = [] sum_cf_sq_d = [] for j in range(W): cnt = [0]*(H+1) sum_cf = [0]*(H+1) sum_sq = [0]*(H+1) for i in range(1, H+1): cnt[i] = cnt[i-1] sum_cf[i] = sum_cf[i-1] sum_sq[i] = sum_sq[i-1] if grid[i-1][j] == 'c': cnt[i] +=1 sum_cf[i] += col_prefix[j][i] sum_sq[i] += (col_prefix[j][i])**2 cnt_ccol_d.append(cnt) sum_cf_d.append(sum_cf) sum_cf_sq_d.append(sum_sq) # For up direction cnt_ccol_u = [] sum_cp_u = [] sum_cp_sq_u = [] for j in range(W): cnt = [0]*(H+1) sum_cp = [0]*(H+1) sum_sq = [0]*(H+1) for i in range(1, H+1): cnt[i] = cnt[i-1] sum_cp[i] = sum_cp[i-1] sum_sq[i] = sum_sq[i-1] if grid[i-1][j] == 'c': cnt[i] +=1 cp = col_prefix[j][i-1] sum_cp[i] += cp sum_sq[i] += cp * cp cnt_ccol_u.append(cnt) sum_cp_u.append(sum_cp) sum_cp_sq_u.append(sum_sq) Q = int(input[idx]); idx +=1 for _ in range(Q): a = int(input[idx])-1; idx +=1 b = int(input[idx])-1; idx +=1 c = int(input[idx])-1; idx +=1 d = int(input[idx])-1; idx +=1 a_row = a c_row = c b_col = b d_col = d res = 0 # Right direction for i in range(a_row, c_row+1): # j: b_col <= j <= d_col j_min = b_col +1 # 0-based j in grid is j+1 in 1-based j_max = d_col +1 # converted to 1-based for the row_prefix j_min_1based = b_col +1 j_max_1based = d_col +1 current_row = row_prefix[i] current_row_d = current_row[d_col+1] # get count of 'c' in row[i], columns [b_col..d_col] (0-based) # to 1-based: [b_col+1, d_col+1] cnt = cnt_c_r[i][j_max_1based] - cnt_c_r[i][j_min_1based -1] if cnt ==0: continue sum_rf = sum_rf_r[i][j_max_1based] - sum_rf_r[i][j_min_1based -1] sum_rf_sq = sum_rf_sq_r[i][j_max_1based] - sum_rf_sq_r[i][j_min_1based -1] sum_k = current_row_d * cnt - sum_rf sum_k_squared = (current_row_d * current_row_d) * cnt - 2 * current_row_d * sum_rf + sum_rf_sq contribution = (sum_k_squared - sum_k) //2 res += contribution # Left direction for i in range(a_row, c_row+1): j_min = b_col j_max = d_col # j: from j_min+1 (0-based) to j_max+1 (1-based) j_min_1based = (b_col) +1 j_max_1based = (d_col) +1 current_row = row_prefix[i] # Left k is row[i][b..j-1] where j is in [b..d] prev_val = row_prefix[i][b_col] if b_col >=0 else 0 # for j in [b_col..d_col], s[i][j] == 'c' # sum_row_prev for j's columns (0-based) cnt = cnt_c_l[i][j_max_1based] - cnt_c_l[i][j_min_1based -1] if cnt ==0: continue sum_rp = sum_rp_l[i][j_max_1based] - sum_rp_l[i][j_min_1based -1] sum_rp_sq = sum_rp_sq_l[i][j_max_1based] - sum_rp_sq_l[i][j_min_1based -1] sum_k = sum_rp - prev_val * cnt sum_k_squared = sum_rp_sq - 2 * prev_val * sum_rp + (prev_val **2) * cnt contribution = (sum_k_squared - sum_k) //2 res += contribution # Down direction for j in range(b_col, d_col +1): # i from a_row to c_row, where s[i][j] == 'c' # compute for each i in a_row <= i <= c_row # down k: i+1 to c_row in the same column j i_min = a_row i_max = c_row if i_min <0 or i_max >=H: continue current_col = col_prefix[j] current_col_c = current_col[c_row +1] cnt = cnt_ccol_d[j][i_max +1] - cnt_ccol_d[j][i_min] if cnt ==0: continue sum_cf = sum_cf_d[j][i_max +1] - sum_cf_d[j][i_min] sum_cf_sq = sum_cf_sq_d[j][i_max +1] - sum_cf_sq_d[j][i_min] sum_k = current_col_c * cnt - sum_cf sum_k_squared = (current_col_c **2)*cnt - 2*current_col_c*sum_cf + sum_cf_sq contribution = (sum_k_squared - sum_k) //2 res += contribution # Up direction for j in range(b_col, d_col +1): # i in a_row <= i <=c_row, and s[i][j] == 'c' # up k: from a to i-1 in column j a_prev = a_row current_col = col_prefix[j] if a_prev -1 <0: current_col_a_prev = 0 else: current_col_a_prev = current_col[a_prev] cnt = cnt_ccol_u[j][c_row +1] - cnt_ccol_u[j][a_prev] if cnt ==0: continue sum_cp = sum_cp_u[j][c_row +1] - sum_cp_u[j][a_prev] sum_cp_sq = sum_cp_sq_u[j][c_row +1] - sum_cp_sq_u[j][a_prev] sum_k = sum_cp - current_col_a_prev * cnt sum_k_squared = sum_cp_sq - 2 * current_col_a_prev * sum_cp + (current_col_a_prev **2) * cnt contribution = (sum_k_squared - sum_k) //2 res += contribution print(res) if __name__ == '__main__': main()