HCHAINS  Islands and Hotel Chains
In Croatia there are N small islands. For the purposes of further tourism development, the government has decided to build exactly one hotel on the each island. The government has contracts with two hotel chains: let's call them A and B. Unfortunately, there is a problem since each hotel chain wants to build as many hotels as possible.
Thus, the following agreement has been made: the hotels will be built such that, for each horizontal or vertical line (that is, if we imagine the problem in the 2D coordinate system, for each line with the equation y = c or x = c), the absolute difference between the number of hotels (on that line) of the chain A and the number of hotels (on that line) of the chain B is at most 1.
Write a program that will, for each small island, determine the hotel chain (A or B) which will build the hotel on that island, such that the upper agreement holds.
Input
In the first line of input there is an integer T, the number of test cases.
For each test case, in the first line there is an integer N, the number of islands.
In the next line there are eight integers: X(1), Y(1), Ax, Bx, Mx, Ay, By, My; each from the interval [1, 100 000], except for X(1) and Y(1) which are from the interval [0, Mx1] and [0, My1], respectively.
2D coordinates of the ith island (for 2 ≤ i ≤ N) are:
X(i) = ( Ax * X(i1) + Bx ) mod Mx;
Y(i) = ( Ay * Y(i1) + By ) mod My.
It is guaranteed that no two islands will have the same position and the solution, not necessarily unique, will always exist.
Note: Author's solution doesn't depend on properties of pseudorandom generator.
Data set is divided into 2 parts:
First part: 1 <= T <= 100, 1 <= N <= 5000
Second part: 1 <= T <= 10, 1 <= N <= 100 000
Output
For each test case, output in a separate line a string of size N, containing only the letters A and B. The ith letter of the string denotes the hotel chain which will build the hotel on the ith island.
Example
Input:
1
10
2 4 8 2 5 6 9 5
Output:
AAAABBBBBA
The points in this example are:
2 4
3 3
1 2
0 1
2 0
3 4
1 3
0 2
2 1
3 0
hide comments
pitcher654:
20180706 19:47:43
Exceptionally bad problem, very cancerogenic 

Aditya Muraletharan:
20130420 12:41:10
Excellent Problem. Had great fun solving it:) 
Added by:  Ivan Katanic 
Date:  20100507 
Time limit:  0.566s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  derived from the problem of International Mathematical Olympiad. prepared by I. KataniÄ‡, A. S. Kurdija and S. Glavina 