Toad Mikhail 有一个 $$$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$$$表示按位异或运算。
输入
第一行包含一个整数$$$k$$$ ($$$2 \leq k \leq 12$$$),表示数组的大小为$$$2^k$$$。
下一行包含 $$$2^k$$$ 空格分隔的整数 $$$a_1, a_2, \ldots, a_{2^k}$$$ ($$$0 \leq a_i < 2^k$$$) - 给定数组的元素。
输出
如果给定数组无法表示为整数 $$$0, 1, \ldots, 2^k-1$$$ 的两个排列的按元素异或,则打印“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$$$ 之间(含);对于所有$$$i$$$,$$$p_i \oplus q_i$$$ 应等于$$$a_i$$$,使得$$$1 \leq i \leq 2^k$$$。如果有多种可能的解决方案,您可以打印任何一个。
示例
输入 #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