Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Is It A Square?

Limits: 1.5s, 256 MB

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?

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.

Samples

InputOutput
6 4
4 1 2 0 -3 -3
1 1
2 3
4 4
5 6
Yes
No
Yes
Yes

Question 1 : Product = 4. It is a square number.

Question 2 : Product = 1 x 2 = 2. It is not a square number.

Question 3 : Product = 0. It is a square number.

Question 4 : Product = (-3) x (-3) = 9. It is a square number.

Author
Discussion
Submit

Login to submit