Trees are fundamental in many branches of computer science (Pun definitely intended). Current stateof-the art parallel computers such as Thinking Machines’ CM-5 are based on fat trees. Quad- and octal-trees are fundamental to many algorithms in computer graphics.

This problem involves building and traversing binary trees.

Given a sequence of binary trees, you are to write a program that prints a level-order traversal of each tree. In this problem each node of a binary tree contains a positive integer and all binary trees have have fewer than 256 nodes.

In a level-order traversal of a tree, the data in all nodes at a given level are printed in left-to-right order and all nodes at level k are printed before all nodes at level k + 1.

For example, a level order traversal of the tree on the right is: 5, 4, 8, 11, 13, 4, 7, 2, 1.

In this problem a binary tree is specified by a sequence of pairs ‘(n,s)’ where n is the value at the node whose path from the root is given by the string s. A path is given be a sequence of ‘L’s and ‘R’s where ‘L’ indicates a left branch and ‘R’ indicates a right branch. In the tree diagrammed above, the node containing 13 is specified by (13,RL), and the node containing 2 is specified by (2,LLR). The root node is specified by (5,) where the empty string indicates the path from the root to itself. A binary tree is considered to be completely specified if every node on all root-to-node paths in the tree is given a value exactly once.

Input

The input is a sequence of binary trees specified as described above. Each tree in a sequence consists of several pairs ‘(n,s)’ as described above separated by whitespace. The last entry in each tree is ‘()’. No whitespace appears between left and right parentheses.

All nodes contain a positive integer. Every tree in the input will consist of at least one node and no more than 256 nodes. Input is terminated by end-of-file.

Output

For each completely specified binary tree in the input file, the level order traversal of that tree should be printed. If a tree is not completely specified, i.e., some node in the tree is NOT given a value or a node is given a value more than once, then the string ‘not complete’ should be printed.

Sample Input

(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()

Sample Output

5 4 8 11 13 4 7 2 1

not complete

题目类型：二叉树遍历

算法分析：首先应该先建树，然后按照题目的要求边读入数据，边向二叉树添加节点。对于没有的子节点则创建一个节点，有子节点的则直接移动到其子节点中，直到输入命令结束。判断所在的节点是否已经赋过值了，如果已经赋过值了就置合法标志valid为false。接着使用BFS遍历建好的二叉树并将节点的值赋值到输出数组中，对于没有赋过值的节点，则将valid标志置为false并break

A number of K balls are dropped one by one from the root of a fully binary tree structure FBT. Each time the ball being dropped first visits a non-terminal node. It then keeps moving down, either follows the path of the left subtree, or follows the path of the right subtree, until it stops at one of the leaf nodes of FBT. To determine a ball’s moving direction a flag is set up in every non-terminal node with two values, either false or true. Initially, all of the flags are false. When visiting a non-terminal node if the flag’s current value at this node is false, then the ball will first switch this flag’s value, i.e., from the false to the true, and then follow the left subtree of this node to keep moving down. Otherwise, it will also switch this flag’s value, i.e., from the true to the false, but will follow the right subtree of this node to keep moving down. Furthermore, all nodes of FBT are sequentially numbered, starting at 1 with nodes on depth 1, and then those on depth 2, and so on. Nodes on any depth are numbered from left to right.

For example, Fig. 1 represents a fully binary tree of maximum depth 4 with the node numbers 1, 2, 3, ..., 15. Since all of the flags are initially set to be false, the first ball being dropped will switch flag’s values at node 1, node 2, and node 4 before it finally stops at position 8. The second ball being dropped will switch flag’s values at node 1, node 3, and node 6, and stop at position 12. Obviously, the third ball being dropped will switch flag’s values at node 1, node 2, and node 5 before it stops at position 10.

Now consider a number of test cases where two values will be given for each test. The first value is D, the maximum depth of FBT, and the second one is I, the I-th ball being dropped. You may assume the value of I will not exceed the total number of leaf nodes for the given FBT.

Please write a program to determine the stop position P for each test case.

For each test cases the range of two parameters D and I is as below:

2 ≤ D ≤ 20, and 1 ≤ I ≤ 524288.

Input

Contains l + 2 lines.

Line 1 l the number of test cases

Line 2 D1 I1 test case #1, two decimal numbers that are separated by one blank

...

Line k + 1 Dk Ik test case #k

Line l + 1 Dl Il test case #l

Line l + 2 -1 a constant ‘-1’ representing the end of the input file

Output

Contains l lines.

Line 1 the stop position P for the test case #1

...

Line k the stop position P for the test case #k

...

Line l the stop position P for the test case #l

Sample Input

5
4 2
3 4
10 1
2 2
8 128
-1
Sample Output

12

7

512

3

255

题目类型：二叉树查找

算法分析：由于每个节点具有开关属性，则当标号k为奇数时其为走左子树的第(k+1)/2个节点(也即其在左子树中的顺序标号)，否则为走右子树的第k/2个节点，一共走D-1次

You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4 kinds of commands:

• 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y )

• 2 X Y : move box X to the right to Y (ignore this if X is already the right of Y )

• 3 X Y : swap box X and Y

• 4: reverse the whole line.

Commands are guaranteed to be valid, i.e. X will be not equal to Y .

For example, if n = 6, after executing 1 1 4, the line becomes 2 3 1 4 5 6. Then after executing 2 3 5, the line becomes 2 1 4 5 3 6. Then after executing 3 1 6, the line becomes 2 6 4 5 3 1. Then after executing 4, then line becomes 1 3 5 4 6 2

Input

There will be at most 10 test cases. Each test case begins with a line containing 2 integers n, m (1 ≤ n, m ≤ 100, 000). Each of the following m lines contain a command.

Output

For each test case, print the sum of numbers at odd-indexed positions. Positions are numbered 1 to n from left to right.

Sample Input

6 4
1 1 4
2 3 5
3 1 6
4
6 3
1 1 4
2 3 5
3 1 6
100000 1
4

Sample Output

Case 1: 12

Case 2: 9

Case 3: 2500050000

题目类型：双重链表

算法分析：使用left[x]表示x的左边节点标号，right[x]表示x的右边节点标号，之后按照题目模拟即可。注意答案可能超出int的范围

Suppose you have to evaluate an expression like A*B*C*D*E where A,B,C,D and E are matrices. Since matrix multiplication is associative, the order in which multiplications are performed is arbitrary. However, the number of elementary multiplications needed strongly depends on the evaluation order you choose.

For example, let A be a 50*10 matrix, B a 10*20 matrix and C a 20*5 matrix. There are two different strategies to compute A*B*C, namely (A*B)*C and A*(B*C).

The first one takes 15000 elementary multiplications, but the second one only 3500.

Your job is to write a program that determines the number of elementary multiplications needed for a given evaluation strategy.

Input

Input consists of two parts: a list of matrices and a list of expressions.

The first line of the input file contains one integer n (1 ≤ n ≤ 26), representing the number of matrices in the first part. The next n lines each contain one capital letter, specifying the name of the matrix, and two integers, specifying the number of rows and columns of the matrix.

The second part of the input file strictly adheres to the following syntax (given in EBNF):

SecondPart = Line { Line }

Line = Expression

Expression = Matrix | "(" Expression Expression ")"

Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"

Output

For each expression found in the second part of the input file, print one line containing the word ‘error’ if evaluation of the expression leads to an error due to non-matching matrices. Otherwise print one line containing the number of elementary multiplications needed to evaluate the expression in the way specified by the parentheses.

Sample Input

9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))

Sample Output

0

0

0

error

10000

error

3500

15000

40500

47500

15125

题目类型：表达式计算(栈模拟)

算法分析：使用栈来模拟计算矩阵表达式

There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.

The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N ≤ 1000 coaches numbered in increasing order 1, 2, . . . , N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1.a2, . . . , aN . Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.

Input

The input file consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, . . . , N. The last line of the block contains just ‘0’. The last block consists of just one line containing ‘0’.

Output

The output file contains the lines corresponding to the lines with permutations in the input file. A line of the output file contains ‘Yes’ if it is possible to marshal the coaches in the order required on the corresponding line of the input file. Otherwise it contains ‘No’. In addition, there is one empty line after the lines corresponding to one block of the input file. There is no line in the output file corresponding to the last “null” block of the input file.

Sample Input

5

1 2 3 4 5

5 4 1 2 3

0

6

6 5 4 3 2 1

0

0

Sample Output

Yes

No

Yes

题目类型：栈模拟

算法分析：使用一个Stack数组表示序列中数的情况，Stack[i] == 0表示i元素还没有入栈；Stack[i] == 1表示i元素在栈内；Stack[i] == 2表示i元素已经出栈。边输入边处理：维护一个合法标志valid，初始时valid置为true。读入一个元素a，判断比a大的元素是否还有在栈中的，如果还有则valid置为false；如果判断完之后valid仍为true，则更新在栈中的最大值元素maxval，a出栈并将小于a的所有还没有入栈的元素都压入栈中。另一个解法是考虑每个元素进入栈中只有两种操作：(1)进栈然后出栈(2)进栈然后暂不出栈。也即存在进栈，立即出栈和暂缓出栈三种方式。依次考察出栈序列的每个元素并判断。下面第一份代码是更好的实现

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]来模拟倒插表，注意数据集中的单词为忽略大小写的