B. Лунный гольф
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Посещая Луну, Незнайка открыл для себя совершенно новую игру, похожую на земной гольф. В лунном гольфе, также как и в земной разновидности, нужно забивать мячи в лунки. Правда в качестве лунок выступают кратеры, а в качестве мячей – метеориты.

Метеориты бывают разной массы, и задача игрока – забить метеориты в кратеры так, чтобы суммарная масса забитых метеоритов была максимальной. При этом правила запрещают забивать в один кратер более одного метеорита.

По правилам лунного гольфа:

  1. игрок всегда находится в точке $$$(0, 0)$$$;
  2. кратеры – идеальные окружности;
  3. при попадании не в центр кратера, а хотя бы на его границу – метеорит неизбежно скатывается к центру и считается забитым;
  4. кратеры не пересекаются и не касаются друг друга;
  5. точка $$$(0, 0)$$$, в которой находится игрок, не попадает внутрь кратера.

Силы Незнайки не бесконечны, и максимальное расстояние, на которое он может забить метеорит, зависит от массы $$$m$$$ этого метеорита и рассчитывается по формуле $$$ d = \sqrt{10^6 / m}$$$.

Помогите Незнайке выиграть – напишите программу, которая по координатам лунок и массе метеоритов определит оптимальную стратегию игры. Для простоты, будем считать, что Незнайка не умеет промахиваться и стратегия просто описывает, какой метеорит в какой кратер нужно забить.

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

В первой строке записано целое число $$$ n $$$ $$$( 1 \leq n \leq 10^4 )$$$ – количество метеоритов. Во второй строке содержится $$$ n $$$ целых чисел $$$ w_i $$$ $$$( 1 \leq w_i \leq 10^6 )$$$, разделенных пробелами – веса метеоритов.

В третьей строке содержится целое число $$$ k $$$ $$$( 1 \leq k \leq 10^5 )$$$ – количество кратеров на игровом поле. В преследующих $$$ k $$$ строках содержатся тройки целых чисел $$$ x_i , y_i, r_i $$$ $$$( -2\,000 \leq x_i, y_i \leq 2\,000 $$$, $$$ 1 \leq r_i \leq 10)$$$, разделенных пробелом – координаты центров кратеров и их радиусы.

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

Первая строка должна содержать целое число $$$ r $$$ $$$( 0 \leq r \leq min(n, k))$$$ – количество метеоритов, которые предполагается забить. Далее следуют $$$ r $$$ строк, в каждой из которых содержатся два целых числа числа $$$ s_i $$$ $$$(1 \leq s_i \leq n )$$$ и $$$ t_i $$$ $$$( 1 \leq t_i \leq k )$$$ – номер метеорита и номер кратера, куда его следует забить. Метеориты и кратеры нумеруются в порядке появления во входных данных. Нумерация начинается с единицы.

Примеры
Входные данные
3
1 100 10000
3
0 10 1
0 100 1
0 1000 1
Выходные данные
3
1 3
2 2
3 1
Входные данные
2
2 3
2
1000 0 1
0 1000 1
Выходные данные
0