Perfect squares
In the magic universe of square roots (), a number is attractive if it’s a perfect square (1, 4, 9, 16. 25, 36, 49, etc). Perfect squares are the squares of integers (4 is a square of 2, 25 is a square of 5, etc).
Given
n numbers and q queries of the form “How many attractive numbers are there in the range ?”, you are asked to write a program that would answer those questions as quickly as possible.Input
The first line of the input contains two integers -
n the number of elements in the array (1 ≤ n ≤ ) and the number of queries q (1 ≤ q ≤ ). The next line contains
n integers separated by a space, that represent the elements of the array .Each of the next
q lines contains 2 integers Output
The program should print
q lines, each one having the number of attractive numbers in the range .Examples
Input | Output |
6 4
9 5 2 4 16 3
0 5
0 1
1 2
2 5 | 3
1
0
2 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 5 MB