{"raw_statement":[{"iden":"background","content":"下发文件见附件。"},{"iden":"statement","content":"注：本题中所有序列下标均从 1 开始。\n\n机器人心脏的跳动，排列成图是什么样的？\n\n你有一个算法竞赛机器人，每分钟心跳 $n$ 次，第 $i$ 次心跳的强度为 $a_i$。这里，$a_1\\sim a_n$ 恰为 $1\\sim n$ 的一个排列。\n\n设 $A_i$ 为序列 $a$ 删除第 $i$ 个元素后得到的序列，即 $A_i=[a_1,\\dots,a_{i-1},a_{i+1},\\dots,a_n]$。\n\n对于元素互不相同的序列 $p$，设 $G(p)$ 为一个无向图，有 $|p|$ 个点，编号为 $1\\sim |p|$。对于每对正整数 $1\\le i\\lt j\\le |p|$，若 $\\forall k\\in [i,j]\\cap \\mathbb{Z}$，都有 $p_k\\in [\\min(p_i,p_j),\\max(p_i,p_j)]$，则 $G(p)$ 中 $i$ 号点和 $j$ 号点有一条边。设 $F(p)$ 为 $G(p)$ 中 $1$ 号点到 $|p|$ 号点的最短路长度，这里一条路径长度定义为其边数。\n\n设 $f(a)=[F(A_1),F(A_2),\\dots,F(A_n)]$。\n\n给定长度为 $n$ 的序列 $[b_1,\\dots,b_n]$，请你求出任意一个 $1\\sim n$ 的排列 $a$，使得 $f(a)=b$。**保证有解。**\n\n在某些子任务中，算法竞赛机器人小 G 会给你一些“提示”：设 $G_0=G(a)$，设 $path_0$ 为 $G_0$ 中某条 $1$ 到 $n$ 的最短路经过的点构成的集合，设 $path_j$ 为 $G(A_j)$ 中某条起始点到结束点的最短路经过的点构成的集合（注意，为了方便，这里给出的 $path_j$ 中点的编号仍然沿用原图中点的编号，参见样例 2）。则小 G 有可能会额外告诉你所有 $path_j$（包括 $path_0$），也有可能只告诉你 $path_0$，也有可能不给你提示，详见输入格式。\n\n保证给出的提示是正确的，也即一定存在一个满足所有提示的排列。\n\n下发文件中有 `checker.cpp`，你可以用它来检查自己的输出是否正确。用法是 `./checker input output output`，`input` 和 `output` 分别为输入文件和你的输出。同时还下发了 `testlib.h`，请将其和 checker 置于同一目录下来编译 checker。"},{"iden":"input","content":"第一行两个正整数，为子任务编号 $S$ 以及数据组数 $T$。\n\n接下来 $T$ 组数据，每组数据格式为：第一行一个正整数 $n$，第二行 $n$ 个正整数 $b_1,\\dots,b_n$。\n\n**特别地，**\n\n1. 若 $S=5$，每组数据还会输入 $n+1$ 行，这 $n+1$ 行里第 $i$ 行是一个长度为 $n$ 的 01 串 $c_i$，$c_{i,j}=[j\\in path_{i-1}]$。\n2. 若 $S=6$，每组数据还会输入第三行，包含一个长度为 $n$ 的 01 串 $c$，$c_i=[i\\in path_0]$。\n\n注意：\n\n1. 即使你的程序不需要用到提示，在 $S=5$ 或 $S=6$ 时你仍然需要读入数组 $c$。\n2. 对于一种输入的 $b$，符合条件的 $a$ 可能不唯一，进而 $c$ 可能也不唯一。**不要求**你的输出符合我们给出的 $c$ 的限制，只要符合 $b$ 的限制即视为正确。\n\n同一行输入的不同变量用一个空格隔开。"},{"iden":"output","content":"对于每组数据输出一行 $n$ 个正整数，为你求出的排列 $a$。"},{"iden":"note","content":"**样例 1 解释**\n\n考虑样例中的第一组数据。一组解是 $a=[1,2,4,3]$。$A_1,A_2,A_3,A_4$ 分别为 $[2,4,3],[1,4,3],[1,2,3],[1,2,4]$。$G(A_1),G(A_2),G(A_3),G(A_4)$ 四个图中的边分别为：\n\n- $G(A_1)$：$(1,2),(2,3)$。因此 $F(A_1)=2$。\n- $G(A_2)$：$(1,2),(2,3)$。因此 $F(A_2)=2$。\n- $G(A_3)$：$(1,2),(1,3),(2,3)$。因此 $F(A_3)=1$。\n- $G(A_4)$：$(1,2),(1,3),(2,3)$。因此 $F(A_4)=1$。\n\n所以 $f(a)=[2,2,1,1]$，符合输入。\n\n符合输入的 $a$ 不唯一，比如 $a=[4,3,1,2]$ 也是正确的。\n\n**样例 2 解释**\n\n该样例的排列和第一个样例中第一组数据是相同的，但本样例存在子任务 5 的提示。注意在给出 $path_j$ 时仍然沿用原编号，例如删去 $1$ 后，新的最短路经过的点编号为 $2\\to 3\\to 4$。\n\n**样例 3 解释**\n\n该样例的排列和第一个样例中第一组数据是相同的，但本样例存在子任务 6 的提示。\n\n**数据范围**\n\n对于所有数据：$1\\le T\\le 4\\times 10^4,4\\le n\\le 10^5,\\sum n\\le 5\\times 10^5$。\n\n- 子任务 1（$7$ 分）$T\\le 250,n\\le 7$。\n- 子任务 2（$5$ 分）$b_i=1$。\n- 子任务 3（$10$ 分）$n\\ge 90000$，保证存在一组解满足 $a_1=1,a_n=n$。\n- 子任务 4（$7$ 分）$n\\ge 90000$，保证存在一组解满足 $a_2=1,a_{n-1}=n$。\n- 子任务 5（$15$ 分）$n\\le 100,\\sum n^3\\le 3\\times 10^6$，存在所有 $path_j$ 的提示。\n- 子任务 6（$15$ 分）$n\\le 100,\\sum n^3\\le 3\\times 10^6$，存在 $path_0$ 的提示。\n- 子任务 7（$15$ 分）$n=100,T=3$，共 5 个测试点，输入生成方式是随机一个 $a$ 再求出 $f(a)$ 作为输入。\n- 子任务 8（$25$ 分）$n\\le 100,\\sum n^3\\le 3\\times 10^6$。\n- 子任务 9（$1$ 分）无特殊限制。"}],"translated_statement":null,"sample_group":[["9 11\n4\n2 2 1 1\n4\n2 2 2 2\n4\n2 1 1 2\n7\n5 5 4 4 4 5 5\n7\n1 3 2 2 2 2 4\n7\n3 3 2 4 4 5 3\n8\n2 2 3 5 3 3 3 4\n8\n5 4 4 4 4 6 6 5\n8\n4 4 4 2 4 4 2 3\n9\n4 7 5 5 5 5 3 4 4\n9\n3 4 4 4 4 4 4 4 6","1 2 4 3\n2 1 4 3\n1 3 2 4\n3 1 7 2 6 4 5\n3 1 6 4 2 5 7\n2 3 1 6 4 7 5\n5 6 3 1 7 4 2 8\n1 8 2 7 3 5 6 4\n6 3 2 7 4 5 1 8\n5 8 6 3 7 1 9 2 4\n2 9 3 1 8 5 7 6 4"],["5 1\n4\n2 2 1 1\n1011\n0111\n1011\n1001\n1010","1 2 4 3"],["6 1\n4\n2 2 1 1\n1011","1 2 4 3"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}