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:
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?
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).
For each question print "Yes" if the product is a square, otherwise print "No" in a separate line.
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.