Macros are a feature of the C/C++ language that perform text substitution (also known as "macro expansion") based on predefined rules, enabling functions such as defining constants and simplifying repetitive code input. For example:

#define PI 3.14159
double area = PI * r * r;

After macro expansion, the above code becomes:

double area = 3.14159 * r * r;

In this process, the macro definition command becomes an empty line, while macros in other lines are expanded into the text defined by the rules.

The processing of macros in C/C++ code during compilation is performed by the preprocessor. Your task is to implement a simplified version of a preprocessor, with the following requirements:

• The code consists of lines. Each line, excluding the newline character at the end, consists of printable ASCII characters (ASCII range 32–126). Each line is either a preprocessor command (starting with #) or plain text (otherwise).
• The preprocessor processes the code line by line:
  • If it is a preprocessor command, execute the command and output an empty line.
  • If it is plain text, perform macro expansion on it and output the result.
• There are two types of preprocessor commands: the macro definition command #define and the macro undefinition command #undef.
  • The format of the macro definition command is #define <name> <content>, where the first part #define is the command name, the second part <name> is the name of the macro to be defined, and the third part <content> is the expansion content of the macro.
  • The format of the macro undefinition command is #undef <name>, where the first part #undef is the command name, and the second part <name> is the name of the macro to be undefined.

In both preprocessor commands, adjacent parts are strictly separated by a single space. <name> is an identifier (one or more characters) consisting of uppercase and lowercase letters, digits, and underscores. <content> can contain any printable ASCII characters (zero or more characters). The effective scope of a macro definition starts from the line where it is defined and ends at the line where the corresponding macro undefinition occurs (if there is no corresponding undefinition, the effective scope covers until the end of the file).

When performing macro expansion on plain text, every sequence of consecutive uppercase letters, lowercase letters, digits, and underscores in a line of text is treated as an identifier (rather than a part of one), and the rest are treated as other characters. Perform macro expansion on the identifiers in the text from left to right:

1. If the identifier is a valid macro name, replace it with its corresponding expansion content. At this point, the macro name enters a state of being expanded until this process ends; otherwise, keep the macro name as is. For example, if macro A is defined as b, then text A expands to b (substitution occurs), text B expands to B (undefined, no substitution), text AA expands to AA (as AA is a different identifier from A and is undefined), and text A*B expands to b*B.
2. After a substitution occurs, if the expansion content contains identifiers, apply the above expansion operation repeatedly, which is called "multiple expansion". For example, if macro A is defined as B and macro B is defined as c, then the expansion result of text A is c.
3. If the macro name to be expanded is the same as a macro name currently being expanded, it is called "recursive expansion", and this macro name will not be expanded further. This rule is used to prevent infinite recursive expansion. For example, if macro A is defined as B+a and macro B is defined as A+b, then the expansion result of text A is A+b+a. Since the initial A is in the state of being expanded, the A inside A+b+a is not expanded further.
4. Other characters are kept as is.

Note: For the sake of simplification, the requirements of this problem are not entirely consistent with the description in the C/C++ language standard; please follow the requirements above. The most obvious difference is that this problem only has two types of lexical units: identifiers and other characters; there are no numeric literals, strings, comments, etc.

Input

Read data from the file preprocessor.in. The first line of the input contains a positive integer $n$, representing the number of lines of code to be processed. The next $n$ lines are the code to be processed.

Output

Output to the file preprocessor.out. Output $n$ lines, which are the results after processing the input line by line.

Examples

Input 1

5
#define BEGIN {
#define END }
#define INTEGER int
class C BEGIN INTEGER x; END;
INTEGER main() BEGIN C c; END

Output 1

class C { int x; };
int main() { C c; }

Examples 2

See preprocessor/preprocessor2.in and preprocessor/preprocessor2.ans in the contestant directory.

Examples 3

See preprocessor/preprocessor3.in and preprocessor/preprocessor3.ans in the contestant directory.

Constraints

For 20% of the data, there are no #define or #undef commands. For another 20% of the data, there is no multiple expansion, and there are no #undef commands. For another 20% of the data, there is no multiple expansion. For another 20% of the data, there is no recursive expansion. For the remaining data, there are no special restrictions. For 100% of the data, $n \le 100$, the number of characters in each input line does not exceed 100, and it is guaranteed that the number of characters in each output line does not exceed 1,000 (character counts do not include the newline character at the end of the line). It is guaranteed that the preprocessor commands in the input data are valid, including but not limited to: The # character will only appear at the first position of a line containing a preprocessor command; it will not appear anywhere else (including in preprocessor commands and plain text). The format of macro definition and undefinition commands is correct and strictly follows the format described in the problem. The same macro will not be defined again before it is undefined. The macro to be undefined has been defined previously and has not been undefined yet.

That is to say, you do not need to perform any syntax or semantic error checking.

Note

When reading input for this problem, it is recommended to use the line-based string reading function in C++, for example:

#include <iostream>
#include <string>
using namespace std;
string line;
// Read a line from cin into line (newline character is discarded)
getline(cin, line);

You can also use the fgets function provided by the C language, for example:

#include <stdio.h>
#define MAX_LEN 200
char line[MAX_LEN];
// Read a line from stdin into line (includes newline character)
fgets(line, MAX_LEN, stdin);

Note: After reading the number of lines $n$, you may need to read an extra line to ignore the subsequent newline character.