Counting Valid Simple Cycles Through a Specific Grid Edge

We are given an n by m grid. Each cell is denoted by \((x,y)\) where x is the row number and y is the column number (1-indexed). Some cells contain obstacles. A cell is free if it does not contain an obstacle.

A simple cycle on this grid is a closed path visiting a sequence of free cells such that:

1. The cycle does not go through any obstacle cell.
2. The cycle is simple (i.e. it does not intersect itself and no cell appears more than once, except that the starting cell appears exactly twice: at the beginning and end).

An edge exists between two cells if they are adjacent horizontally or vertically. A cycle is considered valid if it is a simple cycle.

You are given Q queries. In each query, you are asked to count the number of valid simple cycles that pass through the edge connecting \((x,y)\) and \((x+1,y)\). Note that the coordinates in the queries are 1-indexed. All formulas are in \(\LaTeX\) format.

Note: You may assume that the grid dimensions are small enough (e.g. \(n,m \le 5\)) so that an exhaustive search is feasible.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of rows and columns of the grid.

The following \(n\) lines each contain a string of length \(m\). Each character is either . (denoting a free cell) or # (denoting an obstacle).

The next line contains an integer \(Q\) representing the number of queries.

Each of the next \(Q\) lines contains two integers \(x\) and \(y\). The query asks for the number of valid simple cycles that pass through the edge connecting \((x,y)\) and \((x+1,y)\). It is guaranteed that \(1 \le x < n\) and \(1 \le y \le m\).

outputFormat

For each query, output a single integer on a separate line – the number of valid simple cycles that pass through the specified edge.

sample

2 2
..
..
1
1 1

1