CF1168E.Xor Permutations

Toad Mikhail has an array of $2^k$ integers $a_1, a_2, \ldots, a_{2^k}$.

Find two permutations $p$ and $q$ of integers $0, 1, \ldots, 2^k-1$, such that $a_i$ is equal to $p_i \oplus q_i$ for all possible $i$, or determine there are no such permutations. Here $\oplus$ denotes the bitwise XOR operation.

蟾蜍米哈伊尔有一个长度为 $2^k$ 的整数数组 $a_1, a_2, \ldots, a_{2^k}$。

请找出两个整数 $0, 1, \ldots, 2^k-1$ 的排列 $p$ 和 $q$，使得对所有可能的 $i$ 均满足 $a_i = p_i \oplus q_i$；若不存在这样的排列，则判定其不存在。此处 $\oplus$ 表示按位异或运算。

The first line contains one integer $k$ ($2 \leq k \leq 12$), denoting that the size of the array is $2^k$.

The next line contains $2^k$ space-separated integers $a_1, a_2, \ldots, a_{2^k}$ ($0 \leq a_i \lt 2^k$) — the elements of the given array.

第一行包含一个整数 $k$（$2 \leq k \leq 12$），表示数组的大小为 $2^k$。

第二行包含 $2^k$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_{2^k}$（$0 \leq a_i \lt 2^k$）—— 给定数组的元素。

If the given array can't be represented as element-wise XOR of two permutations of integers $0, 1, \ldots, 2^k-1$, print "Fou".

Otherwise, print "Shi" in the first line.

The next two lines should contain the description of two suitable permutations. The first of these lines should contain $2^k$ space-separated distinct integers $p_{1}, p_{2}, \ldots, p_{2^k}$, and the second line should contain $2^k$ space-separated distinct integers $q_{1}, q_{2}, \ldots, q_{2^k}$.

All elements of $p$ and $q$ should be between $0$ and $2^k - 1$, inclusive; $p_i \oplus q_i$ should be equal to $a_i$ for all $i$ such that $1 \leq i \leq 2^k$. If there are several possible solutions, you can print any.

如果给定数组无法表示为两个整数排列 $0, 1, \ldots, 2^k-1$ 的按元素异或（XOR），则输出 "Fou"。

否则，在第一行输出 "Shi"。

接下来两行应分别描述两个满足条件的排列。第一行包含 $2^k$ 个以空格分隔的互异整数 $p_{1}, p_{2}, \ldots, p_{2^k}$，第二行包含 $2^k$ 个以空格分隔的互异整数 $q_{1}, q_{2}, \ldots, q_{2^k}$。

$p$ 和 $q$ 的所有元素均应在 $0$ 到 $2^k - 1$（含端点）之间；且对所有满足 $1 \leq i \leq 2^k$ 的 $i$，需满足 $p_i \oplus q_i = a_i$。若存在多种可行解，输出任意一种即可。