14 1 s 128 MB

Algospot.com's annual programming contest is drawing near, and there are overwhelming number of registrations (10,000+!). We have only 5 judges, so we cannot handle this number of teams. Therefore, we decided to admit only the "true nerds" to the contest.

JongMan came up with a theory that whether a person's *nerdiness *is dependent on a linear combination of two factors: their shoe size and their typing speed per minute. In his theory, the nerd score

F = A * (shoe size) + B * (typing speed per minute)

will be able to determine whether the guy is a nerd or not. The higher the score, the nerdier the guy is. We intend to set a threshold T; we will only admit people with scores equal to or above T.

However, will this theory work? To find it out, we grabbed the data from some people we personally know. We know their shoe size and typing speeds, and we know whether each of them is a nerd or not. Will there be a set of parameters A, B and T which can successfully separate nerds from the others? Write a program to confirm this.

Please note that A, B and T can be arbitrary real numbers.

The first line of the input file will contain the number of test cases, C (C = 50). Each test case begins n (6 <= n <= 5,000) with the number of people we personally know. n lines will follow with three nonnegative integers in each line. The first integer is 1 if the person is a nerd, and 0 otherwise. The second number and the third number will represent the person's shoe size and typing speed per minute. These two numbers will be in the range [0, 10000].

There will be always at least three people from both group of people - nerds and non-nerds. The group of vectors [shoes size, typing speed] formed by each group will be linearly independent.

For each test case, print one line. The line must contain "THEORY HOLDS" if there are one or more set of parameters which satisfies the given data. "THEORY IS INVALID" should be printed in the other case. See the sample output for details.

## Sample Input | ## Sample Output |
---|---|

3 8 1 2 3 1 3 4 1 4 5 1 2 5 0 4 1 0 5 5 0 3 3 0 4 4 6 1 1 5 1 5 1 1 1 1 0 2 2 0 4 1 0 1 4 6 1 10 10 0 10 10 1 5 15 1 5 5 0 15 15 0 15 5 | THEORY HOLDS THEORY IS INVALID THEORY IS INVALID |