Constellation
Researchers have recently uncovered an ancient manuscript that describes a specific constellation. According to the manuscript, this constellation is made up of M stars, with the distances between each pair of stars precisely known. The stars are considered as points on a plane, representing the sky.
In the current night sky, within the hemisphere where this constellation is likely to be found, there are N visible stars. Typically, constellations are identified by grouping the brightest stars in a section of the sky. However, over the centuries, the brightness of stars may have changed, making it unreliable to use brightness as a criterion. Thus, identifying which stars in today's sky could form the constellation described in the manuscript must rely solely on the distance information.
We define a possible location of the constellation as a sequence of stars (I_1, I_2, ..., I_M) such that for every pair of indices i and j (1 ≤ i, j ≤ M), the distance between stars I_i and I_j matches the distance between the i-th and j-th stars as recorded in the manuscript. Two possible locations are considered distinct if they differ by at least one star in any position.
You are provided with the current set of stars in the sky and a matrix of size MxM, where each element (i, j) represents the square of the distance between the i-th and j-th stars of the constellation. Your task is to determine how many possible locations of this constellation exist.
Input
The input begins with the number M. The following M lines each contain M integers, forming the distance matrix. Next, the number N is given, followed by N lines, each containing two integers X_i, Y_i, which are the coordinates of the i-th star in today's sky.
Constraints are as follows: 2 ≤ N ≤ 30000, 2 ≤ M ≤ min(N, 20).
Each star's coordinates are integers with an absolute value not exceeding 10000. No two stars share the same location.
The distance matrix is symmetric, with zeros on its main diagonal, and all other entries are positive integers not exceeding 10^18.
Output
Output the total number of possible locations for the constellation as described in the manuscript.