Музичний плагіат
Музичні ноти є основними одиницями західної музики. Кожна нота асоціюється з певною частотою. Дві ноти, частоти яких мають відношення ступеня 2 (одна є половиною іншої, одна є подвійною іншої тощо), сприймаються як дуже схожі. Тому ноти з таким відношенням отримують однакову назву, як описано нижче.
Існує дванадцять основних нот у послідовності зростаючої частоти, кожна з яких відокремлена від попередньої однаковою відстанню в музичній шкалі (ця відстань називається півтоном). Сім з цих дванадцяти нот позначаються літерами алфавіту (A, B, C, D, E, F та G). Таблиця нижче показує відстань у півтонах між нотами.
Зверніть увагу, що існує п'ять нот, які не представлені літерами алфавіту: ноти між A та B, між C та D, між D та E, між F та G та між G та A.
Ноти можуть бути змінені двома знаками альтерації, які називаються диез і бемоль, що позначаються відповідно символами '#' та 'b'. Диез підвищує ноту на півтон, бемоль знижує ноту на півтон. Нота зі знаком альтерації позначається назвою ноти, за якою слідує символ альтерації. Зверніть увагу, що за цією схемою ми можемо представити всі дванадцять нот.
Нижче наведено ілюстрацію назв нот відповідно до описаної схеми, на фрагменті клавіатури піаніно.
Мелодія може бути представлена послідовністю нот. Наприклад,
A A D C# C# D E E E F# A D G# A
є добре відомою мелодією. Однак зауважте, що оскільки відстані між півтонами завжди рівні, ту ж мелодію можна записати, починаючи з іншої ноти (ми кажемо, що мелодія в іншій тональності):
B B E D# D# E Gb Gb Gb G# B E A# B
Ваш сусід є відомим композитором, який підозрює, що хтось плагіатував одну з її пісень. Вона попросила вас допомогти написати програму, яка, отримавши послідовність нот мелодії в її пісні та послідовність нот підозрілого уривка мелодії, визначає, чи підозрілий уривок зустрічається, в якійсь тональності, в її пісні.
Вхідні дані
Вхід складається з кількох тестових випадків. Перша строка тестового випадку містить два цілі числа M та T (1 ≤ M ≤ 10^5, 1 ≤ T ≤ 10^4, T ≤ M), що вказують на кількість нот у пісні, підозрюваній у плагіаті, та в підозрілому уривку. Кожна з наступних двох строк містить M та T нот відповідно, що вказують на ноти пісні та підозрілого уривка.
Ноти в кожній строкі розділені одним пробілом; кожна нота є однією з 'A', 'B', 'C', 'D', 'E', 'F' або 'G', можливо, з наступним знаком альтерації: '#' для диеза або 'b' для бемоля.
Останній тестовий випадок супроводжується строкою, що містить лише два нулі, розділені пробілом.
Вихідні дані
Для кожного тестового випадку ваша програма повинна вивести одну строку, що містить один символ, 'S' у випадку, якщо пісня була плагіатована текстом, або 'N' у випадку, якщо пісня не була плагіатована текстом.