Espionagem

---

Descrição

Após a divulgação das denúncias feitas pelo analista de sistemas Edward Snowden, ex-funcionário da CIA e da NSA, sobre o programa de espionagem do governo estadunidense, o governo brasileiro resolveu se movimentar e investir em segurança digital e um programa de espionagem próprio.

Entre os primeiros objetivos do programa está o reconhecimento do possível conteúdo de um conjunto de dados criptografados obtidos pelo governo. Os alvos da investigação, que não podem ser citados no enunciado por questões de segurança dos elaboradores da prova, usaram uma estratégia para dificultar a espionagem:

As mensagens trocadas por eles eram escritas em fitas circulares – de tal forma que o final da mensagem estava diretamente conectado ao início dela;

O conteúdo da mensagem foi criptografado com a Cifra de César (não é o de Sorocaba), um tipo de criptografia de substituição na qual cada letra do texto original é substituída por outra, que se apresenta C posições à frente desta – o número C é conhecido como chave. Assim, por exemplo, caso seja adotada uma chave igual a três (C=3), as ocorrências de ‘A’ no texto serão substituídas por ‘D’, as de ‘B’ serão substituídas por ‘E’, e assim por diant e (ver Figura 1).



Desta forma, uma frase como “O PROBLEMA C DA MARATONA” seria lida como “R SUREOHPD F GD PDUDWRQD”, caso a chave C fosse igual a 3 e, por sorte, a mensagem criptografada fosse lida a partir da posição correta da fita. Porém, se a fita fosse lida a partir de outra posição, como a partir da posição 10, o conteúdo dela seria “D F GD PDUDWRQDR SUREOHP”.

Um erro cometido pelos alvos da investigação foi que eles usaram nas mensagens apenas letras maiúsculas e espaços (e os espaços não foram criptografados), facilitando a identificação do possível conteúdo da mensagem.

Você foi contratado pela ABIN para, dada uma frase procurada e uma lista de mensagens criptografadas, definir se alguma delas pode conter a frase. É importante notar que você não sabe a partir de que posição a fita foi lida para gerar a mensagem criptografa em questão e nem sabe a chave que foi utilizada para criptografá-la.

---

Entrada

A entrada é composta por vários casos de teste. A primeira linha de cada caso de teste contém uma frase que deve ser buscada pelo algoritmo com, no máximo, 100 caracteres (entre letras maiúsculas e espaços). A próxima linha contém um número inteiro N (0 < N < 100) com o número de mensagens criptografadas onde a frase deverá ser procurada. As N linhas seguintes contém uma mensagem criptografada cada com, no máximo, 100 caracteres (entre letras maiúsculas e espaços).

---

Saída

Para cada caso de teste, você deve imprimir um caractere 'S', sem aspas e maiúsculo, caso alguma das mensagens criptografadas puder conter a frase procurada. Imprima um caractere 'N', sem aspas e maiúsculo, caso contrário.

Exemplos de Entrada	Exemplos de Saída
Copiar! O PROBLEMA C DA MARATONA 3 P QSPCSFNB D EP NBSBEPOB T UWTGWJRF H IF RFWFYTSF D F GD PDUDWRQDR SUREOHP MARATONA 3 P QSPCSFNB D EP NBSBEPOB T UWTGWJRF H IF RFWFYTSF D F GD PDUDWRQDR SUREOHP	Copiar! S S