False figures
Эта задача является валидатором тестов к предыдущей задаче. Самое сложное уже проверили, вам предлагается всего лишь проверить вложенность кругов.
Представим таблицу {a_ij} из 1000 строк и 1000 столбцов. Дано Q запросов вида:
i_k j_k r_k, 1 ≤ k ≤ Q
Каждый из них определяет область из элементов таблицы {a_ij} таких, что (i-i_k)^2 + (j-j_k)^2 ≤ r^2_k.
Для удобства будем называть эту область кругом с центром в ячейке (i_k, j_k) и радиусом r_k.
Пара запросов k и l (k < l) считается невалидной, если круги k и l имеют общие ячейки, и существует круг t: k < t≤ l, который не содержится в круге k. Круги различных запросов могут совпадать.
Определить, есть ли среди запросов хотя бы одна невалидная пара.
Входные данные
В первой строке число Q — количество запросов. Далее в Q строках описаны запросы по три целых числа в каждой строке i_k, j_k, r_k — номера строки и столбца центральной ячейки и радиус круга. Ячейки нумеруются с 1.
Выходные данные
Если есть хотя бы одна невалидная пара запросов, вывести номера этих запросов в произвольном порядке. Если таких пар много, разрешается вывести любую из них. Если невалидных пар нет, вывести "Ok".
Ограничения
1 ≤ Q ≤ 10^6
1 + r_k ≤ i_k ≤ 1000-r_k
1 + r_k ≤ j_k ≤ 1000-r_k
0 ≤ r_k < 500