Help!

Time limit1sMemory limit128 MB

Summary

Given two patterns of literal words and named placeholders, find the lexicographically smallest word phrase matching both, or output a minus sign if none exists.

Level: Medium7 of 10
Topics: String, Hash map, Implementation, Brute force
Solved: No attempts yet

Problem

MegaFirm Inc. has created a set of patterns to help its telephone help-desk operators respond to customers. A pattern is a phrase made of words and placeholders. A word is a string of lowercase letters. A placeholder is a word enclosed in angle brackets (that is, < ... >).

A phrase matches a pattern if each placeholder in the pattern can be systematically replaced by a word so that the pattern and the phrase become equal. "Systematically" means that all placeholders with the same name must be replaced by the same word. (Placeholders with different names are allowed to be replaced by the same word.)

For example, the phrase

to be or not to be

matches the pattern

<foo> be <bar> not <foo> <baf>

because we can replace <foo> by to, <bar> by or, and <baf> by be.

Given two patterns, find a phrase that matches both of them.

Input

The first line of input contains n, the number of test cases. Each test case consists of two lines, each of which is a pattern. Patterns consist of lowercase words and placeholders containing lowercase words. No pattern exceeds 100 characters. A word contains at most 16 characters. A single space separates adjacent words and placeholders.

Output

For each test case, output on its own line a phrase that matches both patterns. Since several phrases may match, output the lexicographically smallest one. This is the phrase obtained by replacing every free placeholder — one whose word is not forced by any literal — with the single letter a. If no phrase matches both patterns, output a line containing a single minus sign (-).

Examples3

Example 1

Input

3
how now brown <animal>
<foo> now <color> cow
who are you
<a> <b> <a>
<a> b
c <a>

Expected output

how now brown cow
-
c b

Example 2

Input

1
<foo> be <bar> not <foo> <baf>
to be or not to be

Expected output

to be or not to be

Example 3
Input
```
1
<x> <y>
<p> <q>
```
Expected output
```
a a
```