Сузір'я#1912
Нещодавно дослідники виявили стародавній манускрипт, який описує певне сузір'я. Згідно з манускриптом, сузір'я складається з зірок, і відомі відстані між кожною парою зірок, якщо розглядати небо як площину, а зірки як точки на цій площині.
На сьогоднішньому небі у тій півкулі, де ймовірно знаходиться це сузір'я, видно зірок. Зазвичай сузір'я складається з найяскравіших зірок ділянки неба, однак за тисячоліття яскравість зірок могла змінитися, тому цей критерій вже не є надійним. Відтак, щоб визначити, які зірки сьогоднішнього неба можуть утворити сузір'я, що описане у манускрипті, слід використовувати лише дані про відстані.
Можливим розташуванням сузір'я називається послідовність зірок (I_1, I_2, \ldots, I_M) така, що для кожного та (1 \leq i, j \leq M) відстань між зірками I_i і I_j дорівнює відстані між -ою та -ою зірками у манускрипті. Два можливих розташування вважаються різними, якщо хоча б одна зірка займає різні позиції.
Вам задано множину зірок на сьогоднішньому небі. Також задано матрицю розміром M \times M, де елемент — це квадрат відстані між -ю та -ю зірками сузір'я. Порахуйте кількість можливих розташувань даного сузір'я.
Перший рядок містить число . Далі йдуть рядків по цілих чисел — матриця відстаней. Потім подається число , а далі рядків з по двома цілими числами X_i, Y_i — координати -ї зірки на сучасному небі.
2 \leq N \leq 30000, 2 \leq M \leq \min(N, 20).
Координати кожної зірки — цілі числа з абсолютним значенням не більше . Жодні дві зірки не мають однакових координат.
Задана матриця відстаней симетрична, її головна діагональ містить лише нулі, а всі інші елементи — додатні числа, не більші за 10^{18}.
Виведіть кількість можливих розташувань сузір'я з манускрипту.
Приклад 1