CF1168E Xor Permutations

Toad Mikhail 有一个长度为 $2^k$ 的整数数组 $a_1,\dots,a_{2^k}$。 请找到两个 $0,\dots,2^k - 1$ 的排列 $p,q$，使得 $\forall 1 \le i \le 2^k,p_i \oplus q_i = a_i$，或告诉我们无解。 其中 $\oplus$ 表示按位异或运算。

第一行，一个整数 $k\;(2 \le k \le 12)$，表示数组的长度为 $2^k$。 第二行，$2^k$ 个整数 $a_1,\dots,a_{2^k}\;(0 \le a_i < 2^k)$，表示给定的数组。

如果无解，输出「Fou」。 否则，在第一行输出「Shi」。 接下来两行描述符合条件的两个排列。 其中第一行输出 $2^k$ 个整数 $p_1,\dots,p_{2^k}$，第二行输出 $2^k$ 个整数 $q_1,\dots,q_{2^k}$。 如果有多解，输出任意解。