C. Coprimes
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A. Tuttu (a distant relative of W. Tutte) is a young mathematician with a promising future. As a child, he was very lonely, since he had no siblings nor cousins. One of his earliest Christmas gifts was a Number Theory book. That is the reason he focused on studying this area since a very early age. He was very interested in coprimes, but he could not solve the following problem and he asked you to help him.

Given a sequence of N positive integers, we want to answer M queries. Each query is represented by two indices. He would like to know if there exists a pair of relatively prime numbers in the sequence whose positions are between the given indices.

Input

The first line has the numbers N and M separated by a space. The second line contains N positive integers a1, a2, ..., aN separated by a space. Then there are M lines, each one containing two integers, and r, separated by a space, encoding a query.

  • 2 ≤ N ≤ 5·104
  • 1 ≤ M ≤ 2·105
  • 1 ≤ ai ≤ 5·105, 1 ≤ i ≤ N
Output

For each one of the queries you should print "S" (without the double quotes) if there is a pair of relatively prime integers between (including) the sequence positions indexed by and r, or "N" otherwise.

Examples
Input
5 3
6 15 10 6 7
1 3
2 4
4 5
Output
N
N
S
Input
6 4
39 78 143 26 22 70
2 5
3 6
4 6
1 5
Output
N
S
N
S
Note

Two numbers are called coprime (or relatively prime) if their greatest common divisor is the number 1.