Rotating Rod Sweep

We have a rod (OA) that rotates clockwise about the origin (O). Initially, the rod points upward (i.e. in the direction of the positive (Y)–axis) and has a length of 1 (i.e. (OA=1)). In the plane there are (n) objects; the (i)th object is at (\left(x_i,y_i\right)) and has a value (z_i). The rod rotates continuously (at a constant angular speed, say 1 radian per unit time). When the rod’s direction exactly coincides with an object’s polar angle (\theta_i) (measured in radians in the range ([0, 2\pi)) where (\theta_i) is computed from the positive (X)–axis) and the distance (r_i=\sqrt{x_i^2+y_i^2}) is less than or equal to the current rod length (L) (initially 1), that object is swept (i.e. removed) and the rod instantly extends by (z_i); note that if the rod’s newly extended segment now touches other objects along the same ray (i.e. having the same polar angle) they are also removed simultaneously. All objects removed in one such event receive the same rank. The rank of a sweep event is defined by the order in which objects disappear – the first event gets rank 1, the next event rank 2, and so on. If an object is never swept (i.e. the rod never becomes long enough when its direction aligns with the object), output (-1) for that object.

The relation between time and the rod’s orientation is as follows. Assume the rod rotates at 1 radian per unit time. At time (T), the rod’s angle is (\alpha(T)=\frac{\pi}{2}- (T \bmod 2\pi)) (in radians, taken modulo (2\pi)). For an object with polar angle (\theta), let its offset be defined by [ \delta = \Bigl(\frac{\pi}{2} - \theta \Bigr) \bmod 2\pi. ] If the current time (T) has (T \bmod 2\pi \le \delta), then the object’s next occurrence (when the rod’s direction matches (\theta)) is at time (T - (T \bmod 2\pi) + \delta); otherwise, it is at (T - (T \bmod 2\pi) + 2\pi + \delta). In our simulation, we always choose the unswept object (with (r \le L)) that will be hit the earliest in time – let its polar angle be (\theta_0). Then, at that event time, the rod’s direction is (\theta_0) and we remove all unswept objects whose polar angle equals (\theta_0) (within a small tolerance) and whose distance is (\le L); for each object removed, we add its value (z_i) to (L). All these objects get the same rank (the rank of the current event). The simulation starts with (L=1) and time (T=0), and continues until no unswept object satisfies (r_i\le L). For those objects that never get swept, output (-1).

Input Format and Output Format are described below.

inputFormat

The first line contains an integer (n) (the number of objects). Each of the following (n) lines contains three space-separated numbers: (x_i), (y_i) and (z_i). (x_i, y_i) represent the coordinates of the (i)th object and (z_i) (a positive number) is the value by which the rod length increases when object (i) is swept.

outputFormat

Output (n) integers separated by spaces. The (i)th integer is the rank of the (i)th object (according to the order of their sweep events). Objects swept simultaneously have the same rank. If an object is never swept, output (-1) for that object.

sample

3
0 1 2
1 0 3
-1 0 1

1 2 3