У жабы Михаила есть \(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\) обозначает операцию побитовое исключающее ИЛИ.
Выходные данные
Если данный массив не может быть представлен как поэлементный 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\). Если существует несколько возможных решений, вы можете вывести любое.