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

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Bit manipulation


Solutions:
import sys, math
from collections import defaultdict as dd, deque
mod = int(1000000000.0) + 7
mod2 = 998244353
yes = 'YES'
no = 'NO'
Yes = 'Yes'
No = 'No'
input = sys.stdin.readline
bits = 19
inf = int(1000000000.0) + 999

def main():

	def solve():
		for bit in range(bits):
			rcnt[bit] = inf
		for i in range(n - 1, -1, -1):
			for bit in range(bits):
				nxt[i][bit] = inf
			for bit in range(bits):
				is_bit_set = a[i] & 1 << bit
				if is_bit_set:
					val = rcnt[bit]
					if val != inf:
						nxt[i][bit] = min(nxt[i][bit], val)
						for b2 in range(bits):
							nxt[i][b2] = min(nxt[i][b2], nxt[val][b2])
					rcnt[bit] = i
	(n, q) = map(int, input().split())
	a = [int(i) for i in input().split()]
	rcnt = [0] * bits
	nxt = [[0] * bits for i in range(n)]
	solve()
	for Q in range(q):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		ans = 0
		for bit in range(bits):
			if a[y] & 1 << bit:
				if nxt[x][bit] <= y:
					ans = 1
					break
		print('Shi' if ans else 'Fou')
TC = 1
if 1:
	main()
else:
	t = Thread(target=main)
	t.start()
	t.join()


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop, heapify
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
from itertools import accumulate
from functools import lru_cache
M = mod = 998244353

def 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))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
(n, q) = li()
queue = [-1] * 20
ans = [[-1] * 20 for i in range(n + 1)]
l = li()
for (i, curr) in enumerate(l):
	for j in range(20):
		if curr >> j & 1:
			for k in range(20):
				ans[i][k] = max(ans[i][k], ans[queue[j]][k])
			ans[i][j] = i
	for j in range(20):
		queue[j] = max(queue[j], ans[i][j])
queries = []
for i in range(q):
	queries.append(li())
for i in range(q):
	(a, b) = queries[i]
	a -= 1
	b -= 1
	currans = 0
	for j in range(20):
		if l[a] >> j & 1 and ans[b][j] >= a:
			currans = 1
			break
	print('Shi' if currans else 'Fou')


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = mod = 10 ** 9 + 7

def 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))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip().split()]

def st():
	return str(input().rstrip())[2:-1]

def val():
	return int(input().rstrip())

def li2():
	return [str(i)[2:-1] for i in input().rstrip().split()]

def li3():
	return [int(i) for i in st()]
he = []
(n, q) = li()
queue = [-1] * 20
ans = [[-1] * 20 for i in range(n + 1)]
l = li()
for (i, curr) in enumerate(l):
	for j in range(20):
		if curr >> j & 1:
			for k in range(20):
				ans[i][k] = max(ans[i][k], ans[queue[j]][k])
			ans[i][j] = i
	for j in range(20):
		queue[j] = max(queue[j], ans[i][j])
queries = []
for i in range(q):
	queries.append(li())
for i in range(q):
	(a, b) = queries[i]
	a -= 1
	b -= 1
	currans = 0
	for j in range(20):
		if l[a] >> j & 1 and ans[b][j] >= a:
			currans = 1
			break
	print('Shi' if currans else 'Fou')