There are different kinds of pizza, and listing all of them down on a paper is not an easy job. Fortunately, we can describe them with features. For example, a pizza with
#{Hawaiian}
pineapple,ham
#{BBQBeef}
beef,BBQsauce
Sometimes, we can describe a feature with other features. For example,
#{SixFamilies} tag is described bypork,sausage,#{BBQBeaf},greenPepper,#{Mushroom}
pork,sausage,beef,BBQsauce,greenPepper,mushroom,onion
The description of a feature will not start with another feature.
The first line of the input file contains an integer T (1<= T<= 100) indicating the number of test cases.
For each test case, first line contains three integers n, L, R (1<= n<= 100; 1<= L<= R<= 100000; 0<= R-L<= 100). Then n lines follow. Each line contains two strings Name, Expr separated by exactly one space. Both Name and Expr will not contain any whitespaces. The last line contains a $Name$ that you are going to expand. All expressions are valid. That is, you can always find a description of a feature in the list. A Name consists of lower-case and upper-case letters. An Expr is a comma-separated list of ingredients, where each ingredient is either a word of lower/upper case letters or #{Name}. The length of Name and Expr will not exceed 100.
For each test case, please output the desired substring in a line. You may assume that the length of expanded version contains at least R characters (may be infinite!)
2
3 1 10
Seafood shrimp,octopus
SeafoodEX seashell,#{Seafood},fish
FishFood seaweed,#{SeafoodEX}
FishFood
1 2 7
XD XD,#{XD},XD,#{XD},XD
XD
seaweed,se D,XD,X
Migrated from old NTUJ.
Tmt, Ferng
| No. | Testdata Range | Score |
|---|