Huy là một nhà toán học đại tài, được giao nhiệm vụ nghiên cứu về chủ đề số chính phương. Số chính phương là số nguyên có thể biểu diễn dưới dạng bình phương của một số nguyên (ví dụ như ~1, 4, 9, 16, 25, \dots~ là các số chính phương, nhưng ~17~ thì không phải số chính phương).

Vào một ngày đẹp trời, bạn thân của Huy là Chương hỏi Huy về một bài toán liên quan đến dãy số, và cũng liên quan đến chủ đề số chính phương mà Huy đang nghiên cứu, bài toán được mô tả như sau:

Cho một dãy ~N~ số nguyên dương ~a[1], a[2], a[3], \dots, a[N]~. Hàm ~F(x, y)~ được định nghĩa là tích của các phần tử từ vị trí ~x~ đến vị trí ~y~, cụ thể hơn ~F(x, y) = a[x] \times a[x + 1] \times \dots \times a[y]~. Có ~Q~ câu hỏi cần phải trả lời, câu hỏi thứ ~i~ gồm hai số nguyên dương ~L_i, R_i~ (~1 \le L_i \le R_i \le N~). Với câu hỏi thứ ~i~, in ra xâu kí tự “YES” nếu ~F(L_i, R_i)~ là số chính phương, ngược lại in ra xâu kí tự “NO”.

Yêu cầu: Hãy giúp Huy giải bài toán này.

Input

• Dòng đầu tiên là hai số nguyên dương ~N~ và ~Q~ (~1 \le N, Q \le 70000~).
• Dòng thứ hai gồm ~N~ số nguyên dương ~a[1], a[2], a[3], \dots, a[N]~ (~1 \le a[i] \le 70000~).
• Dòng thứ ~i~ trong ~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~L_i~ và ~R_i~ (~1 \le L_i \le R_i \le N~).

Output

• Gồm ~Q~ dòng, dòng thứ ~i~ là xâu kí tự “YES” nếu ~F(L_i, R_i)~ là số chính phương, ngược lại in ra xâu kí tự “NO”.