human
Can you solve the below in PYTHON?
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...

=====
Give me a Python code 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?
assistant
#Here is Python code 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.

#!/usr/bin/env python
from __future__ import division, print_function
from collections import defaultdict

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

def chk(m,um,mc,umc):
    ans=float("Inf")
    if(m<0 or um<0 or mc<0 or umc<0):
        return ans
    if(m%2==1 and mc==1+m-mc):
        ans=min(ans,m)
    if(um%2==0 and umc==um-umc):
        ans=min(ans,um)
    return ans

from types import GeneratorType

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to

    return wrappedfunc

@bootstrap
def dfs(i,g,vis,color,count):
    vis[i]=True
    contains=False
    for j in g[i]:
        if(not vis[j]):
            x=yield dfs(j,g,vis,color,count)
            count[i]+=x
            if(x==0):
                contains=True
    if(contains==False and color[i]==0):
        count[i]=1
    else:
        count[i]=0
    yield count[i]
@bootstrap
def dfs1(i,g,vis,count,g1):
    vis[i]=True
    ans=1
    for j in g[i]:
        if(not vis[j]):
            g1[i].append(j)
            x=yield dfs1(j,g,vis,count,g1)
            ans+=x
    count[i]=ans
    yield ans
@bootstrap
def dfs2(g1,i,vis):
    vis[i]=True
    for j in g1[i]:
        yield dfs2(g1,j,vis)
    yield 0
class FenwickTree:
    def __init__(self, x):
        """transform list into BIT"""
        self.bit = x
        for i in range(len(x)):
            j = i | (i + 1)
            if j < len(x):
                x[j] += x[i]

    def update(self, idx, x):
        """updates...