# 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?

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 ≤ 10 ^{5})** and

**q (1 ≤ q ≤ 10**.

^{5})The second line contains

**n**integers

**A**.

_{1}, A_{2}, … , A_{n}( -10^{5}≤ A_{i}≤ 10^{5})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

Input | Output |
---|---|

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.

#### fsshakkhor

→

Login to submit