Babel Towers

Babel Inc. is a company that designs structures for skyscrapers. They have developed a simple technique to estimate the feasibility of a design, based on the fact that their designs are equivalent to stack blocks of circular section and constant height. The height of a block is used as the unit of lineal measure. Blocks are all made of the same non deformable uniform material, so that the weight of a block is proportional to its volume and its center of mass is the geometrical center of the block. A typical block is of the form which weight is determined by the radius of the circular section (because every one has height 1). For n ≥ 1, an n-tower is a stack of n blocks. Blocks in an n-tower are numbered 0,1,...,n−1, from the bottom to the top. Given an n-tower, its k-subtower is defined as the k-tower with the first k blocks of the n-tower, 0 ≤ k < n. An example of a 5-tower could look like the following figure: A tower is feasible when it can be built putting its blocks one by one from bottom to top. At each building step the correspond- ing subtower should be stable, i.e., every block of it must remain in the position that it is designed to stay. When placing a block results in a stack of blocks which part of it has a center of mass that lies out of the base on that it is supported we say that the resulting tower collapses and is unfeasible. Babel Inc. does not consider stable a situation where the center of mass of the system of blocks that are supposed to rest on a block lies on the border of the supporting surface. For instance, two blocks of the same dimensions with one of them placed centered on the circumference of the other constitute a 2-tower that collapses; but if the second one is placed within the circle of the first one the system is feasible. Your problem is to help Babel Inc. in the evaluation of tower designs. Given a design for a n-tower you must judge if it is feasible and, if it is not, you must tell at which floor it would collapse. In this last case you give k as answer, with 0 < k < n, if the (k − 1)-subtower is feasible but the k-subtower collapses. Input The input file contains several test cases. Each test case begins with a line indicating N, 0 < N < 1000, the number of blocks that the designed tower should have. Then, there is a line describing each one of the blocks. The block k, 0 ≤ k < N, is described by a line containing 3 integers separated by blanks, of the form xk yk rk which indicates that the block k with radius rk must be placed supported on the block k − 1 (exception: block 0 is placed on the ground) with its center of mass on the point ⟨xk , yk , k + 0.5⟩ with respect to a grid with origin in ⟨0,0,0⟩, for xk,yk ≤ |105| and 1 ≤ rk ≤ 105. A case begin with N = 0 means that there are no more cases to analyze.

2/2 Output Output texts for each input case are presented in the same order that input is read. For each test case the answer must be of the form ‘Feasible’ if the design is feasible. In other case, the answer should be of the form ‘Unfeasible k’ indicating that the (k − 1)-subtower is feasible but the k-subtower is unfeasible. Sample Input 3 0 0 10 2 0 12 -4 1 1 4 0 0 12 0 0 10 0 9 10 0 17 5 4 004 014 104 -1 -1 4 2 10 10 5 003 0 Sample Output Feasible Unfeasible 3 Feasible Unfeasible 1