You are given a string S of length N consisting of lowercase English letters.

Each lowercase letter ('a' to 'z') belongs to one of two groups: Black or White. The group assignment is fixed for every letter, meaning all occurrences of the same letter always have the same group.

You may perform the following operation any number of times:

• Select any two adjacent characters and swap them only if their corresponding letters belong to different groups.

Determine the lexicographically smallest string that can be obtained after performing any number of valid operations.

---

Input Format

The first line contains an integer T, the number of test cases.

For each test case:

• The first line contains an integer N, the length of the string.

• The second line contains the string S.

• The third line contains a string groups of length 26, consisting only of 'B' and 'W'.

  • groups[0] represents the group of 'a'.
  • groups[1] represents the group of 'b'.
  • ...
  • groups[25] represents the group of 'z'.

---

Output Format

For each test case, print the lexicographically smallest string that can be obtained.

---

Constraints

• 1 ≤ T ≤ 5
• 2 ≤ N ≤ 16000
• The sum of N over all test cases does not exceed 16000
• S contains only lowercase English letters.
• groups contains exactly 26 characters, each either 'B' or 'W'.

---

Sample Input

1
4
ahag
BBBBBBBWBBBBBBBBBBBBBBBBBB

Sample Output

aagh

---

Explanation

Only the letter 'h' belongs to the White group, while 'a' and 'g' belong to the Black group.

A possible sequence of operations is:

• Swap the adjacent characters 'h' and 'a' (different groups): ahag → ahag
• Swap the adjacent characters 'h' and 'g' (different groups): ahag → aagh

No further sequence of valid swaps can produce a lexicographically smaller string.

---

Expected Approach

Observe that adjacent swaps are allowed only between characters belonging to different groups. Characters of the same group cannot cross each other, so their relative order remains fixed. This property can be exploited to construct the lexicographically smallest reachable string efficiently.

Time Complexity: O(N log N) or better.

Space Complexity: O(N)