Same word

Time limit2sMemory limit512 MB

Summary

Given two sets of binary words, decide whether some nonempty concatenation of words from the first set equals some nonempty concatenation from the second.

Level: Medium7 of 10
Topics: String, BFS, Graph, Math
Solved: No attempts yet

Problem

You are given two sets of words made of zeros and ones. Decide whether some concatenation of one or more words from the first set equals some concatenation of one or more words from the second set. A word may be used more than once.

For example, if the first set consists of 010 and 11 and the second set consists of 0 and 101, then 01011010 can be built from either set.

010 + 11 + 010 = 01011010 = 0 + 101 + 101 + 0

Input

The input holds several test cases and continues until the end of the file.

The first line of each test case has two integers $N_1$ and $N_2$ , the number of words in the first set and the number of words in the second set. Each of the next $N_1$ lines has one word of the first set, and each of the following $N_2$ lines has one word of the second set.

Constraints

$1 \le N_1, N_2 \le 20$
Every word has at least 1 and at most 40 characters, all of them zeros or ones.

Output

For each test case print one character on its own line. Print S if a concatenation of one or more words from the first set can equal a concatenation of one or more words from the second set, and N otherwise.

Examples2

Example 1

Input

Expected output

S
N
S

Example 2
Input
```
1 1
1
1
1 1
0
1
```
Expected output
```
S
N
```