Сузір`я
Нещодавно дослідники виявили стародавнвй манускрипт, який описує деяке сузір'я. З нього випливає, що сузір'я складаєься з 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.
Вихідні дані
Виведіть кількість можливих місцезнаходжень сузір'я із манускрипту.