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}$。 如果有多解，输出任意解。

题目描述

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.

输入输出样例

输入样例 #1

2
0 1 2 3

输出样例 #1

Shi
2 0 1 3 
2 1 3 0 

输入样例 #2

2
0 0 0 0

输出样例 #2

Shi
0 1 2 3 
0 1 2 3 

输入样例 #3

2
0 1 2 2

输出样例 #3

Fou