9156: Palindrome Subsequence

You are given a string $s$ of length $n$, and there are some fixed positions in the string. You need to find a palindrome subsequence of $s$ which contains all fixed positions and has the largest lexicographical order.

Formally, let the string s=c1c2...cns=c_1c_2...c_ns=c1c2...cn, and the fixed positions F={a1, a2, ..., am}  (1≤ai≤n)F=\{a_1,\ a_2,\ ...,\ a_m\}\ \ (1\le a_i\le n)F={a1, a2, ..., am}  (1≤ai≤n). You should find a sequence P=(p1, p2, ..., pt)P=(p_1,\ p_2,\ ...,\ p_t)P=(p1, p2, ..., pt) (1≤pi≤n,  pi<pi+1)(1\le p_i\le n,~\ p_i<p_{i+1})(1≤pi≤n,  pi<pi+1) satisfying:

• ∀1≤i≤m,  ai\forall 1\le i\le m, ~\ a_i∀1≤i≤m,  ai appears in $P$.
• cp1cp2...cptc_{p_1}c_{p_2}...c_{p_t}cp1cp2...cpt is a palindrome and its lexicographical order is the largest.

A string is a palindrome if it reads the same backwards as forwards.

The first line contains a single integer $T$ (1≤T≤1000)(1\le T\le 1000)(1≤T≤1000) - the number of test cases.
For each test case, the first line contains an integer $n$ ($1\le n\le 1000$), denoting the length of the string.
The second line contains a string $s$ of length $n$, and $s$ consists of first $10$ lowercase letters (\texttt{`a' - `j'}).
The third line contains $n$ integers a1, a2, ..., ana_1,~ a_2,~ ...,~ a_na1, a2, ..., an (ai∈{0,1})(a_i\in \{0,1\})(ai∈{0,1}). ai=1a_i=1ai=1 denotes $i$ is a fixed position.
It is guaranteed that the sum of $n$ over all test cases does not exceed 1000.

For each test case, print a string - the palindrome subsequence that has the largest lexicographical order. If the answer doesn't exists, print ``-1'' (without quotes) instead.

4
10
abdcdcaddb
0 0 0 0 0 0 0 0 0 0
5
abcbb
0 0 0 1 0
5
abcbb
1 1 1 1 1
11
hehhehahhhh
0 1 0 0 0 0 0 0 1 0 0

dddd
bcb
-1
hehheh