CF1168C.And Reachability

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.

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 $q$ lines. In the $i$ -th of them print "Shi" if $y_i$ is reachable from $x_i$ , otherwise, print "Fou".

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