Нещодавно дослідники виявили стародавнвй манускрипт, який описує деяке сузір'я. З нього випливає, що сузір'я складаєься з \textbf{M} зірок, а також відомі відстані між кожною парою зірок сузір'я, якщо розглядати небо як площину, а зірки --- як точки на цій площині. На сьогоднішньому небі у тій півкулі, де ймовірно знаходится описане сузір'я, видно \textbf{N} зірок. Звичайним сузір'ям вважають об'єднання самих яскравих зірок якого-небудь фрагменту неба, але за тисячоліття, що пройшли, яскравості зірок могли змінитись, тому спиратись на цей показник вже неможливо. Відповідно, визначати, які зірки сьогоднішнього неба можуть утворювати описане у манускрипті сузір'я, приходиться лише на основі даних про відстані. Будем називати \textit{можливим місуезнаходженням сузір'я} список зірок (\textbf{I_1}, \textbf{I_2}, ..., \textbf{I_M}) такий, що для кожного \textbf{i} та \textbf{j} (\textbf{1} ≤ \textbf{i}, \textbf{j} ≤ \textbf{M}) відстань між зірками \textbf{I_i} та \textbf{I_j} дорівнює відстані міжу \textbf{i}-ою та \textbf{j}-ою зірками манускрипта. Два можливих містцезнаходження різні, якщо хоча б на одній із позицій у них записані різні зірки. Вам задано множину зірок на сьогоднішньому небі. Також задано матрицю розмірності \textbf{M}x\textbf{M}, де елемент (\textbf{i}, \textbf{j}) позначає квадрат відстані між зірками \textbf{i} та \textbf{j} сузір'я. Підрахуйте кількість можливи місцезнаходжень цього сузір'я. \InputFile Перший рядок вхідного файлу містить число \textbf{M}. Наступні \textbf{M} рядків містять по \textbf{M} цілих чисел кожен --- матрицю відстаней. Далі записано число \textbf{N}, а потім йде \textbf{N} рядків, кожен з яких містить пару цілих чисел \textbf{X_i}, \textbf{Y_i} --- координати \textbf{i}-ої зірки на сьогоднішньому небі. \textbf{2} ≤ \textbf{N} ≤ \textbf{30000}, \textbf{2} ≤ \textbf{M} ≤ \textbf{min(N, 20)}. Координати кожної зірки --- цілі числа, які не перевищують \textbf{10000} за абсолютною величиною. Ніякі дві зірки не знаходяться в одній точці. Задана матриця відстаней симетрична, її головна діагональ містить лише нулі, а всі інші числа додатні і не перевищують \textbf{10^18}. \OutputFile Виведіть кількість можливих місцезнаходжень сузір'я із манускрипту.