Friend Suggestions Simulator

A new social network wants to improve its service by suggesting people you may know.
For a given user X, the suggestion algorithm works as follows:

Consider every user who is not already a friend of X (and is not X).
For each such candidate Y, count how many mutual friends X and Y share.
Pick the candidate with the largest number of mutual friends.
If there is a tie, pick the one whose name is lexicographically smallest.

Lexicographic order is defined as usual over lowercase Latin letters:
A string $A$ is lexicographically smaller than $B$ if either

there exists a position $i$ such that for all $j < i$ the characters are equal in $A$ and $B$ , and the $i$ -th character of $A$ appears earlier in the alphabet than the $i$ -th character of $B$; or
$A$ is a prefix of $B$ .

For example, "abc" < "abd", "abc" < "ba", "abc" < "abcd", but "abc" > "aaa" and "abc" > "a".

Your task is to simulate this social network. Initially, no one is friends with anyone. You will process $M$ operations of three types:

ADD name1 name2 — make the two users friends
REMOVE name1 name2 — remove the friendship between the two users
SUGGEST name — output the suggested friend for name according to the rule above

It is guaranteed that for every SUGGEST operation, at least one valid suggestion exists (i.e., not everyone is already a friend of that user).

Constraints

$2 \leq N \leq 50$
Usernames are distinct, consist only of lowercase Latin letters, and have length $1$ to $10$ .
$1 \leq M \leq 2000$
Users in every ADD operation aren't yet friends
Users in every REMOVE operation are already friends

Input

The first line contains an integer $T$ — the number of test cases.

Each test case is given as follows:

One line with two integers $N$ and $M$ .
$N$ lines with the distinct usernames.
$M$ lines, each an operation in one of the formats:
- ADD name1 name2
- REMOVE name1 name2
- SUGGEST name

Output

For each test case $i$ ( $1 \leq i \leq T$ ), output Case #i:, followed by the results of the SUGGEST operations.
For each SUGGEST operation, print the suggested friend's name, on a line of its own.

Example

Input

1
4 6
gojira
rachvela
lekva
samurai
ADD gojira rachvela
ADD gojira lekva
ADD lekva samurai
SUGGEST samurai
ADD samurai gojira
SUGGEST samurai

Output

Case #1:
gojira
rachvela