Is It A Square?
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
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.