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