There are cards for each of spades, clovers, diamonds, and hearts, and there are cards with numbers to for each mark. For example, "1" of spade, "1" of clover, "1" of diamond, and "1" of heart are represented by "S1", "C1", "D1", and "H1", respectively. Initially, the cards are arranged in the order of .

"Shuffle" according to 'Q' queries. Specifically, in the -th query, do the following:

and are given. Bring all the cards from card to card to the beginning while keeping their order. That is, when in the sequence of the card, the sequence is changed to .

Process queries in order, and Output the subsequence consisting only of all spade cards, the subsequence consisting only of all clover cards, the subsequence consisting only of all diamond cards, and the subsequence consisting only of all heart cards in this order.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Constraints

Input

and are kinds of character strings that can be made by arranging one character of "S" or "C" or "D" or "H" and the number respectively.

Output

Output the subsequence consisting only of spade cards, the subsequence consisting only of clover cards, the subsequence consisting only of diamond cards, and the subsequence consisting only of heart cards in this order in 4 rows.

Sample

Sample Input 1

1 2
C1 D1
D1 S1

Sample Output 1

S1
C1
D1
H1

The initial sequence is .
By the first query, ~ goes to the beginning, so it is changed to .
By the second query, ~ goes to the beginning, so it is changed to .
If , the output result is obvious because there is only one for each, no matter how you sort it.

Sample Input 2

3 2
C2 D1
S3 H3

Sample Output 2

S3 S1 S2
C1 C2 C3
D2 D3 D1
H1 H2 H3

The initial sequence is .
By the first query, ~ goes to the beginning, so it is changed to .
By the first query, ~ goes to the beginning, so it is changed to .
Subsequences consisting of only each mark are for spades, for clovers, for diamonds, and for hearts.

Sample Input 3

2 1
C2 C2

Sample Output 3

S1 S2
C2 C1
D1 D2
H1 H2

In some cases, and are equal. In that case, bring that one card to the beginning.