Note: In this problem, all sequence indices are 1-based.

What does the heartbeat of a robot look like when arranged as a graph?

You have a competitive programming robot that beats $n$ times per minute, with the intensity of the $i$-th heartbeat being $a_i$. Here, $a_1 \sim a_n$ is a permutation of $1 \sim n$.

Let $A_i$ be the sequence obtained by removing the $i$-th element from sequence $a$, i.e., $A_i = [a_1, \dots, a_{i-1}, a_{i+1}, \dots, a_n]$.

For a sequence $p$ with distinct elements, let $G(p)$ be an undirected graph with $|p|$ vertices, labeled $1 \sim |p|$. For every pair of positive integers $1 \le i < j \le |p|$, there is an edge between vertex $i$ and vertex $j$ in $G(p)$ if and only if for all $k \in [i, j] \cap \mathbb{Z}$, $p_k \in [\min(p_i, p_j), \max(p_i, p_j)]$. Let $F(p)$ be the length of the shortest path from vertex $1$ to vertex $|p|$ in $G(p)$, where the length of a path is defined as the number of edges.

Let $f(a) = [F(A_1), F(A_2), \dots, F(A_n)]$.

Given a sequence $[b_1, \dots, b_n]$ of length $n$, find any permutation $a$ of $1 \sim n$ such that $f(a) = b$. It is guaranteed that a solution exists.

In some subtasks, the competitive programming robot "Little G" will provide you with some "hints": Let $G_0 = G(a)$, and let $path_0$ be the set of vertices forming a shortest path from $1$ to $n$ in $G_0$. Let $path_j$ be the set of vertices forming a shortest path from the start vertex to the end vertex in $G(A_j)$ (note: for convenience, the vertex labels in $path_j$ refer to the indices in the original sequence $a$, see Example 2). Little G may provide all $path_j$ (including $path_0$), or only $path_0$, or no hints at all. See the Input section for details.

It is guaranteed that the provided hints are correct, meaning there exists at least one permutation that satisfies all hints.

A checker.cpp is provided in the files; you can use it to verify your output. The usage is ./checker input output output, where input and output are the input file and your output file, respectively. testlib.h is also provided; please place it in the same directory as the checker to compile it.

Input

The first line contains two positive integers, the subtask number $S$ and the number of test cases $T$.

Each of the $T$ test cases is formatted as follows: the first line contains a positive integer $n$, and the second line contains $n$ positive integers $b_1, \dots, b_n$.

Specifically:

1. If $S=5$, each test case will include $n+1$ additional lines. The $i$-th line of these $n+1$ lines is a binary string $c_i$ of length $n$, where $c_{i,j} = [j \in path_{i-1}]$.
2. If $S=6$, each test case will include a third line containing a binary string $c$ of length $n$, where $c_i = [i \in path_0]$.

Note:

1. Even if your program does not need the hints, you must still read the array $c$ when $S=5$ or $S=6$.
2. For a given input $b$, the valid permutation $a$ may not be unique, and consequently, $c$ may not be unique. Your output is not required to match the provided $c$ constraints; it is considered correct as long as it satisfies the $b$ constraints.

Different variables on the same line are separated by a single space.

Output

For each test case, output a single line containing $n$ positive integers representing the permutation $a$ you found.

Examples

Input 1

9 11
4
2 2 1 1
4
2 2 2 2
4
2 1 1 2
7
5 5 4 4 4 5 5
7
1 3 2 2 2 2 4
7
3 3 2 4 4 5 3
8
2 2 3 5 3 3 3 4
8
5 4 4 4 4 6 6 5
8
4 4 4 2 4 4 2 3
9
4 7 5 5 5 5 3 4 4
9
3 4 4 4 4 4 4 4 6

Output 1

1 2 4 3
2 1 4 3
1 3 2 4
3 1 7 2 6 4 5
3 1 6 4 2 5 7
2 3 1 6 4 7 5
5 6 3 1 7 4 2 8
1 8 2 7 3 5 6 4
6 3 2 7 4 5 1 8
5 8 6 3 7 1 9 2 4
2 9 3 1 8 5 7 6 4

Note 1

Consider the first test case in the example. One solution is $a=[1,2,4,3]$. $A_1, A_2, A_3, A_4$ are $[2,4,3], [1,4,3], [1,2,3], [1,2,4]$ respectively. The edges in the four graphs $G(A_1), G(A_2), G(A_3), G(A_4)$ are:

• $G(A_1)$: $(1,2), (2,3)$. Thus $F(A_1)=2$.
• $G(A_2)$: $(1,2), (2,3)$. Thus $F(A_2)=2$.
• $G(A_3)$: $(1,2), (1,3), (2,3)$. Thus $F(A_3)=1$.
• $G(A_4)$: $(1,2), (1,3), (2,3)$. Thus $F(A_4)=1$.

So $f(a)=[2,2,1,1]$, which matches the input.

The valid $a$ is not unique; for example, $a=[4,3,1,2]$ is also correct.

Input 2

5 1
4
2 2 1 1
1011
0111
1011
1001
1010

Output 2

1 2 4 3

Note 2

The permutation for this example is the same as the first test case in Example 1, but this example includes hints for Subtask 5. Note that when providing $path_j$, the original indices are still used; for example, after removing $1$, the vertices in the new shortest path are $2 \to 3 \to 4$.

Input 3

6 1
4
2 2 1 1
1011

Output 3

1 2 4 3

Note 3

The permutation for this example is the same as the first test case in Example 1, but this example includes hints for Subtask 6.

Constraints

For all data: $1 \le T \le 4 \times 10^4, 4 \le n \le 10^5, \sum n \le 5 \times 10^5$.

• Subtask 1 (7 points): $T \le 250, n \le 7$.
• Subtask 2 (5 points): $b_i = 1$.
• Subtask 3 (10 points): $n \ge 90000$, guaranteed that a solution exists with $a_1=1, a_n=n$.
• Subtask 4 (7 points): $n \ge 90000$, guaranteed that a solution exists with $a_2=1, a_{n-1}=n$.
• Subtask 5 (15 points): $n \le 100, \sum n^3 \le 3 \times 10^6$, hints for all $path_j$ are provided.
• Subtask 6 (15 points): $n \le 100, \sum n^3 \le 3 \times 10^6$, hint for $path_0$ is provided.
• Subtask 7 (15 points): $n=100, T=3$, 5 test cases total, input generated by picking a random $a$ and calculating $f(a)$.
• Subtask 8 (25 points): $n \le 100, \sum n^3 \le 3 \times 10^6$. Depends on subtasks 1, 5, 6, 7.
• Subtask 9 (1 point): No special constraints. Depends on subtasks 1-8.