use std::io; fn main() { let stdin = io::stdin(); let mut input = String::new(); stdin.read_line(&mut input).unwrap(); let dims: Vec<usize> = input.trim().split_whitespace().map(|x| x.parse().unwrap()).collect(); let (h, w) = (dims[0], dims[1]); let mut map = Vec::new(); for _ in 0..h { input.clear(); stdin.read_line(&mut input).unwrap(); map.push(input.trim().chars().collect::<Vec<char>>()); } input.clear(); stdin.read_line(&mut input).unwrap(); let q: usize = input.trim().parse().unwrap(); let mut queries = Vec::new(); for _ in 0..q { input.clear(); stdin.read_line(&mut input).unwrap(); let query: Vec<usize> = input.trim().split_whitespace().map(|x| x.parse().unwrap()).collect(); queries.push((query[0] - 1, query[1] - 1, query[2] - 1, query[3] - 1)); } let mut results = vec![0i64; q]; { let mut score = vec![0i64; h * w * w]; fn calc(h: usize, l: usize, w: usize, map: &Vec<Vec<char>>, score: &mut Vec<i64>) { let mut c = 0i64; let mut cw = 0i64; let mut now = 0i64; for i in l..w { if map[h][i] == 'c' { c += 1; } else { now += cw; cw += c; } score[h * w * w + l * w + i] += now; } } fn calc2(h: usize, r: usize, w: usize, map: &Vec<Vec<char>>, score: &mut Vec<i64>) { let mut c = 0i64; let mut cw = 0i64; let mut now = 0i64; for i in (0..=r).rev() { if map[h][i] == 'c' { c += 1; } else { now += cw; cw += c; } score[h * w * w + i * w + r] += now; } } for i in 0..h { for j in 0..w { calc(i, j, w, &map, &mut score); calc2(i, j, w, &map, &mut score); } } for (qi, &(a, b, c, d)) in queries.iter().enumerate() { for i in a..=c { results[qi] += score[i * w * w + b * w + d]; } } } { let mut score2 = vec![0i64; w * h * h]; fn calc3(w: usize, l: usize, h: usize, map: &Vec<Vec<char>>, score2: &mut Vec<i64>) { let mut c = 0i64; let mut cw = 0i64; let mut now = 0i64; for i in l..h { if map[i][w] == 'c' { c += 1; } else { now += cw; cw += c; } score2[w * h * h + l * h + i] += now; } } fn calc4(w: usize, r: usize, h: usize, map: &Vec<Vec<char>>, score2: &mut Vec<i64>) { let mut c = 0i64; let mut cw = 0i64; let mut now = 0i64; for i in (0..=r).rev() { if map[i][w] == 'c' { c += 1; } else { now += cw; cw += c; } score2[w * h * h + i * h + r] += now; } } for i in 0..w { for j in 0..h { calc3(i, j, h, &map, &mut score2); calc4(i, j, h, &map, &mut score2); } } for (qi, &(a, b, c, d)) in queries.iter().enumerate() { for i in b..=d { results[qi] += score2[i * h * h + a * h + c]; } } } for res in results { println!("{}", res); } }