Problem Description

Note: All sequence indices in this problem start from 1.

What does the heartbeat of a robot, arranged into a graph, look like?

You have an algorithmic competition robot that beats its heart $n$ times per minute, with the intensity of the $i$-th heartbeat being $a_i$. Here, $a_1 \sim a_n$ is exactly 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, numbered from $1$ to $|p|$. For every pair of positive integers $1 \le i < j \le |p|$, if $\forall k \in [i, j] \cap \mathbb{Z}$, $p_k \in [\min(p_i, p_j), \max(p_i, p_j)]$, then there is an edge between vertex $i$ and vertex $j$ in $G(p)$. Let $F(p)$ be the shortest path length from vertex $1$ to vertex $|p|$ in $G(p)$, where the length of a path is defined as the number of edges it contains.

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

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

In some subtasks, the algorithmic competition robot, Little G, will provide some "hints": Let $G_0 = G(a)$, and let $path_0$ be the set of vertices on some shortest path from $1$ to $n$ in $G_0$. Let $path_j$ be the set of vertices on some shortest path from the start to the end in $G(A_j)$ (note that the vertex numbers in $path_j$ still follow the original graph's numbering, see Sample 2 for details). Little G may provide all $path_j$ (including $path_0$), or only $path_0$, or no hints, depending on the subtask.

It is guaranteed that the provided hints are correct, meaning there always exists a permutation that satisfies all hints.

The provided files include checker.cpp, which you can use to check if your output is correct. The usage is ./checker input output output, where input and output are your input and output files, respectively. Also included is testlib.h, which should be placed in the same directory as the checker for compilation.

Input Format

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

Next, $T$ groups of data follow. Each group consists of: 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 group will also include $n+1$ additional lines. The $i$-th line of these $n+1$ lines is a 01 string $c_i$ of length $n$, where $c_{i,j} = [j \in path_{i-1}]$.
2. If $S = 6$, each group will also include a third line containing a 01 string $c$ of length $n$, where $c_i = [i \in path_0]$.

Note:

1. Even if your program does not need the hints, you still need to read the array $c$ when $S = 5$ or $S = 6$.
2. For a given input $b$, there may be multiple valid $a$ sequences, and thus multiple possible $c$ arrays. It is not required that your output matches the given $c$ constraints, as long as it satisfies the $b$ constraints.

Variables on the same line of input are separated by a space.

Output Format

For each test case, output one line containing $n$ positive integers, which is the permutation $a$ you found.

Sample Input and Output

Sample 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

Sample 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

Sample Input #2

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

Sample Output #2

1 2 4 3

Sample Input #3

6 1
4
2 2 1 1
1011

Sample Output #3

1 2 4 3

Notes/Hints

Sample 1 Explanation

Consider the first group of data in the sample. 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.

There are multiple valid $a$ sequences, such as $a = [4, 3, 1, 2]$, which is also correct.

Sample 2 Explanation

This sample's permutation is the same as the first group of data in the first sample, but it includes hints for subtask 5. Note that when providing $path_j$, the vertex numbers still follow the original numbering, e.g., after removing $1$, the new shortest path passes through vertices $2 \to 3 \to 4$.

Sample 3 Explanation

This sample's permutation is the same as the first group of data in the first sample, but it includes hints for subtask 6.

Data Range

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 to exist a solution where $a_1 = 1, a_n = n$.
• Subtask 4 ($7$ points): $n \ge 90000$, guaranteed to exist a solution where $a_2 = 1, a_{n-1} = n$.
• Subtask 5 ($15$ points): $n \le 100, \sum n^3 \le 3 \times 10^6$, with hints for all $path_j$.
• Subtask 6 ($15$ points): $n \le 100, \sum n^3 \le 3 \times 10^6$, with hints for $path_0$.
• Subtask 7 ($15$ points): $n = 100, T = 3$, 5 test points, input generated by randomly selecting an $a$ and then computing $f(a)$.
• Subtask 8 ($25$ points): $n \le 100, \sum n^3 \le 3 \times 10^6$.
• Subtask 9 ($1$ point): No special restrictions.

见题面 Input 部分

见题面 Output 部分