E. Xor-перестановки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У жабы Михаила есть $$$2^k$$$ целых чисел $$$a_1, a_2, \ldots, a_{2^k}$$$.

Найдите две такие перестановки $$$p$$$ и $$$q$$$ целых чисел $$$0, 1, \ldots, 2^k-1$$$, что $$$a_i$$$ равно $$$p_i \oplus q_i$$$ для всех возможных $$$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$$$) — элементы данного массива.

Выходные данные

Если данный массив не может быть представлен как поэлементный XOR двух перестановок целых чисел $$$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$$$ включительно; $$$p_i \oplus q_i$$$ должно быть равно $$$a_i$$$ для всех $$$i$$$ таких, что $$$1 \leq i \leq 2^k$$$. Если существует несколько возможных решений, вы можете вывести любое.

Примеры
Входные данные
2
0 1 2 3
Выходные данные
Shi
2 0 1 3 
2 1 3 0
Входные данные
2
0 0 0 0
Выходные данные
Shi
0 1 2 3 
0 1 2 3
Входные данные
2
0 1 2 2
Выходные данные
Fou