C. Champion's Meeting (Easy)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The only difference between the easy and hard versions is the constraint on $$$k$$$, $$$a_i$$$, and $$$b_i$$$.

In the game of Umamusume, racers are divided into $$$k$$$ prestige levels numbered from $$$1$$$ to $$$k$$$, inclusive. Prestige levels are ordered, with $$$1$$$ being the most prestigious, and $$$k$$$ being the least prestigious.

For the upcoming Champion's Meeting, Magikarp has prepared two teams of racers, Team A and Team B. Team A has $$$n$$$ racers with prestige levels $$$a_1, a_2, \cdots, a_n$$$, and Team B has $$$m$$$ racers with prestige levels $$$b_1, b_2, \cdots, b_m$$$. All of Magikarp's racers have a unique prestige level. However, organizer Tazuna has informed Magikarp that he is only allowed to submit a single team, so he should merge his two teams into a single team of size $$$n+m$$$, Team C.

The members of both teams are quite stubborn, so members of Team A must remain in the same order in Team C, and members of Team B must remain in the same order in Team C.

To maximize his chances of success, Magikarp also wants to put more prestigious racers towards the front. He will do this by trying to find a sequence of prestige levels in Team C that is lexicographically smallest.

Help Magikarp merge his teams and print out any lexicographically minimal solution. If multiple answers exist, print out any of them.

Input

The first line of input will contain $$$3$$$ space-separated integers $$$n$$$, $$$m$$$, and $$$k$$$ $$$(1\le n,m\le 2\cdot 10^5, \mathbf{k=n+m})$$$ — the number of racers in Team A, the number of racers in Team B, and the number of prestige levels.

The second line of input will contain $$$n$$$ space-separated integers representing $$$a_1, a_2, \cdots, a_n$$$ $$$(1\le a_i\le k)$$$ — the prestige levels of racers in Team A.

The third line of input will contain $$$m$$$ space-separated integers representing $$$b_1, b_2, \cdots, b_m$$$ $$$(1\le b_i\le k)$$$ — the prestige levels of racers in Team B.

All racers will have unique prestige levels.

Output

Output a single string of $$$n+m$$$ characters, where each character is either A or B. If the $$$i$$$th character is A, then the $$$i$$$th racer in Team C is the next unused racer from Team A. If the $$$i$$$th character is B, then the $$$i$$$th racer in Team C is the next unused racer from Team B.

Example
Input
5 7 12
2 9 3 11 7
1 4 5 6 8 10 12
Output
BABBBBAABAAB
Note

Here, we choose the 1st racer from Team B to be the 1st racer in Team C since the 1st character of the output string is B. We then choose the 1st racer from Team A to be the 2nd racer in Team C since the 2nd character of the output string is A. Then we choose the 2nd racer from Team B, the 3rd racer from Team B, the 4th racer from Team B, etc.

The final array of prestiges we get will then be:

$$$$$$ [1,2,4,5,6,8,9,3,10,11,7,12] $$$$$$

It can be shown that this is the only solution to this sample testcase.