You are given an integer $$$n$$$ and a binary string$$$^{\text{∗}}$$$ $$$s$$$ of length $$$n$$$.

For a permutation$$$^{\text{†}}$$$ $$$p$$$ of length $$$n$$$ and an integer $$$x$$$, we define $$$\text{find}(x)$$$ as in the following pseudocode:

function find(int x):
    l := 1
    r := n
    while l <= r:
        let m be a random integer between l and r (inclusive)
        if p[m] == x
            return m
        if p[m] > x:
            r := m - 1
        else:
            l := m + 1
    return undefined     // not found

We call an integer $$$x$$$ ($$$1\le x\le n$$$) stable if and only if $$$\text{find}(x)$$$ is always not undefined and $$$p_{\text{find}(x)}=x$$$ always holds, no matter how the value of $$$m$$$ is selected in the process of the pseudocode.

You have to construct a permutation $$$p$$$ of length $$$n$$$, such that:

For each $$$1\le i\le n$$$, the integer $$$i$$$ is stable if and only if $$$s_i=\mathtt{1}$$$.

Or determine that no such permutation exists.

$$$^{\text{∗}}$$$A binary string is a string where each character is either $$$\mathtt{0}$$$ or $$$\mathtt{1}$$$.

$$$^{\text{†}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\le n \le 2\cdot 10^5$$$) — the length of the permutation.

The second line contains the binary string $$$s$$$ of length $$$n$$$ ($$$s_i=\mathtt{0}$$$ or $$$\mathtt{1}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case:

If no such permutation exists, print "NO" in the only line of output.
Otherwise, print "YES" in the first line of output. Then output $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1\le p_i\le n$$$) in the second line — the permutation you constructed.

You can output the token in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

If there are multiple answers, you may print any of them.

Note

In the first test case, we have constructed $$$p=[1,2,3]$$$. Take $$$\text{find(2)}$$$ as an example:

In the beginning, $$$l=1$$$ and $$$r=3$$$;
We will select $$$m$$$ as a random integer between $$$l=1$$$ and $$$r=3$$$.
- If we choose $$$m=1$$$:
  - $$$p_1=1 \lt 2$$$, so $$$l$$$ is set to $$$m + 1 = 2$$$. Now $$$l=2$$$ and $$$r=3$$$;
  - We will select $$$m$$$ as a random integer between $$$l=2$$$ and $$$r=3$$$.
  - If we choose $$$m=2$$$: $$$p_2=2$$$, so the return value is $$$2$$$.
  - If we choose $$$m=3$$$: $$$p_3=3 \gt 2$$$, so $$$r$$$ is set to $$$m-1=2$$$. Now $$$l=2$$$ and $$$r=2$$$, so we can only select $$$m=2$$$. $$$p_2=2$$$, so the return value is $$$2$$$.
- If we choose $$$m=2$$$:
  - $$$p_2=2$$$, so the return value is $$$2$$$.
- If we choose $$$m=3$$$, the process is similar to that when $$$m=1$$$ is chosen. The return value is always $$$2$$$.
Thus, no matter how $$$m$$$ is selected during the process, the return value of $$$\text{find}(2)$$$ is always $$$2$$$.

So $$$p_{\text{find}(2)}= p_2 = 2$$$ always holds, and the integer $$$2$$$ is stable.

Similarly, we can show that integers $$$1$$$ and $$$3$$$ are also stable. Thus, the permutation $$$p = [1, 2, 3]$$$ is a valid answer.

In the second test case, we have constructed $$$p=[2,4,3,5,1]$$$. Take $$$\text{find(3)}$$$ as an example:

In the beginning, $$$l=1$$$ and $$$r=5$$$;
We will select $$$m$$$ as a random integer between $$$l=1$$$ and $$$r=5$$$. Let's choose $$$m=2$$$;
$$$p_2=4 \gt 3$$$, so $$$r$$$ is set to $$$m-1=1$$$. Now $$$l=1$$$ and $$$r=1$$$;
We will select $$$m$$$ as a random integer between $$$l=1$$$ and $$$r=1$$$. We can only choose $$$m=1$$$;
$$$p_1=2 \lt 3$$$, so $$$l$$$ is set to $$$m + 1 = 2$$$. Now $$$l=2$$$ and $$$r=1$$$;
Since $$$l \gt r$$$, the loop is exited and the return value is undefined.

Thus, the return value of $$$\text{find}(3)$$$ is undefined, so the integer $$$3$$$ is not stable.

Similarly, we can show that integers $$$1$$$, $$$2$$$, $$$4$$$, and $$$5$$$ are also not stable. Thus, $$$p = [2, 4, 3, 5, 1]$$$ is a valid answer.

Some other permutations, such as $$$p=[5,4,3,2,1]$$$ and $$$p=[3,5,1,4,2]$$$, are also valid answers. You may print any of them.

In the third test case, it can be proven that no such permutation exists.

Idx	Name	Rating
A	Equal Occurrences	800
B	Merging the Sets	1100
C	Wrong Binary Search	1300
D1	Max Sum OR (Easy Version)	1500
D2	Max Sum OR (Hard Version)	2000
E	Yet Another MEX Problem	2300
F	Bubble Sort	2900

Codeforces Round 1052 (Div. 2)