human
Give me a 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 given the following:
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...
Using python3 can you solve the prior task?
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.

from __future__ import print_function 
from os import environ
import sys
import math
from bisect import bisect_left
# from collections import defaultdict
if environ.get("epoweripi"):
    sys.stdin = open('../../input.txt', 'r')
    sys.stdout = open('../../output.txt', 'w')

input = sys.stdin.readline
mod = (10**9) + 7
def I(): return input().strip() 
def II(): return int(input().strip())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

#if using python3
if sys.version[0]=="3":
    print = sys.stdout.write 
    def P(z=''):    
        print(str(z)+'\n')
    def LP(z=[]): 
        for i in z:
            print(str(i)+' ')
        print('\n')
#if using pypy2/python2
else:
    def P(z=''):    
        print(str(z))
    def LP(z=[]): 
        for i in z:
            print(str(i)+' ', end='')
        print()

######## mathematical functions
def gcd(a, b):
    return a if b==0 else gcd(b, a%b)
def sieve(n):
    isPrimes = [True for i in range(n+1)]
    isPrimes[0], isPrimes[1] = False, False
    p = 2
    while p*p<=n:
        if isPrimes[p]==True:
            for j in range(p*p,n+1,p):
                isPrimes[j] = False
        p+=1
    #return accordingly
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
########

def solve():
    n = II()
    l = LI()
    s = I()
    idxs = [i for i in range(n)]
    idxs.sort(key =  lambda x: (s[x], l[x]))
    # P(idxs)
    new_rating = [0 for x in range(n)]
    k = 1
    for i in idxs:
        new_rating[i] = k
        k+=1
    LP(new_rating)

def main():
    for _ in range(II()):
        solve()

if __name__=="__main__":
    main()