D. Dot Product Game
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A permutation of $$$1$$$ to $$$n$$$ in this problem is a $$$1$$$-based sequence of $$$n$$$ integers in which every integer from $$$1$$$ to $$$n$$$ appears exactly once. Alice and Bob are playing a game on $$$A = [a_1, a_2, \ldots, a_n]$$$ and $$$B = [b_1, b_2, \ldots, b_n]$$$, two permutations of $$$1$$$ to $$$n$$$. They take turns to perform operations, with Alice going first, and the one with no possible operation loses.

In each turn, Alice can only operate on the permutation $$$A$$$, while Bob can only operate on the permutation $$$B$$$. A valid operation consists of choosing two indices $$$i$$$ and $$$j$$$ on the operable permutation ($$$1 \leq i, j \leq n$$$) and swapping their corresponding elements, under the constraint that $$$\sum_{i=1}^{n}{a_i b_i} = a_1 b_1 + a_2 b_2 + \cdots + a_n b_n$$$, the dot product of these two permutations, must strictly increase after the swap. Namely, a player loses if he or she cannot perform any swap to increase the dot product, and the other player wins the game.

As Alice and Bob are both clever enough to adopt the best strategy, the winner of such a game can be determined from the start. Therefore, they decide to play the game $$$n$$$ times with modifications to make it less boring. Please help them to predict the winners of these $$$n$$$ games.

More specifically, two initial permutations $$$A = [a_1, a_2, \ldots, a_n]$$$, $$$B = [b_1, b_2, \ldots, b_n]$$$, and $$$(n - 1)$$$ modifications $$$[(t_1, l_1, r_1, d_1), (t_2, l_2, r_2, d_2), \ldots, (t_{n - 1}, l_{n - 1}, r_{n - 1}, d_{n - 1})]$$$ will be given. The first game will start from the given permutations $$$A$$$ and $$$B$$$, and for $$$k = 1, 2, \ldots, n - 1$$$, the $$$(k + 1)$$$-th game will start from the permutations for the $$$k$$$-th game after shifting the interval between indices $$$l_k$$$ and $$$r_k$$$ of the permutation $$$t_k$$$ left $$$d_k$$$ times.

Please note that shifting an interval $$$[p_l, p_{l + 1}, \ldots, p_r]$$$ left once will give $$$[p_{l + 1}, p_{l + 2}, \ldots, p_r, p_l]$$$. For instance, shifting the interval $$$[2, 4]$$$ of $$$[1, 2, 3, 4, 5]$$$ left once will give $$$[1, 3, 4, 2, 5]$$$, and twice will give $$$[1, 4, 2, 3, 5]$$$. Besides, shifting the interval $$$[1, 5]$$$ of $$$[3, 1, 4, 5, 2]$$$ left $$$4$$$ times will give $$$[2, 3, 1, 4, 5]$$$.

Input

The first line of the input contains an integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$), indicating the number of test cases. For each test case:

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 5 \times 10^5$$$), indicating the length of the permutations.

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$), indicating the permutation $$$A$$$.

The third line contains $$$n$$$ distinct integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq n$$$), indicating the permutation $$$B$$$.

In the next $$$(n - 1)$$$ lines, the $$$i$$$-th line contains a character $$$t_i$$$ ($$$t_i \in \{\texttt{A}, \texttt{B}\}$$$), and three integers $$$l_i$$$, $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$), and $$$d_i$$$ ($$$1 \leq d_i \leq n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \times 10^5$$$.

Output

For each test case, output a string of length $$$n$$$ in one line, where the $$$i$$$-th character of the string is A if Alice wins the $$$i$$$-th game, or B otherwise (i.e., Bob wins the $$$i$$$-th game).

Example
Input
5
3
1 2 3
1 2 3
A 1 1 1
B 1 1 1
3
1 2 3
2 1 3
A 1 2 1
B 2 2 1
3
1 2 3
2 1 3
A 1 3 1
B 1 2 1
3
1 2 3
3 2 1
A 2 2 1
B 2 3 1
10
1 2 3 4 5 6 7 8 9 10
4 2 3 9 6 1 5 8 7 10
A 2 9 10
B 2 7 9
A 1 10 8
B 4 6 7
B 3 10 6
A 2 5 5
A 8 9 4
B 3 9 3
A 2 7 2
Output
BBB
ABB
AAB
AAB
AABBBBAAAA
Note

For the third test case of the sample case:

  • The first game starts with $$$A = [1, 2, 3]$$$, $$$B = [2, 1, 3]$$$;
  • The second game starts with $$$A = [2, 3, 1]$$$, $$$B = [2, 1, 3]$$$;
  • The third game starts with $$$A = [2, 3, 1]$$$, $$$B = [1, 2, 3]$$$.