Недавно исследователи обнаружили древний манускрипт, который описывает некоторое созвездие. Из него следует, что созвездие состоит из M звёзд, а также известны расстояния между каждой парой звёзд созвездия, если рассматривать небо как плоскость, а звёзды — как точки на этой плоскости.
На сегодняшнем небе в том полушарии, где предположительно находится описанное созвездие, видно N звёзд. Обычно созвездием считают объединение самых ярких звёзд какого-либо фрагмента неба, но за прошедшие тысячелетия яркости звёзд могли измениться, поэтому опираться на этот показатель уже невозможно. Следовательно, определять, какие звёзды сегодняшнего неба могут образовывать описанное в манускрипте созвездие, приходится лишь на основе данных расстояний.
Будем называть возможным местоположением созвездия список звёзд (I_1, I_2, ..., I_M) такой, что для каждого i и j (1 ≤ i, j ≤ M) расстояние между звёздами I_i и I_j равно расстоянию между i-ой и j-ой звёздами манускрипта. Два возможных местоположения различны, если хотя бы на одной из позиций в них записаны разные звёзды.
Вам задано множество звёзд на сегодняшнем небе. Также дана матрица размерности MxM, где элемент (i, j) обозначает квадрат расстояния между звёздами i и j созвездия. Подсчитайте количество возможных местоположений этого созвездия.
Первая строка входного файла содержит число M. Следующие M строк содержат по M целых чисел каждая — матрицу расстояний. Далее записано число N, а затем следует N строк, каждая из которых содержит пару целых чисел X_i, Y_i — координаты i-ой звезды на сегодняшнем небе.
2 ≤ N ≤ 30000, 2 ≤ M ≤ min(N, 20).
Координаты каждой звезды — целые числа, не превосходящие 10000 по абсолютному значению. Никакие две звезды не находятся в одной точке.
Заданная матрица расстояний симметрична, её главная диагональ содержит только нули, а все остальные числа положительные и не превосходят 10^18.
Выведите количество возможных местоположений созвездия из манускрипта.