13644번 - Palavras 다국어

Dados dois conjuntos de palavras formadas por zeros e uns, você deve escrever um programa para determinar se existem concatenações de palavras de cada um dos conjuntos que gerem uma mesma palavra. Por exemplo, se um conjunto A contém as palavras 010 e 11 e outro conjunto B contém as palavras 0 e 101, então a palavra 01011010 pode ser formada tanto por contatenações de palavras de A como por contatenações de palavras de B:

010 · 11 · 010 = 01011010 = 0 · 101 · 101 · 0

A primeira linha de um caso de teste contém dois inteiros, N₁ e N₂, que indicam respectivamente o número de palavras do primeiro e do segundo conjunto de palavras. Cada uma das N₁ linhas seguintes contém uma palavra do primeiro conjunto. Cada uma das N₂ linhas seguintes contém uma palavra do segundo conjunto.

Restrições

• 1 ≤ N₁, N₂ ≤ 20
• cada palavra tem no mínimo um caractere e no máximo 40 caracteres, todos zeros e uns.

Para cada caso de teste seu programa deve imprimir uma única linha, contendo um único caractere. Se for possivel encontrar uma concatenação de uma ou mais palavras do primeiro conjunto que seja igual a uma concatenação de uma ou mais palavras do segundo conjunto então o caractere deve ser S, caso contrário deve ser N.