Constellation#1912
Researchers recently discovered an ancient manuscript describing a certain constellation. According to the manuscript, the constellation consists of stars, and the distances between every pair of stars are known if we consider the sky as a plane and the stars as points on that plane.
In the current sky, within the hemisphere where this constellation is presumably located, there are visible stars. Usually, a constellation is considered as a combination of the brightest stars in a section of the sky, but over the millennia the brightness of stars could have changed, so this criterion is no longer reliable. Thus, to determine which of today's stars could form the constellation described in the manuscript, we must use only the distance data.
A possible location of the constellation is a sequence of stars (I_1, I_2, \ldots, I_M) such that for every and (1 \leq i, j \leq M), the distance between stars I_i and I_j equals the distance between the th and th stars in the manuscript. Two possible locations are considered different if at least one star is different at the same position.
You are given a set of stars in the current sky. You are also given an M \times M matrix, where element is the square of the distance between the th and th stars of the constellation. Count the number of possible locations for the constellation.
The first line contains an integer . The next lines each contain integers — the distance matrix. Then the integer is given, followed by lines, each containing two integers X_i, Y_i — the coordinates of the th star in today’s sky.
2 \leq N \leq 30000, 2 \leq M \leq \min(N, 20).
Coordinates of each star are integers with absolute value at most . No two stars occupy the same position.
The given distance matrix is symmetric, its main diagonal contains zeros only, and all other entries are positive integers not exceeding 10^{18}.
Output the number of possible locations of the constellation from the manuscript.
Example 1