28a Olimpíada Brasileira de Informática
Submeta sua solução

Subsequência

Você foi contratado pela Agência Extra-Espacial Brasileira, que procura indícios de vida extra-terrestre. Um dos telescópios da Agência, para o espectro ultravioleta, gera uma sequência de valores inteiros positivos que devem ser analisados continuamente. Dadas duas sequências SA e SB, sua primeira missão é determinar se SB é uma subsequência de SA. Uma subsequência de uma dada sequência S é um conjunto de elementos de S que não são necessariamente adjacentes mas que mantêm a mesma ordem em que aparecem em S. Por exemplo, [2], [1,4], [1,2,4] e [1,2,3,4] são subsequências de [1,2,3,4], mas [4,3], [3,4,1] e [1,3,5] não são.

Entrada

A primeira linha contém dois inteiros A e B, o número de elementos das sequências. A segunda linha contém A inteiros Xi, os números da sequência SA. A seguir a entrada contém B inteiros Yi, os números da sequência SB.

Saída

Seu programa deve produzir uma única linha, contendo um único caractere, que deve ser a letra maiúscula `S' se SB é uma subsequência da SA ou a letra maiúscula `N' caso contrário.

Restrições

  • 1 ≤ A ≤ 105
  • 1 ≤ B ≤ A
  • -109 ≤ Xi ≤ 109 para 1 ≤ i ≤ A
  • -109 ≤ Yi ≤ 109 para 1 ≤ i ≤ B

Informações sobre a pontuação

  • A tarefa vale 100 pontos.
  • Para um conjunto de casos de testes valendo 11 pontos, A = B = 2.
  • Para um conjunto de casos de testes valendo outros 33 pontos, os números aparecem no máximo uma vez em cada sequência, A ≤ 100, 1 ≤ Xi ≤ 100 e 1 ≤ Yi ≤ 100.
  • Para um conjunto de casos de testes valendo outros 56 pontos, nenhuma restrição adicional.

Exemplos

Entrada
5 3
1 2 3 4 5
2 3 5
Saída
S
	

 

Entrada
5 4
8 17 8 21 23
8 8 21 22
Saída
N
	

 

PJ P1 P2 PS
Tarefas Programação Nível 1
Promoção
logo sbc
Patrocínio
Apoio
Coordenação