A12608 | 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](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

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 < 2^k$ ) — the elements of the given array.

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.