Folding Machine

One reason a Turing machine computes more than simpler models is its infinite tape, divided into cells that store information.

A Folding machine borrows that idea with two changes. Its tape is finite, every cell holds an integer, and the only operation it performs is folding the tape.

A folding operation works like this. The machine picks a crease, either between two adjacent cells or at one of the two ends of the tape, and folds one side over the other. Cells that come to lie on top of each other are added together, and the folded result becomes the new tape. The new tape has the length of the longer of the two parts.

The crease does not have to be at the middle of the tape. When the folded part is the shorter one, the remaining cells of the longer part keep their values.

A crease at the very start or the very end of the tape leaves every value alone and only reverses the order of the cells.

Science of Bends Company develops commercial versions of the Folding machine, and its production has gone up recently. Part of the last lot does not work correctly, so the machines need more testing before they ship. Selling a defective machine would damage the company's name.

During a test, tapes are fed to a machine and the machine returns a computation result. The engineers in charge wrote down the results, but they forgot to write down which foldings each test used. Rather than test every machine again from scratch, they agreed to accept a test whenever at least one sequence of foldings turns the input tape into the recorded output tape. Given the input tape and the output tape, write a program that decides whether such a sequence exists. Performing no folding at all is allowed, so two tapes that are already equal are accepted.

The input has four lines. The first two lines describe the input tape and the last two lines describe the output tape.

The first line contains one integer $N$, the size of the input tape. The second line contains $N$ integers $v_1, \dots, v_N$, the contents of the input tape. The third line contains one integer $M$, the size of the output tape. The fourth line contains $M$ integers $w_1, \dots, w_M$, the contents of the output tape.

Restrictions

• $1 \le M \le N \le 15$
• $0 \le v_i \le 10^8$ for every $i$ with $1 \le i \le N$
• $0 \le w_j \le 10^8$ for every $j$ with $1 \le j \le M$

Print one line holding a single character. Print S if some sequence of foldings turns the input tape into the output tape, and N otherwise.