У жабы Пимпла есть массив целых чисел \(a_1, a_2, \ldots, a_n\).
Скажем, что \(y\) достижимо из \(x\), если \(x<y\) и существует такой целочисленный массив \(p\), что \(x = p_1 < p_2 < \ldots < p_k=y\) и \(a_{p_i}\, \&\, a_{p_{i+1}} > 0\) для всех таких целых чисел \(i\), что \(1 \leq i < k\).
Здесь \(\&\) обозначает операцию побитовое И.
Вам дано \(q\) пар индексов, проверьте достижимость для каждой из них.
Выходные данные
Выведите \(q\) строк. В \(i\)-й из них выведите «Shi», если \(y_i\) достижимо из \(x_i\). Иначе выведите «Fou».
Примечание
В первом примере \(a_3 = 0\). Побитовое И с ним всегда будет равно нулю. \(a_2\, \&\, a_4 > 0\), поэтому \(4\) достижима из \(2\), а чтобы дойти от \(1\) до \(4\), вы можете воспользоваться \(p = [1, 2, 4]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
1 3 0 2 1
1 3
2 4
1 4
|
Fou
Shi
Shi
|