Under construction

Still being built. Things may change

Reading Brackets in English

Time limit8sMemory limit512 MB

Summary
Given an English phrase describing nested lists, output the S-expression it encodes, or AMBIGUOUS if the phrase has more than one reading.
Level

Medium6 of 10

Topics
String, Dynamic programming, Recursion
Solved
No attempts yet

Problem

Shun and his professor are studying Lisp and S-expressions. Shun is in Tokyo to give a presentation on their research. His professor cannot go with him because of other work today.

An hour ago, Shun was making final checks on his slides when he found some serious mistakes. He called his professor right away because he did not have enough data on hand to fix them.

Their discussion is still going on. It is proceeding with difficulty. Most of their data is written in S-expressions, so they have to exchange S-expressions over the telephone.

Your task is to write a program that outputs the S-expression represented by a given English phrase.

The rules to translate an S-expression are as follows.

  1. An S-expression with one element is translated into "a list of ". (e.g. "(A)" becomes "a list of A")
  2. An S-expression with two elements is translated into "a list of and ". (e.g. "(A B)" becomes "a list of A and B")
  3. An S-expression with more than three elements is translated into "a list of , , ... and ". (e.g. "(A B C D)" becomes "a list of A, B, C and D")
  4. The above rules are applied recursively. (e.g. "(A (P Q) B (X Y Z) C)" becomes "a list of A, a list of P and Q, B, a list of X, Y and Z and C")

Each atomic element of an S-expression is a string of fewer than 10 capital letters. All words ("a", "list", "of", "and") and atomic elements are separated by a single space, but no space is inserted before a comma. No phrase for an empty S-expression occurs in the input. You can assume that every test case can be translated into an S-expression, but the possible S-expressions may not be unique.

Input

The first line contains a single positive integer NN, the number of test cases. Then NN test cases follow. Each test case is one line containing an English phrase that represents an S-expression. The length of each phrase is up to 1000 characters.

Output

For each test case, output the corresponding S-expression on its own line. A single space is inserted between elements, and no space is inserted after an open bracket "(" or before a closing bracket ")". If the phrase can be read as two or more different S-expressions, output AMBIGUOUS.

Examples1

  1. Example 1

    Input
    4
a list of A, B, C and D
a list of A, a list of P and Q, B, a list of X, Y and Z and C
a list of A
a list of a list of A and B
    Expected output
    (A B C D)
(A (P Q) B (X Y Z) C)
(A)
AMBIGUOUS