This page is still under construction.

Parts of this page are still being built. What you see may change.

Find the Hidden Word

Time limit1sMemory limit256 MB

Summary
Given a list of known words and several messages, find which listed words occur as substrings in each message and report NO, the unique word, or AMBIGUOUS.
Level

Medium5 of 10

Topics
String matching, Trie
Solved
No attempts yet

Problem

A white rabbit wants to send one word to a black rabbit without letting any other rabbit find out which word it is. The two rabbits agreed on a scheme beforehand, and the white rabbit handed the black rabbit the full list of words it knows. When the white rabbit sends a word, it mixes many other letters in front of the word, behind it, and around it, and sends the whole thing as one long message.

For a message, find every word on the list that occurs in the message as a contiguous substring. If exactly one distinct word occurs, that word is the one the white rabbit meant to send. Help the black rabbit answer for each message.

Input

The first line has the number of test cases TT (1≤T≤21 \le T \le 2). Each test case has the following form.

  1. The first line has the number of words the white rabbit knows, NN (1≤N≤2000001 \le N \le 200000).
  2. Each of the next NN lines has one known word. The length KiK_i of a word is at least 6 and at most 50, and a word uses lowercase English letters only.
  3. The next line has the number of messages the white rabbit sent, MM (1≤M≤101 \le M \le 10).
  4. Each of the next MM lines has one message. The length LiL_i of a message is at least 6 and at most 10000, and a message uses lowercase English letters only.

Output

Print one line for each message. First count the distinct words the white rabbit knows that occur in the message as a contiguous substring.

  1. If there is no such word, print NO.
  2. If there is exactly one, print that word as it is.
  3. If there are two or more, print AMBIGUOUS.

Examples6

  1. Example 1

    Input
    1
    5
    ambiguous
    metamorphism
    inevitably
    impeccable
    constellation
    3
    inevitable
    abcdefghijklmetamorphismnopqrstuvwxyz
    itsambiguousbecausethereisconstellationtoo
    
    Expected output
    NO
    metamorphism
    AMBIGUOUS
    
  2. Example 2

    Input
    1
    1
    abcdef
    2
    abcdef
    abcdeg
    
    Expected output
    abcdef
    NO
    
  3. Example 3

    Input
    1
    2
    ababab
    zzzzzz
    2
    abababababab
    abababab
    
    Expected output
    ababab
    ababab
    
  4. Example 4

    Input
    1
    2
    abcdef
    abcdefg
    3
    zzabcdefgzz
    zzabcdefzz
    zzzzzzabcdzzzz
    
    Expected output
    AMBIGUOUS
    abcdef
    NO
    
  5. Example 5

    Input
    2
    2
    bananas
    cherrys
    2
    ibuybananastoday
    icherryeverything
    1
    bananas
    2
    bananasplit
    cherryscherrys
    
    Expected output
    bananas
    NO
    bananas
    NO
    
  6. Example 6

    Input
    1
    5
    alphabet
    betagram
    gammaray
    deltaflow
    epsilonx
    10
    xxalphabetxx
    zzzbetagramzzz
    qqqqqqqqqq
    alphabetbetagram
    deltaflowdeltaflow
    gammarayyyyy
    epsilonxepsilonx
    nothingheretoseeatall
    alphabetgammaray
    deltaflowepsilonx
    
    Expected output
    alphabet
    betagram
    NO
    AMBIGUOUS
    deltaflow
    gammaray
    epsilonx
    NO
    AMBIGUOUS
    AMBIGUOUS