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](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.