use std::io;
use std::collections::{HashMap, HashSet, VecDeque};
use rand::{random, random_bool, random_range};
use std::time::{SystemTime, UNIX_EPOCH};
type NodeID = (usize, usize);
fn main() {
let mut input = String::new();
io::stdin().read_line(&mut input).expect("Failed to read input");
let startdata: Vec<usize> = input.split_whitespace().map(|e| e.parse::<usize>().unwrap()).collect();
let mut grid: Vec<Vec<bool>> = vec!();
for row in 0..startdata[0] {
let mut rowinput = String::new();
io::stdin().read_line(&mut rowinput).expect("Failed to read input");
let newrow = rowinput.into_bytes().into_iter().map(|c| if c == 46 {true} else {false}).collect();
/*let mut newrow = vec!();
for c in 0..startdata[1] {
newrow.push(random_bool(0.3));
}*/
grid.push(newrow);
}
//dbg!(&grid);
let mut distancehash: HashMap<(NodeID, NodeID), usize> = HashMap::new();
for _q in 0..startdata[2] {
let mut questioninput = String::new();
io::stdin().read_line(&mut questioninput).expect("Failed to read input");
let start = SystemTime::now().duration_since(UNIX_EPOCH).unwrap().as_nanos();
let questiondata: Vec<usize> = questioninput.split_whitespace().map(|e| e.parse::<usize>().unwrap()-1).collect();
let source: NodeID = (questiondata[0], questiondata[1]);
let destination: NodeID = (questiondata[2], questiondata[3]);
/*let y1 = random_range(0..startdata[0]);
let y2 = random_range(0..startdata[0]);
let x1 = random_range(0..startdata[1]);
let x2 = random_range(0..startdata[1]);
let source = (y1, x1);
let destination = (y2, x2);*/
match distancehash.get(&(source, destination)) {
Some(d) => {
println!("{} ", d);
//let end = SystemTime::now().duration_since(UNIX_EPOCH).unwrap().as_nanos();
//println!("{}", end-start);
continue;
},
None => {}
}
if source == destination {
println!("0 ");
//let end = SystemTime::now().duration_since(UNIX_EPOCH).unwrap().as_nanos();
//println!("{}", end-start);
continue;
}
if source.0 == destination.0 || source.1 == destination.1 {
println!("1 ");
//let end = SystemTime::now().duration_since(UNIX_EPOCH).unwrap().as_nanos();
//println!("{}", end-start);
continue;
}
let mut sourceset: HashSet<NodeID> = HashSet::new();
let mut destset: HashSet<NodeID> = HashSet::new();
distancehash.insert((source, source), 0);
distancehash.insert((destination, destination), 0);
let mut sourcequeue: VecDeque<NodeID> = VecDeque::new();
sourcequeue.push_front(source);
let mut destqueue: VecDeque<NodeID> = VecDeque::new();
destqueue.push_front(destination);
'outer: while sourcequeue.len() != 0 && destqueue.len() != 0 {
let node = sourcequeue.pop_back().unwrap();
let dist = *distancehash.get(&(source, node)).unwrap();
let destnode = destqueue.pop_back().unwrap();
let destdist = *distancehash.get(&(destination, destnode)).unwrap();
sourceset.insert(node);
destset.insert(destnode);
if destset.contains(&node) {
let desttonode = distancehash[&(destination, node)];
distancehash.insert((source, destination), dist+desttonode);
distancehash.insert((destination, source), dist+desttonode);
break 'outer;
}
if sourceset.contains(&destnode) {
let sourcetonode = distancehash[&(source, node)];
distancehash.insert((source, destination), destdist+sourcetonode);
distancehash.insert((destination, source), destdist+sourcetonode);
break 'outer;
}
for row in 0..grid.len() {
if row == node.0 {
for cell in 0..node.1 {
if grid[row][cell] {
let neighbor = (row, cell);
let d = match distancehash.get(&(source, neighbor)) {
Some(distance) => *distance,
None => 1000000
};
if d > dist {
distancehash.insert((source, neighbor), dist+1);
distancehash.insert((neighbor, source), dist+1);
sourcequeue.push_front(neighbor);
}
if neighbor == destination {
break 'outer;
}
}
}
for cell in (node.1+1)..grid[row].len() {
if grid[row][cell] {
let neighbor = (row, cell);
let d = match distancehash.get(&(source, neighbor)) {
Some(distance) => *distance,
None => 1000000
};
if d > dist {
distancehash.insert((source, neighbor), dist+1);
distancehash.insert((neighbor, source), dist+1);
sourcequeue.push_front(neighbor);
}
if neighbor == destination {
break 'outer;
}
}
}
} else {
if grid[row][node.1] {
let neighbor = (row, node.1);
let d = match distancehash.get(&(source, neighbor)) {
Some(distance) => *distance,
None => 1000000
};
if d > dist {
distancehash.insert((source, neighbor), dist+1);
distancehash.insert((neighbor, source), dist+1);
sourcequeue.push_front(neighbor);
}
if neighbor == destination {
break 'outer;
}
}
}
}
for row in 0..grid.len() {
if row == destnode.0 {
for cell in 0..destnode.1 {
if grid[row][cell] {
let neighbor = (row, cell);
let d = match distancehash.get(&(destination, neighbor)) {
Some(distance) => *distance,
None => 1000000
};
if d > destdist {
distancehash.insert((destination, neighbor), destdist+1);
distancehash.insert((neighbor, destination), destdist+1);
destqueue.push_front(neighbor);
}
if neighbor == source {
break 'outer;
}
}
}
for cell in (destnode.1+1)..grid[row].len() {
if grid[row][cell] {
let neighbor = (row, cell);
let d = match distancehash.get(&(destination, neighbor)) {
Some(distance) => *distance,
None => 1000000
};
if d > destdist {
distancehash.insert((destination, neighbor), destdist+1);
distancehash.insert((neighbor, destination), destdist+1);
destqueue.push_front(neighbor);
}
if neighbor == source {
break 'outer;
}
}
}
} else {
if grid[row][destnode.1] {
let neighbor = (row, destnode.1);
let d = match distancehash.get(&(destination, neighbor)) {
Some(distance) => *distance,
None => 1000000
};
if d > destdist {
distancehash.insert((destination, neighbor), destdist+1);
distancehash.insert((neighbor, destination), destdist+1);
destqueue.push_front(neighbor);
}
if neighbor == source {
break 'outer;
}
}
}
}
}
match distancehash.get(&(source, destination)) {
Some(s) => {println!("{} ", s);},
None => {println!("-1 ");}
}
//let end = SystemTime::now().duration_since(UNIX_EPOCH).unwrap().as_nanos();
//println!("{}", end-start);
}
}