Hacking tasks
The scientific committee of JBOI 2016 together with the competitors is
placed in the ethno complex Macedonian Village. The contestants found the tasks in the first competition day very hard, so they are organizing to hack the tasks for the second competition day. Are you ready to be a spy?
The scientific committee consists of N members (with IDs numbered from 1
to N), placed somewhere in the Macedonian Village. Unfortunately, we don't
know exactly where they are. What we do know - each member has different
position. In fact the position of the i-th member could be expressed as (xi, yi).
Each member has exactly one reporter, also a member, to whom he should
send a message. A reporter is chosen according to one of two used
connectivity systems: Armadillo or Benedictus.
According to Armadillo, the reporter of the i-th member is the member most
distant to him (according to standard metrics: Euclidean distance where
the distance between two points (x1, y1) and (x2, y2) is defined as (x1 - x2)2 + (y1 - y2)2).
According to Benedictus, the reporter of the i-th member becomes the
member which has the lowest y-coordinate that is strictly bigger than yi. If such member doesn't exist then the member with the lowest y coordinate is
chosen.
It's easy to note, that these systems aren't complete and there can be
conflicts. Because of that, the Chairman decided that when according to
the used system the reporter can't be chosen uniquely, for Armadillo the
member with the lowest ID among them will be chosen and for Benedictus
the member with the lowest x-coordinate among them.
It's everything we know so far. Now it's your turn. We've come across a list
of reporters of each of the members. We can't distinguish whether the
scientific committee uses Armadillo or Benedictus. Will you manage?
Input
Because there are just two possible connectivity systems, to prevent contestants from earning points by randomly printing the result, each input will consists of a number of situations.
line 1: M, the number of situations to consider
next M lines: first N, the number of members in the scientific committee, and then N integers r1,r2, r3,...,rN, where ri is the ID of the reporter of the ith member.
Subtasks
(10 points) 1 ≤ M ≤ 20, 2 ≤ N ≤ 20
(15 points) 1 ≤ M ≤ 10, 2 ≤ N ≤ 1000, There is no BOTH in the solution.
(20 points) 1 ≤ M ≤ 10, 2 ≤ N ≤ 100000, There is no BOTH in the solution.
(15 points) 1 ≤ M ≤ 10, 2 ≤ N ≤ 100000, The positions of all members are points that form a regular n-sided polygon
(20 points) 1 ≤ M ≤ 10, 2 ≤ N ≤ 1000
(20 points) 1 ≤ M ≤ 10, 2 ≤ N ≤ 100000
Output
M lines: For each situation in each line you need to print “A” if only Armadillo strategy can be used, “B” if only Benedictus strategy can be used or “BOTH” if both strategies can be used.
Constraints
Time limit: 1500 milliseconds
Memory limit: 64 megabytes
Examples
input 3 3 2 3 1 4 2 1 4 3 2 2 1 | output B A BOTH |
Explanation: There are 3 situations to consider (M=3).
For the first list of reporters, the scientific committee could only use Benedictus. Example positions of the committee members with ID numbers 1, 2 and 3 are: (0, 0), (0, 1) and (0, 2), accordingly.
For the second list of reporters, Armadillo is only possible strategy and example positions of the committee members with ID numbers 1, 2, 3 and 4 are: (0, 0), (1, 1), (1, 0), (0, 1).
For the third sample test we can't uniquely determine the system. If the coordinates of the member with ID=1 is (0, 0), and the coordinates of the member with ID=2 is (1, 1), both answers are correct. Therefore, we print BOTH.