human
What is 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:
PYTHON 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.
 #!/usr/bin/env python
from __future__ import division, print_function

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 solve(n, p, s):
    q = [0] * n
    like = sum(1 if s[i] == '1' else 0 for i in range(n))
    dislike = n - like
    likeslot = set(range(dislike + 1, n + 1))
    dislikeslot = set(range(1, dislike + 1))
    for i in range(n):
        if s[i] == '1' and p[i] > dislike:
            likeslot.discard(p[i])
            q[i] = p[i]
        if s[i] == '0' and p[i] <= dislike:
            dislikeslot.discard(p[i])
            q[i] = p[i]
    likeiter = iter(likeslot)
    dislikeiter = iter(dislikeslot)
    for i in range(n):
        if s[i] == '1' and p[i] <= dislike:
            q[i] = next(likeiter)
        if s[i] == '0' and p[i] > dislike:
            q[i] = next(dislikeiter)
    return q

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        p = inputarr()
        s = input()
        print(*solve(n, p, s))

# region fastio

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b),...