And Reachability

3000ms

262144K

Description:

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".

Sample Input:

Sample 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]$$$.

Informação

Provedor Codeforces

Código CF1168C