In this problem, a dictionary is collection of key-value pairs, where keys are lower-case letters, and values are non-negative integers. Given an old dictionary and a new dictionary, find out what were changed.

Each dictionary is formatting as follows:

{key:value,key:value,...,key:value}

Each key is a string of lower-case letters, and each value is a non-negative integer without leading zeros or prefix ‘+’. (i.e. -4, 03 and +77 are illegal). Each key will appear at most once, but keys can appear in any order.

Input

The first line contains the number of test cases T (T ≤ 1000). Each test case contains two lines. The first line contains the old dictionary, and the second line contains the new dictionary. Each line will contain at most 100 characters and will not contain any whitespace characters. Both dictionaries could be empty.

WARNING: there are no restrictions on the lengths of each key and value in the dictionary. That means keys could be really long and values could be really large.

Output

For each test case, print the changes, formatted as follows:

• First, if there are any new keys, print ‘+’ and then the new keys in increasing order (lexicographically), separated by commas.

• Second, if there are any removed keys, print ‘-’ and then the removed keys in increasing order (lexicographically), separated by commas.

• Last, if there are any keys with changed value, print ‘*’ and then these keys in increasing order (lexicographically), separated by commas.

If the two dictionaries are identical, print ‘No changes’ (without quotes) instead. Print a blank line after each test case.

Sample Input

3
{a:3,b:4,c:10,f:6}
{a:3,c:5,d:10,ee:4}
{x:1,xyz:123456789123456789123456789}
{xyz:123456789123456789123456789,x:1}
{first:1,second:2,third:3}
{third:3,second:2}

Sample Output

+d,ee

-b,f

*c

No changes

-first

题目类型：简单字符处理+二分搜索

算法分析：使用map<string, string>ma[2]分别表示旧和新字典，然后直接循环判断。注意解析字符串的方法和字典可能是空的

The word “search engine” may not be strange to you. Generally speaking, a search engine searches the web pages available in the Internet, extracts and organizes the information and responds to users’ queries with the most relevant pages. World famous search engines, like GOOGLE, have become very important tools for us to use when we visit the web. Such conversations are now common in our daily life:

“What does the word like ∗ ∗ ∗ ∗ ∗∗ mean?”

“Um. . . I am not sure, just google it.”

In this problem, you are required to construct a small search engine. Sounds impossible, does it? Don’t worry, here is a tutorial teaching you how to organize large collection of texts efficiently and respond to queries quickly step by step. You don’t need to worry about the fetching process of web pages, all the web pages are provided to you in text format as the input data. Besides, a lot of queries are also provided to validate your system.

Modern search engines use a technique called inversion for dealing with very large sets of documents. The method relies on the construction of a data structure, called an inverted index, which associates terms (words) to their occurrences in the collection of documents. The set of terms of interest is called the vocabulary, denoted as V . In its simplest form, an inverted index is a dictionary where each search key is a term ω ∈ V . The associated value b(ω) is a pointer to an additional intermediate data structure, called a bucket. The bucket associated with a certain term ω is essentially a list of pointers marking all the occurrences of ω in the text collection. Each entry in each bucket simply consists of the document identifier (DID), the ordinal number of the document within the collection and the ordinal line number of the term’s occurrence within the document.

Let’s take Figure-1 for an example, which describes the general structure. Assuming that we only have three documents to handle, shown at the right part in Figure-1; first we need to tokenize the text for words (blank, punctuations and other non-alphabetic characters are used to separate words) and construct our vocabulary from terms occurring in the documents. For simplicity, we don’t need to consider any phrases, only a single word as a term. Furthermore, the terms are case-insensitive (e.g. we consider “book” and “Book” to be the same term) and we don’t consider any morphological variants (e.g. we consider “books” and “book”, “protected” and “protect” to be different terms) and hyphenated words (e.g. “middle-class” is not a single term, but separated into 2 terms “middle” and “class” by the hyphen). The vocabulary is shown at the left part in Figure-1. Each term of the vocabulary has a pointer to its bucket. The collection of the buckets is shown at the middle part in Figure-1. Each item in a bucket records the DID of the term’s occurrence.

After constructing the whole inverted index structure, we may apply it to the queries. The query is in any of the following formats:

term

term AND term

term OR term

NOT term

A single term can be combined by Boolean operators: ‘AND’, ‘OR’ and ‘NOT’ (‘term1 AND term2’ means to query the documents including term1 and term2; ‘term1 OR term2’ means to query the documents including term1 or term2; ‘NOT term1’ means to query the documents not including term1). Terms are single words as defined above. You are guaranteed that no non-alphabetic characters appear in a term, and all the terms are in lowercase. Furthermore, some meaningless stop words (common words such as articles, prepositions, and adverbs, specified to be “the, a, to, and, or, not” in our problem) will not appear in the query, either.

For each query, the engine based on the constructed inverted index searches the term in the vocabulary, compares the terms’ bucket information, and then gives the result to user. Now can you construct the engine?

Input

The input starts with integer N (0 < N < 100) representing N documents provided. Then the next N sections are N documents. Each section contains the document content and ends with a single line of ten asterisks.

**********

You may assume that each line contains no more than 80 characters and the total number of lines in the N documents will not exceed 1500.

Next, integer M (0 < M ≤ 50000) is given representing the number of queries, followed by M lines, each query in one line. All the queries correspond to the format described above.

Output

For each query, you need to find the document satisfying the query, and output just the lines within the documents that include the search term (For a ‘NOT’ query, you need to output the whole document). You should print the lines in the same order as they appear in the input. Separate different documents with a single line of 10 dashes.

----------

If no documents matching the query are found, just output a single line: ‘Sorry, I found nothing.’. The output of each query ends with a single line of 10 equal signs.

==========

Sample Input

4
A manufacturer, importer, or seller of
digital media devices may not (1) sell,
or offer for sale, in interstate commerce,
or (2) cause to be transported in, or in a
manner affecting, interstate commerce,
a digital media device unless the device
includes and utilizes standard security
technologies that adhere to the security
system standards.
**********
Of course, Lisa did not necessarily
intend to read his books. She might
want the computer only to write her
midterm. But Dan knew she came from
a middle-class family and could hardly
afford the tuition, let alone her reading
fees. Books might be the only way she
could graduate
**********
Research in analysis (i.e., the evaluation
of the strengths and weaknesses of
computer system) is essential to the
development of effective security, both
for works protected by copyright law
and for information in general. Such
research can progress only through the
open publication and exchange of
complete scientific results
**********
I am very very very happy!
What about you?
**********
6
computer
books AND computer
books OR protected
NOT security
very
slick
Sample Output

want the computer only to write her
----------
computer system) is essential to the
==========
intend to read his books. She might
want the computer only to write her
fees. Books might be the only way she
==========
intend to read his books. She might
fees. Books might be the only way she
----------
for works protected by copyright law
==========
Of course, Lisa did not necessarily
intend to read his books. She might
want the computer only to write her
midterm. But Dan knew she came from
a middle-class family and could hardly
afford the tuition, let alone her reading
fees. Books might be the only way she
could graduate
----------
I am very very very happy!
What about you?
==========
I am very very very happy!
==========
Sorry, I found nothing.
==========

题目类型：简单字符处理+二分搜索

算法分析：根据题目的提示使用map<string, vector<node>>dict[maxn]来模拟倒插表，注意数据集中的单词为忽略大小写的

In this problem, we consider a simple programming language that has only declarations of onedimensional integer arrays and assignment statements. The problem is to find a bug in the given program.

The syntax of this language is given in BNF as follows:

⟨program⟩ ::= ⟨declaration⟩|⟨program⟩⟨declaration⟩|⟨program⟩⟨assignment⟩

⟨declaration⟩ ::= ⟨array name⟩ [⟨number⟩]⟨new line⟩

⟨assignment⟩ ::= ⟨array name⟩ [⟨expression⟩]= ⟨expression⟩⟨newline⟩

⟨expression⟩ ::= ⟨number⟩|⟨array name⟩ [⟨expression⟩]

⟨number⟩ ::= ⟨digit⟩|⟨digit positive⟩⟨digit string⟩

⟨digit string⟩ ::= ⟨digit⟩|⟨digit⟩⟨digit string⟩

⟨digit positive⟩ ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

⟨digit⟩ ::= 0 | ⟨digit positive⟩

⟨array name⟩ ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

where ⟨new line⟩ denotes a new line character (LF).

Characters used in a program are alphabetical letters, decimal digits, =, [, ] and new line characters. No other characters appear in a program.

A declaration declares an array and specifies its length. Valid indices of an array of length n are integers between 0 and n − 1, inclusive. Note that the array names are case sensitive, i.e. array a and array A are different arrays. The initial value of each element in the declared array is undefined.

For example, array a of length 10 and array b of length 5 are declared respectively as follows.

a[10]

b[5]

An expression evaluates to a non-negative integer. A ⟨number⟩ is interpreted as a decimal integer. An ⟨array name⟩ [⟨expression⟩] evaluates to the value of the ⟨expression⟩-th element of the array. An assignment assigns the value denoted by the right hand side to the array element specified by the left hand side.

Examples of assignments are as follows.

a[0]=3

a[1]=0

a[2]=a[a[1]]

a[a[0]]=a[1]

A program is executed from the first line, line by line. You can assume that an array is declared once and only once before any of its element is assigned or referred to.

Given a program, you are requested to find the following bugs.

• An index of an array is invalid.

• An array element that has not been assigned before is referred to in an assignment as an index of array or as the value to be assigned.

You can assume that other bugs, such as syntax errors, do not appear. You can also assume that integers represented by ⟨number⟩s are between 0 and 231 − 1 (= 2147483647), inclusive.

Input

The input consists of multiple datasets followed by a line which contains only a single ‘.’ (period). Each dataset consists of a program also followed by a line which contains only a single ‘.’ (period). A program does not exceed 1000 lines. Any line does not exceed 80 characters excluding a new line character.

Output

For each program in the input, you should answer the line number of the assignment in which the first bug appears. The line numbers start with 1 for each program. If the program does not have a bug, you should answer zero. The output should not contain extra characters such as spaces.

Sample Input

a[3]
a[0]=a[1]
.
x[1]
x[0]=x[0]
.
a[0]
a[0]=1
.
b[2]
b[0]=2
b[1]=b[b[0]]
b[0]=b[1]
.
g[2]
G[10]
g[0]=0
g[1]=G[0]
.
a[2147483647]
a[0]=1
B[2]
B[a[0]]=2
a[B[a[0]]]=3
a[2147483646]=a[2]
.
.
Sample Output

2

2

2

3

4

0

题目类型：简单字符处理+栈模拟

算法分析：由于表达式可能存在嵌套的情况，所以需要使用栈来模拟计算。对于每个赋值语句'='左右两边的表达式都要分别计算并需要考虑不同的情况

I mean your borrowers of books — those mutilators of collections, spoilers of the symmetry of shelves, and creators of odd volumes. – (Charles Lamb, Essays of Elia (1823) ‘The Two Races of Men’)

Like Mr. Lamb, librarians have their problems with borrowers too. People don’t put books back where they should. Instead, returned books are kept at the main desk until a librarian is free to replace them in the right places on the shelves. Even for librarians, putting the right book in the right place can be very time-consuming. But since many libraries are now computerized, you can write a program to help.

When a borrower takes out or returns a book, the computer keeps a record of the title. Periodically, the librarians will ask your program for a list of books that have been returned so the books can be returned to their correct places on the shelves. Before they are returned to the shelves, the returned books are sorted by author and then title using the ASCII collating sequence. Your program should output the list of returned books in the same order as they should appear on the shelves. For each book, your program should tell the librarian which book (including those previously shelved) is already on the shelf before which the returned book should go.

Input

First, the stock of the library will be listed, one book per line, in no particular order. Initially, they are all on the shelves. No two books have the same title. The format of each line will be:

title" by author

The end of the stock listing will be marked by a line containing only the word:

END

Following the stock list will be a series of records of books borrowed and returned, and requests from librarians for assistance in restocking the shelves. Each record will appear on a single line, in one of the following formats:

BORROW title

RETURN title

SHELVE

The list will be terminated by a line containing only the word:

END

Output

Each time the SHELVE command appears, your program should output a series of instructions for the librarian, one per line, in the format:

Put title1 after title2

or, for the special case of the book being the first in the collection:

Put title first

After the set of instructions for each SHELVE, output a line containing only the word:

END

Assumptions & Limitations:

1. A title is at most 80 characters long.

2. An author is at most 80 characters long.

3. A title will not contain the double quote (") character.

Sample Input

"The Canterbury Tales" by Chaucer, G.
"Algorithms" by Sedgewick, R.
"The C Programming Language" by Kernighan, B. and Ritchie, D.
END
BORROW "Algorithms"
BORROW "The C Programming Language"
RETURN "Algorithms"
RETURN "The C Programming Language"
SHELVE
END

Sample Output

Put "The C Programming Language" after "The Canterbury Tales"

Put "Algorithms" after "The C Programming Language"

END

题目类型：简单字符处理

算法分析：首先将图书的标题和作者读入并分别使用结构体数组存储相应的值并排序，然后分类处理。当输入的命令是”BORROW”时，将相应数据的访问标志is_return置为-1，当命令是”RETURN”时，将相应数据的访问标志is_return置为1，当命令是”SHELVE”时，遍历所有is_return为1的数据，然后按照位置的不同输出相应的信息并把is_return置为0，注意含first语句的输出。下面第一份代码是更好的实现