Problem Statement

Given a sequence $A$ of $N$ numbers, answer the following $Q$ questions.

• In the $i$-th question, you are given integers $L_i$ and $R_i$. Is $A_{L_i} \times A_{L_i+1} \times \dots \times A_{R_i}$ a cubic number?

Here, a positive integer $x$ is said to be a cubic number when there is a positive integer $y$ such that $x=y^3$.

Constraints

• All values in input are integers.
• $1 \le N,Q \le 2 \times 10^5$
• $1 \le A_i \le 10^6$
• $1 \le L_i \le R_i \le N$

Input

Input is given from Standard Input in the following format:

N Q
A_1 A_2 \dots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

Output

Print $Q$ lines. The $i$-th line should contain Yes if, in the $i$-th question, $A_{L_i} \times A_{L_i+1} \times \dots \times A_{R_i}$ is a cubic number, and No otherwise. The checker is case-insensitive; output can be either uppercase or lowercase.