False figures#4598
This problem is a validator for the tests of the previous problem. The hardest part has already been checked; your task is only to check the nesting (positioning) of circles.
Imagine a table \{a_{ij}\} with rows and columns. There are queries of the form:
i_k\ j_k\ r_k, 1 \leq k \leq Q
Each query defines a region of elements in the table \{a_{ij}\} such that (i - i_k)^2 + (j - j_k)^2 \leq r_k^2.
For convenience, we will call this region a circle with center at (i_k, j_k) and radius r_k.
A pair of queries and (k < l) is called invalid if circles and share at least one cell, and there exists a circle with k < t \leq l, which is not contained within circle . Circles from different queries may coincide.
Determine whether there is at least one invalid pair among the queries.
The first line contains the integer — the number of queries. Then each of the next lines describes a query with three integers i_k, j_k, r_k — the row and column of the center cell and the radius of the circle. Cells are numbered from .
If there is at least one invalid pair, output the numbers of such queries in any order. If there are multiple such pairs, output any one of them. If there are no invalid pairs, output Ok.
Constraints
1 \leq Q \leq 10^6
1 + r_k \leq i_k \leq 1000 - r_k
1 + r_k \leq j_k \leq 1000 - r_k
0 \leq r_k < 500
Example 1