404386: GYM101492 C Coprimes

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.

The first line has the numbers N and M separated by a space. The second line contains N positive integers a₁, a₂, ..., a_N 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·10⁴
• 1 ≤ M ≤ 2·10⁵
• 1 ≤ a_i ≤ 5·10⁵, 1 ≤ i ≤ N
• 

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.

5 3
6 15 10 6 7
1 3
2 4
4 5

N
N
S

6 4
39 78 143 26 22 70
2 5
3 6
4 6
1 5

N
S
N
S

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