Background

The distributed files can be found in the attachment.

Problem Description

Note: In this problem, all sequence indices start from $1$.

What does the robot heartbeats look like when arranged into a graph?

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

Let $A_i$ be the sequence obtained by deleting 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 all distinct elements, let $G(p)$ be an undirected graph with $|p|$ vertices, numbered $1 \sim |p|$. For every pair of positive integers $1 \le i \lt j \le |p|$, if for all $k \in [i,j] \cap \mathbb{Z}$, we have $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 length of the shortest path from vertex $1$ to vertex $|p|$ in $G(p)$, where the length of a path is defined as its 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$, please 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 give you some “hints”. Let $G_0 = G(a)$. Let $path_0$ be the set of vertices visited by some shortest path from $1$ to $n$ in $G_0$. Let $path_j$ be the set of vertices visited by some shortest path from the start vertex to the end vertex in $G(A_j)$ (note: for convenience, the vertex indices in $path_j$ still use the indices from the original graph, see Sample 2). Then little G may additionally tell you all $path_j$ (including $path_0$), or may only tell you $path_0$, or may provide no hints. See the input format for details.

It is guaranteed that the given hints are correct, i.e., there exists a permutation that satisfies all hints.

The distributed files include checker.cpp, which you can use to check whether your output is correct. Usage: ./checker input output output, where input and output are the input file and your output. testlib.h is also provided; please compile the checker with testlib.h placed in the same directory as the checker.

Input Format

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

Then follow $T$ test cases. Each test case is:

• The first line contains one positive integer $n$.
• The second line contains $n$ positive integers $b_1,\dots,b_n$.

In particular,

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

Notes:

1. Even if your program does not need the hints, when $S = 5$ or $S = 6$ you still need to read the array $c$.
2. For the same input $b$, the valid $a$ may not be unique, and thus $c$ may also not be unique. Your output is not required to satisfy the constraints given by our $c$; it will be judged correct as long as it satisfies the constraints of $b$.

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

Output Format

For each test case, output one line with $n$ positive integers: the permutation $a$ you found.

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

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

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

1 2 4 3

6 1
4
2 2 1 1
1011

1 2 4 3

Hint

Explanation of Sample 1

Consider the first test case in the sample. One solution is $a = [1,2,4,3]$. Then $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)$. Therefore $F(A_1) = 2$.
• $G(A_2)$: $(1,2), (2,3)$. Therefore $F(A_2) = 2$.
• $G(A_3)$: $(1,2), (1,3), (2,3)$. Therefore $F(A_3) = 1$.
• $G(A_4)$: $(1,2), (1,3), (2,3)$. Therefore $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.

Explanation of Sample 2

The permutation in this sample is the same as the first test case in Sample 1, but this sample includes the hints for subtask $5$. Note that when giving $path_j$, the original indices are still used. For example, after deleting $1$, the vertices on the new shortest path are numbered $2 \to 3 \to 4$.

Explanation of Sample 3

The permutation in this sample is the same as the first test case in Sample 1, but this sample includes the hints for subtask $6$.

Constraints

For all testdata: $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$, and it is guaranteed that there exists a solution satisfying $a_1 = 1, a_n = n$.
• Subtask 4 ($7$ points): $n \ge 90000$, and it is guaranteed that there exists a solution satisfying $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 a hint for $path_0$.
• Subtask 7 ($15$ points): $n = 100$, $T = 3$, with $5$ test points. The input is generated by picking a random $a$ and then computing $f(a)$ as the input.
• Subtask 8 ($25$ points): $n \le 100$, $\sum n^3 \le 3 \times 10^6$.
• Subtask 9 ($1$ point): No special constraints.

Translated by ChatGPT 5