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

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

Note

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

And Reachability

Examples