Shikamaru is the most brilliant student of his class. He is very good at Mathematics. Mr. Asuma is their math teacher. Today he taught the class about square numbers. A square number is a non-negative integer which is the product of some integer with itself. For example, 0, 1, 4, 9, 16, 25 are square numbers, but 2, 3, 5, 6 are not. Mr. Asuma wanted to test whether his students can identify square numbers or not. So he gave them a homework.

He gave them an array A[ consisting of n integers and asked q questions. In each question, he gave them two integers l and r which denotes two positions of the array. The students have to tell whether the product of all the integers between the two positions (l and r inclusive) is a square number or not. In other words, they have to compute the value of P represented as the following:

$P = \prod\limits_{i=l}^r A_i$

And check whether it is a square or not. The array follows 1-based indexing.

After returning home, Shikamaru started doing his homework. He was able to answer some of the questions correctly, but later some of the products P became so huge and he could not identify whether they are square or not. Can you help Shikamaru doing his homework?

Input

The first line contains two integers n (1 ≤ n ≤ 105) and q (1 ≤ q ≤ 105). The second line contains n integers A1, A2, ... , An ( -105 ≤ Ai ≤ 105 ). Each of the next q lines contains two integers l and r (1 ≤ l ≤ r ≤ n).

Output

For each question print "Yes" if the product is a square, otherwise print "No" in a separate line.

Sample

Input

Output

6 4
4 1 2 0 -3 -3
1 1
2 3
4 4
5 6

Yes
No
Yes
Yes

For the first input, the product is 4. It is a square number.

For the second input, the product is 1×2 = 2. It is not a square number.

For the third input, the product is 0. It is a square number.

For the fourth input, the product is (-3)×(-3) = 9. It is a square number.