C. И-достижимость
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У жабы Пимпла есть массив целых чисел $$$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$$$ пар индексов, проверьте достижимость для каждой из них.

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

В первой строке записаны два целых числа $$$n$$$ и $$$q$$$ ($$$2 \leq n \leq 300\,000$$$, $$$1 \leq q \leq 300\,000$$$) — количество чисел в массиве и количество запросов, на которые вам нужно будет ответить.

Во второй строке записаны $$$n$$$ целых чисел, разделенных пробелами: $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 300\,000$$$) — данный массив.

В следующих $$$q$$$ строках записаны по два целых числа. В $$$i$$$-й из них записаны два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \leq x_i < y_i \leq n$$$). Вам нужно проверить, достижимо ли $$$y_i$$$ из $$$x_i$$$.

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

Выведите $$$q$$$ строк. В $$$i$$$-й из них выведите «Shi», если $$$y_i$$$ достижимо из $$$x_i$$$. Иначе выведите «Fou».

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

В первом примере $$$a_3 = 0$$$. Побитовое И с ним всегда будет равно нулю. $$$a_2\, \&\, a_4 > 0$$$, поэтому $$$4$$$ достижима из $$$2$$$, а чтобы дойти от $$$1$$$ до $$$4$$$, вы можете воспользоваться $$$p = [1, 2, 4]$$$.