题意极其复杂。
原题的示例为 \(3\)-Benes 网络，我们不妨自己动手，画出一个 \(4\)-Benes 网络。
由题意，中间的两个大长方形对应两个 \(3\)-Benes 网络。
根据上图，容易看出左边的 \(3\)-Benes 网络对应了 \(4\)-Benes 网络中的偶数位，右边的 \(3\)-Benes 网络对应了 \(4\)-Benes 网络中的奇数位。
接下来考虑说明如下事实：对于任意的输出序列，总能构造出对应的 \(n\)-Benes 网络。
对于 \(n=1\) 的情况，显然在关闭开关时的输出为 \([0,1]\)，打开开关时的输出为 \([1,0]\)，恰好对应 \(0\) 和 \(1\) 的两种排列方式。
接下来归纳论证，假设我们已经论证了 \(n = n_0 - 1\) 时命题成立，考虑如何论证 \(n = n_0\) 时命题成立。
不妨从 \(0\) 和 \(1\) 两个数入手，进而推广到所有数。
初始时，我们可以通过开关交换 \(0\) 和 \(1\) 的位置，经过一轮传输后，\(0\) 和 \(1\) 必然位于不同的 \((n-1)\)-Benes 网络。
由于 \((n-1)\)-Benes 网络可以将数任意排列，且 \((n-1)\)-Benes 网络可以到达最后一行所有的开关处，将 \(0\) 和 \(1\) 分别连向对应的开关即可。
然而这样做会有问题。考虑一个下方的开关对应的两个数在同一个 \((n-1)\)-Benes 网络里，这样我们就无法让他们到达同一个开关处。
我们考虑对于下方的每个开关，其对应的两个数连边，说明其不能在同一个 \((n-1)\)-Benes 网络里，对于上方的每个开关，也是同理。
我们只需要证明其可以进行二分图染色即可，染色方法对应了每个数被分到两个 \((n-1)\)-Benes 网络中的其中一个。
考虑反证法，若不能进行二分图染色，则原图存在奇环。我们考虑奇环中必然存在两条相邻的边，同时属于上方或下方。
而我们知道，上方的每条边互不相交，下方也是同理的，所以原图不存在奇环，进而可以将其看作二分图。
也就是说，我们能够将每个数分配到两个 \((n-1)\)-Benes 网络中的一个，进而我们就可以构造出合法的方案。
考虑如何处理字典序最小的限制。
我们不妨从前往后处理，对于每一个开关，我们考虑其是否打开。这样操作相当于钦定了一些点的颜色，由此我们进行二分图染色判定即可。
到这里就做完了，精细实现可以做到 \(O(Tn2^n)\)。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=13;
char ans[2*N-1][1<<N-1];
int col[1<<N],tmp[1<<N],block[1<<N],tot_block;
bool vis[1<<N];
vector<int> G[1<<N];
void dfs(int u,int pre_color){tmp[u]=pre_color;block[u]=tot_block; for(int i=0;i<G[u].size();i++){int v=G[u][i];if(tmp[v]==-1){dfs(v,1-pre_color);}}
}
bool flag1[1<<N],flag2[1<<N];
void check(vector<int> V){for(int i=0;i<V.size();i++){tmp[V[i]]=-1;}tot_block=0;for(int i=0;i<V.size();i++){if(tmp[V[i]]==-1){tot_block++;flag1[tot_block]=false;flag2[tot_block]=false;dfs(V[i],0);}}
}
void solve(int id_l,int id_r,int pos_l,int pos_r,vector<int> s,vector<int> t){if(id_l==id_r){if(s[0]==t[0] && s[1]==t[1]){ans[id_l][pos_l]='0';}else{ans[id_l][pos_l]='1';}return ;}vector<int> l_s,l_t;vector<int> r_s,r_t;for(int i=0;i<pos_r-pos_l;i++){col[s[i*2]]=-1;col[s[i*2+1]]=-1;G[s[i*2]].clear();G[s[i*2+1]].clear();}for(int i=0;i<pos_r-pos_l;i++){G[s[i*2]].push_back(s[i*2+1]);G[s[i*2+1]].push_back(s[i*2]);}for(int i=0;i<pos_r-pos_l;i++){G[t[i*2]].push_back(t[i*2+1]);G[t[i*2+1]].push_back(t[i*2]);}check(s);for(int i=0;i<pos_r-pos_l;i++){ans[id_l][i+pos_l]='0';col[s[i*2]]=0;col[s[i*2+1]]=1;bool tmp1=flag1[block[s[i*2]]],tmp2=flag2[block[s[i*2]]];if(col[s[i*2]]==tmp[s[i*2]]){tmp1=true;} else{tmp2=true;}if(tmp1 && tmp2){ans[id_l][i+pos_l]='1';col[s[i*2]]=1;col[s[i*2+1]]=0;if(col[s[i*2]]==tmp[s[i*2]]){flag1[block[s[i*2]]]=true;}else{flag2[block[s[i*2]]]=true;}l_s.push_back(s[i*2+1]);r_s.push_back(s[i*2]);}else{if(col[s[i*2]]==tmp[s[i*2]]){flag1[block[s[i*2]]]=true;}else{flag2[block[s[i*2]]]=true;}l_s.push_back(s[i*2]);r_s.push_back(s[i*2+1]);}}for(int i=0;i<pos_r-pos_l;i++){if(col[t[i*2]]==0 && col[t[i*2+1]]==1){ans[id_r][i+pos_l]='0';l_t.push_back(t[i*2]);r_t.push_back(t[i*2+1]);}else{ans[id_r][i+pos_l]='1';l_t.push_back(t[i*2+1]);r_t.push_back(t[i*2]);}}solve(id_l+1,id_r-1,pos_l,(pos_l+pos_r)>>1,l_s,l_t);solve(id_l+1,id_r-1,(pos_l+pos_r)>>1,pos_r,r_s,r_t);
}
int main(){int n;while(~scanf("%d",&n) && n){vector<int> s,t;for(int i=0;i<(1<<n);i++){s.push_back(i);int num;scanf("%d",&num);t.push_back(num);}solve(0,2*n-2,0,1<<n-1,s,t);for(int i=0;i<=2*n-2;i++){for(int j=0;j<(1<<n-1);j++){printf("%c",ans[i][j]);}printf("\n");}printf("\n");}return 0;
}