Toad Pimple has an array of integers $a_1, a_2, \ldots, a_n$.

We say that $y$ is reachable from $x$ if $x<y$ and there exists an integer array $p$ such that $x = p_1 < p_2 < \ldots < p_k=y$, and $a_{p_i}\, \&\, a_{p_{i+1}} > 0$ for all integers $i$ such that $1 \leq i < k$.

Here $\&$ denotes the bitwise AND operation.

You are given $q$ pairs of indices, check reachability for each of them.


-----Input-----

The first line contains two integers $n$ and $q$ ($2 \leq n \leq 300\,000$, $1 \leq q \leq 300\,000$) — the number of integers in the array and the number of queries you need to answer.

The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 300\,000$) — the given array.

The next $q$ lines contain two integers each. The $i$-th of them contains two space-separated integers $x_i$ and $y_i$ ($1 \leq x_i < y_i \leq n$). You need to check if $y_i$ is reachable from $x_i$. 


-----Output-----

Output $q$ lines. In the $i$-th of them print "Shi" if $y_i$ is reachable from $x_i$, otherwise, print "Fou".


-----Example-----
Input
5 3
1 3 0 2 1
1 3
2 4
1 4

Output
Fou
Shi
Shi



-----Note-----

In the first example, $a_3 = 0$. You can't reach it, because AND with it is always zero. $a_2\, \&\, a_4 > 0$, so $4$ is reachable from $2$, and to go from $1$ to $4$ you can use $p = [1, 2, 4]$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "from bisect import bisect_left as bl\nfrom bisect import bisect_right as br\nfrom heapq import heappush,heappop,heapify\nimport math\nfrom collections import *\nfrom functools import reduce,cmp_to_key\nimport sys\ninput = sys.stdin.readline\n\nfrom itertools import accumulate\nfrom functools import lru_cache\n\nM = mod = 998244353\ndef factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))\ndef inv_mod(n):return pow(n, mod - 2, mod)\n \ndef li():return [int(i) for i in input().rstrip('\\n').split()]\ndef st():return input().rstrip('\\n')\ndef val():return int(input().rstrip('\\n'))\ndef li2():return [i for i in input().rstrip('\\n')]\ndef li3():return [int(i) for i in input().rstrip('\\n')]\n\n\n\n\nn, q = li()\n\n\nqueue = [-1] * 20\n\nans = [[-1] * 20 for i in range(n + 1)]\nl = li()\nfor i, curr in enumerate(l):\n\n    for j in range(20):\n        if curr >> j & 1:\n            for k in range(20):        \n                ans[i][k] = max(ans[i][k], ans[queue[j]][k])\n            ans[i][j] = i\n    \n    for j in range(20):queue[j] = max(queue[j], ans[i][j])\n\n\nqueries = []\nfor i in range(q):queries.append(li())    \nfor i in range(q):\n    a, b = queries[i]\n    a -= 1\n    b -= 1\n\n    currans = 0\n\n    for j in range(20):\n        if (l[a] >> j) & 1 and ans[b][j] >= a:\n            currans = 1\n            break\n    print('Shi' if currans else 'Fou')"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 15767