Counting Boards Activating a Convolution Template

In the recent milestone in artificial intelligence, Google's AlphaGo defeated world champion Lee Sedol. Unlike traditional search‐based AIs, AlphaGo used a convolutional neural network. In such models, the board is scanned with a fixed‐size window. For example, on a 5×6 board using a 2×4 window there are \( (5-2+1)\times(6-4+1)=12 \) possible windows.

Templates (filters) of the same size as the window are predefined. A template is said to be activated on a board if there exists at least one window on the board which matches the template exactly. Otherwise, the template is not activated. In the figure below a 5×6 board is shown together with two 2×4 templates – the first template is activated, while the second is not.

For this problem we simplify the game: we only consider an \( n\times m \) board where each cell can be one of three types: a black stone, a white stone, or empty. Thus, there are \(3^{n\times m}\) possible boards. You are given \(q\) templates, each of size \(2\times c\) (note that every template has exactly 2 rows). For each template, determine the number of boards that activate it. A board activates a template if at least one contiguous submatrix (window) of size \(2\times c\) in the board is exactly equal to the template.

Note: Both the board and each template are represented using characters. For the board, each cell is one of:

• B representing a black stone,
• W representing a white stone,
• N representing an empty cell.

The templates use the same representation. It is guaranteed that \(c\) is less than or equal to \(m\).

Example: Suppose \(n=2, m=3\) (thus the board has 6 cells, and the total number of boards is \(3^6=729\)). Here there is only one possible window (consisting of the two rows). If a template of size \(2\times2\) is given, then there are 2 possible window positions in each board (columns 1–2 and 2–3). For instance, if the first query template is

Row1: BW
Row2: NB

then 18 boards will activate this template (details in the explanation below).

Input/Output Note: When \(n=1\) no window exists so no board can activate any template.

inputFormat

The first line contains three integers \(n\), \(m\) and \(q\) \( (2 \le n,\;1 \le m,\; 1 \le q \le 100)\) where \(n\) and \(m\) specify the board dimensions and \(q\) is the number of templates. It is guaranteed that \(n\ge2\) because the template has 2 rows.

Then follow \(2q\) lines. Each template is described by 2 consecutive lines. Each of these lines is a string of length \(c\) \((1\le c\le m)\) consisting only of the characters B, W and N, which represent black, white and empty respectively.

Input Example:

2 3 3
BW
NB
NN
NN
WB
BW

outputFormat

For each template, output a single line containing one integer – the number of boards that activate the template. (Since the total number of boards is \(3^{n\times m}\), the answer for a template is given by \(3^{n\times m}\) minus the number of boards which do not contain the template in any window.)

Output Example:

18
17
18

sample

2 3 3
BW
NB
NN
NN
WB
BW

18
17
18

</p>