Mirko and Slavko's Hiking Game

Mirko and Slavko love hiking on a mountain that has two kinds of locations: peaks and valleys. When they are at a peak, Slavko chooses which valley to descend to (provided a trail exists) and when they are in a valley, Mirko chooses which peak to climb to. They never visit the same location twice. The game terminates when the current location has no unvisited neighbour. The twist is: if the final location is a peak then Mirko wins, and if it is a valley then Slavko wins.

Assume both players play optimally. For any starting peak, determine the winner. The decision process can be formulated recursively. For a peak P with available moves, since Slavko moves, the outcome is $$\text{Outcome}(P)=\begin{cases} S & \text{if}\ \exists\, v:\,\text{Outcome}(v)=S,\\ M & \text{otherwise}, \end{cases}$$ whereas for a valley V with moves, since Mirko moves, the outcome is $$\text{Outcome}(V)=\begin{cases} M & \text{if}\ \exists\, v:\,\text{Outcome}(v)=M,\\ S & \text{otherwise}. \end{cases}$$ In the base case, if no move is available then the outcome is determined solely by the type of the current location: a peak yields a win for Mirko and a valley yields a win for Slavko.

inputFormat

The first line contains two integers p and q (1 ≤ p, q ≤ 10), representing the number of peaks and valleys respectively.

The next p lines describe the trails from each peak. The i-th of these lines begins with an integer k (0 ≤ k ≤ q), the number of valleys reachable from peak i, followed by k distinct integers (each between 1 and q) indicating the indices (1-indexed) of these valleys.

The next q lines describe the trails from each valley. The j-th of these lines begins with an integer k (0 ≤ k ≤ p), the number of peaks reachable from valley j, followed by k distinct integers (each between 1 and p) indicating the indices (1-indexed) of these peaks.

outputFormat

Output a single line containing p characters separated by spaces. For each initial peak (from 1 to p), output M if Mirko wins when starting at that peak, or S if Slavko wins.

sample

2 2
1 1
1 2
1 2
1 1

S S