Identical Shape Pairs in Grid Components

You are given an n × m grid where each cell contains an integer. Initially every cell is black. At time t seconds, every cell whose number is \(\le t\) becomes white. You are then given multiple queries. For each query, you are given a value of t and must determine the number of unordered pairs of black 4-connected components that have exactly the same shape (when compared via translation only, i.e. without any rotation or reflection).

A 4-connected component is a maximal set of black cells such that each cell is connected to at least one other cell in the set through one of its four neighbors (up, down, left, right). The shape of a component is defined by the relative positions of its cells when normalized (translated so that the smallest row and column indices are 0). Two components are considered identical if their normalized sets of coordinates match exactly.

Your task is to output, for each query, the total number of pairs of connected components that have identical shapes.

Note: Each pair is counted only once. For example, if a particular shape occurs in 3 components, this contributes \( \binom{3}{2} = 3\) pairs.

inputFormat

The first line contains two integers n and m — the number of rows and columns of the grid.

Each of the next n lines contains m integers, representing the grid values.

The next line contains a single integer q, the number of queries. Each of the following q lines contains an integer t representing the time (in seconds).

outputFormat

For each query, output a single integer on a new line — the number of unordered pairs of black 4-connected components whose normalized shapes are exactly identical.

sample

3 3
1 2 3
4 5 6
7 8 9
2
4
7

0
0