F :: Term Generator

Time Limit: 10 Seconds Memory Limit: 65536 KB

A formula has the syntax shown in figure 1(a). If a formula has the particular syntax given in figure 1(b) we say that the formula is in Normal Form (NF).

A formula is converted to NF according to the rewriting rules given below, where F represents a formula, S stands for a non empty sequence of formulae, and s and s' denote possibly empty sequences of formulae. Applying a rewriting rule q->r on a formula F means to substitute by r a part of F that matches the pattern q, as shown in figure 2. The conversion terminates when no rewriting rule can be applied. The conversion terminates for any formula, and the result is unique regardless which rules are applied on which parts of the formula and in which order.

Let NF(F) be the normal form of the formula F. The problem is to write a term generator that for a given formula F and a number k outputs the next k terms from NF(F) in the order in which they appear in NF(F). If the terms are exhausted, the generator continues from the first term of NF(F). For example, consider F=(+(*(+(*ab)(+a))b)), and NF(F)=(+(*abb)(*ab)) as in figure 2. Generating the first term from NF(F) yields (*abb). Generating two more terms produces (*ab), (*abb). Notice that if NF(F) contains similar terms, as in the last example in figure 3, these terms are considered distinct.

Input

The content of a data set is F k1...kn 0, n>0, where F is a formula, and k1...kn are long integers different than 0. For each k_i, i=1,n, the program generates the next |ki| terms from NF(F) and, if k_i>0, prints these terms on the standard output.

Output

Each printed term starts from the beginning of a line and there are no white spaces between the characters of the term. The generated terms are not printed if k_i<0. White spaces are used freely in the input. Each formula F in the input has at most 150 characters and each term of NF(F) is at most 80 characters long, not counting white spaces. The input data terminate with an end of file, and are correct.

Sample Input

(+(*(+(*ab)(+a))b))
-3 1 1 0
(+xyy) -2 1 0

Sample Output

(*ab)
(*abb)
y

Submit

Source: South Eastern European Regional Contest 2011