Khả năng tới được qua AND

Cho mảng số nguyên $a_1,a_2,\dots ,a_n$.

Ta nói $y$ tới được từ $x$ nếu $x<y$ và tồn tại dãy chỉ số $x=p_1<p_2<\dots <p_k=y$ sao cho $a_{p_i}<mrow><mi>\&</mi></mrow>a_{p_{i+1}}>0$ với mọi $1\le i<k$. Ở đây $\&$ là phép AND bit.

Cho $q$ truy vấn, mỗi truy vấn gồm cặp chỉ số $(x,y)$. Với mỗi truy vấn, hãy kiểm tra xem $y$ có tới được từ $x$ hay không.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$ $(2\le n\le 3·{10}^5,1\le q\le 3·{10}^5)$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ $(0\le a_i\le 3·{10}^5)$.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x$ và $y$ $(1\le x<y\le n)$.

Dữ liệu ra

In ra $q$ dòng. Trên dòng thứ $i$, in Shi nếu $y_i$ tới được từ $x_i$, ngược lại in Fou.

Ràng buộc

• $2\le n\le 3·{10}^5$
• $1\le q\le 3·{10}^5$
• $0\le a_i\le 3·{10}^5$
• $1\le x_i<y_i\le n$

Ví dụ