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

蟾蜍皮普尔有一个整数数组 $a_1, a_2, \ldots, a_n$。

我们称 $y$ 可从 $x$ 到达，当且仅当 $x \lt y$，且存在一个整数数组 $p$，满足 $x = p_1 \lt p_2 \lt \ldots \lt p_k=y$，并且对所有满足 $1 \leq i \lt k$ 的整数 $i$，均有 $a_{p_i}\, \&\, a_{p_{i+1}} \gt 0$。

此处 $\&$ 表示按位与运算。

你将收到 $q$ 对下标，请对每一对判断其可达性。

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

第一行包含两个整数 $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 \lt y_i \leq n$）。你需要判断 $y_i$ 是否可以从 $x_i$ 到达。

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

输出 $q$ 行。在第 $i$ 行中，如果从 $x_i$ 可以到达 $y_i$，则输出 "Shi"；否则，输出 "Fou"。

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

在第一个例子中，$a_3 = 0$。你无法到达它，因为与它进行按位与运算的结果恒为零。$a_2\, \&\, a_4 \gt 0$，因此可以从 $2$ 到达 $4$；而要从 $1$ 到达 $4$，可以使用路径 $p = [1, 2, 4]$。