Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

D. Рыцари
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Над Берляндией снова сгустились тучи. Армия злого лорда Ван де Марта собирается захватить королевство. На военный совет созванный королём Берляндии Валерием Суровым прибыло n рыцарей. После долгих дискуссий стало ясно, что в королевстве есть ровно n опорных точек (сдача каждого из них врагу равносильна поражению в войне) и каждый рыцарь займёт одну из этих точек.

Берляндия разделена на m + 1 область m заборами, и единственный способ перейти из одной области в другую это перелезть через забор. Каждый забор представляет собой окружность на плоскости, причём никакие два забора не имеют общих точек и ни одна опорная точка не находится на заборе. Вам задано k пар чисел ai, bi. Для каждой пары вам нужно узнать: сколько заборов придётся пересечь рыцарю, находящемуся в опорной точке номер ai, чтобы достигнуть опорной точки bi (в случае если Ван де Март нанесёт первый удар в опорную точку номер bi). Поскольку каждый рыцарь путешествует на коне (а коня непросто перекидывать через забор), то вам нужно для каждой пары найти минимальное число пересечений.

Входные данные

В первой строке входных данных записано три целых числа n, m, k (1 ≤ n, m ≤ 1000, 0 ≤ k ≤ 100000). В следующих n строках записано по два целых числа Kxi, Kyi ( - 109 ≤ Kxi, Kyi ≤ 109) — координаты опорной точки номер i. Опорные точки могут совпадать.

Каждая из следующих m строк описывает забор номер i тремя целыми числами ri, Cxi, Cyi (1 ≤ ri ≤ 109,  - 109 ≤ Cxi, Cyi ≤ 109) — радиусом и центром окружности, на которой находится соответствующий забор.

Далее заданы k пар целых чисел ai, bi (1 ≤ ai, bi ≤ n), каждая в отдельной строке — запросы на которые вам придётся отвечать. ai и bi могут совпадать.

Выходные данные

Выведите ровно k строк, в каждой из которых записано одно число — ответ на соответствующий запрос.

Примеры
Входные данные
2 1 1
0 0
3 3
2 0 0
1 2
Выходные данные
1
Входные данные
2 3 1
0 0
4 4
1 0 0
2 0 0
3 0 0
1 2
Выходные данные
3