Hide

Problem F
Institute of Advanced Category Manipulation

A certain magazine annually ranks universities across the country in various categories, as a service for readers who may be deciding which university to attend. Each university is given three scores $R$, $T$, and $S$ (integers from $0$ to $100$) for its research, teaching, and community service, respectively. These scores are then interpreted somehow and the top universities in a number of categories are named. There are many categories to compete in (research university, undergraduate university, small university, etc.). Sometimes these categories appear to be invented just to make a particular university a “top university” (e.g. top university in rural area with population $30\, 000$ to $45\, 000$).

The Institute of Advanced Category Manipulation (ACM) is not pleased with its ranking, because it is not a top university in any category. The public relations department of ACM has decided that it can invent its own category of universities, and rank each university based on a linear combination of the three scores. The combined score $U$ for each university is calculated by the formula:

\[ U = aR + bT + cS \]

where $a$, $b$, $c$ are constant real numbers. To make sure that the readers do not notice the scores suddenly getting too large or too small, it is required that $a^2 + b^2 + c^2 = 1$. Since some of the scores for ACM are low compared to its peers, they will even allow any of $a$, $b$, and $c$ to be negative. A university is considered a top university in the new category if its combined score is greater than or equal to the combined scores of each of the other universities. Each category is defined by the constants $(a,b,c)$ satisfying the constraints given above.

This idea is quickly catching on among university administrators. For example, the Research University of Ivory Towers has decided to use $(a,b,c) = (0.57735, -0.57735, -0.57735)$. Even with this manipulation, some universities cannot be considered top universities. In the second case of the sample input below, The University of Mediocrity has a score of $R = T = S = 50$. It cannot be considered a top university among the given universities regardless of how it manipulates the categories.

In this problem, you will be given the research, teaching, and community service scores of some universities. Your task is to determine which of these universities can be considered a top university.

Input

The input consists of multiple test cases. The first line of input is a single integer, not more than $10$, indicating the number of test cases to follow. The first line of each case is a positive integer $n$ ($1 \leq n \leq 50$) specifying the number of universities to be considered. The following $n$ lines each contains three integers specifying the research, teaching, and community service scores.

Output

For each case, display on a single line a string consisting of $n$ characters. The $i$-th character is T if the $i$-th university given in the input can be considered a top university and F otherwise.

Sample Input 1 Sample Output 1
2
4
100 0 0
0 100 0
0 0 100
100 100 100
9
100 0 0
0 100 0
0 0 100
100 100 0
100 0 100
0 100 100
100 100 100
0 0 0
50 50 50
TTTT
TTTTTTTTF

Please log in to submit a solution to this problem

Log in