Maratona de Programação da SBC Brazil
The musical notes are the basic units of Western music. Each note is associated with a frequency. Two notes for which the fundamental frequencies have a ratio of power of 2 (one is half of the other, one is double of the other, etc..) are perceived as very similar. Therefore, any notes with that kind of relationship are given the same name, as described below.
There are twelve basic notes in a sequence of increasing frequency, each note separated from the previous note by the same distance in the musical scale (this distance is called a semitone). Seven of these twelve notes are represented by letters of the alphabet (A, B, C, D, E, F and G). The table below shows the distance, in semitones, between the notes.
A melody can be represented by a sequence of notes. For example,
A A D C# C# D E E E F# A D G# A
is a well known melody. Note however that as the distances between the semitones are always equal, the same melody can be written starting with another note (we say that the melody is in another key):
B B E D# D# E Gb Gb Gb G# B E A# B
Your neighbor is a famous composer who suspects someone has plagiarized one of her songs. She asked your help to write a program that, given the sequence of notes of the melody in her song, and the sequence of notes of a suspicious snippet of melody, determines if the suspicious snippet occurs, in some key, in her song.
The input consists of several test cases. The first line of a test case contains two integers M and T (1 ≤ M ≤ 100000, 1 ≤ T ≤ 10000, T ≤ M ), indicating the number of notes in the song suspected of having been plagiarized and in the suspect snippet. Each of the next two lines contains M and T notes, respectively, indicating the notes of the song and of the suspect snippet.
Notes in each line are separated by one space; each note is one among `A', `B', `C', `D', `E', `F' or `G', possibly followed by an accidental sign: `#' for sharp or `b' for flat.
The last test case is followed by a line containing only two zeros separated by a blank space.
For each test case your program must print a single line containing one character, `S' in case the song has been plagiarized by the text, or `N' in case the song has not been plagiarized by the text.
|Input Sample||Output Sample|