human
PYTHON3 solution for "Berland Music is a music streaming service built specifically to support Berland local artist. Its developers are currently working on a song recommendation module.

So imagine Monocarp got recommended n songs, numbered from 1 to n. The i-th song had its predicted rating equal to p_i, where 1 ≤ p_i ≤ n and every integer from 1 to n appears exactly once. In other words, p is a permutation.

After listening to each of them, Monocarp pressed either a like or a dislike button. Let his vote sequence be represented with a string s, such that s_i=0 means that he disliked the i-th song, and s_i=1 means that he liked it.

Now the service has to re-evaluate the song ratings in such a way that:

  * the new ratings q_1, q_2, ..., q_n still form a permutation (1 ≤ q_i ≤ n.
each integer from 1 to n appears exactly once).

  * every song that Monocarp liked should have a greater rating than every song that Monocarp disliked (formally, for all i, j such that s_i=1 and s_j=0, q_i>q_j should hold). 


Among all valid permutations q find the one that has the smallest value of ∑_{i=1}^n |p_i-q_i|, where |x| is an absolute value of x.

Print the permutation q_1, q_2, ..., q_n. If there are multiple answers, you can print any of them.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of testcases.

The first line of each testcase contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of songs.

The second line of each testcase contains n integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n) — the permutation of the predicted ratings.

The third line contains a single string s, consisting of n characters. Each character is either a 0 or a 1. 0 means that Monocarp disliked the song, and 1 means that he liked it.

The sum of n over all testcases doesn't exceed 2 ⋅ 10^5.

Output

For each testcase, print a permutation q — the re-evaluated ratings of the songs. If there are multiple answers such that ∑_{i=1}^n |p_i-q_i| is minimum possible, you can print any of them.

Example

Input

3
2
1 2
10
3
3 1 2
111
8
2...":
assistant
#Here is Python program to find the one that has the smallest value of ∑_{i=1}^n |p_i-q_i|, where |x| is an absolute value of x.
 def bm(n,r,lr,ld):
    c=0
    for x in ld:
        if x==0:
            c=c+1
    ad=r[:c]
    al=r[c:]
    if (len(ad)==0)|(len(al)==0):
        tr=[]
        for x in lr:
            tr.append(str(x))
        return ' '.join(tr)
    vl=[]
    vd=[]
    for i in range(len(lr)):
        if ld[i]==1:
            vl.append(lr[i])
        else:
            vd.append(lr[i])
    vl.sort()
    vd.sort()
    dd={}
    for z in zip(vd,ad):
        dd[z[0]]=z[1]
    dl={}
    for z in zip(vl,al):
        dl[z[0]]=z[1]
    fa=[]
    for i in range(len(lr)):
        if ld[i]==1:
            fa.append(dl.get(lr[i]))
        else:
            fa.append(dd.get(lr[i]))
    tr=[]
    for x in fa:
        tr.append(str(x))
    return ' '.join(tr)
t=int(input())
ln=[]
ls1=[]
ls2=[]
for x in range(t):
    n=int(input())
    s1=str(input())
    s2=str(input())
    ln.append(n)
    ls1.append(s1)
    ls2.append(s2)
la=[]
for i in range(len(ls1)):
    n=ln[i]
    r=[a for a in range(1,ln[i]+1)]
    ar=ls1[i].split(' ',)
    lr=[]
    for y in ar:
        lr.append(int(y))
    sr=ls2[i]
    ldt=list(sr)
    ld=[]
    for z in ldt:
        ld.append(int(z))
    ans=bm(n,r,lr,ld)
    la.append(ans)
for x in la:
    print(x)