URI Online Judge | 1718

Grandpa Pepe's Pizza

By Ricardo Anido BR Brazil

Timelimit: 1

Grandpa Pepe is famous for his pizzas. They are delicious, and have the format of a perfect circle. Grandpa prepared a special pizza for tonight’s dinner, and put a certain number of olives randomly distributed on the pizza, but all of them exactly on the pizza’s border.

Your problem is to determine, knowing the pizza’s circumference, the number of olives and the position of each olive, if it is possible to divide the pizza in circular sectors of exactly the same size, such that each piece contains exactly one olive.

The figure below shows (a) a pizza of circumference 12 with 3 olives and a possible division in equal sized pieces; and (b) a pizza of circumference 12 with 4 olives that cannot be divided in equal parts as described above. Despite being tasty, the olives are very small, and their dimensions can be disregarded when computing the division.


The input contains several test cases. The first line of a test case contains two integers C (3C105 ) and N (3N104 , NC) indicating respectively the circumference of the pizza and the number of olives. The integer C is multiple of N . The second line contains N distinct integers Xi (0X1 < X2 < . . . < XN < C), in increasing order, describing the positions of the olives, given as the length of the circular arc, clockwise, from a fixed point in the circumference.


For each test case in the input your program must produce a single line, containing a single letter, which must be S if it is possible to divide the pizza as described above, or N otherwise.

Sample Input Sample Output

12 3

2 8 11