Fractionalization

In modern western square dancing, the dancers execute calls, according to definitions they have memorized. Each call is either an atomic unit, or made up of a sequence of other calls. Experienced dancers are expected to be able to dance not only all the calls they have learned, but also fractions of calls. For example, given the list of calls and their definitions below:

    Trade:          Hinge Hinge
    CenterTwoTrade: CenterTwoHinge CenterTwoHinge
    SpinTheTop:     Trade FanTheTop
    HotFootSpin:    FanTheTop CenterTwoTrade SpinTheTop

the call "HotFootSpin" has three parts: "FanTheTop" (an atomic unit), "CenterTwoTrade" (which has two parts), and "SpinTheTop" (which also has two parts). Each part of a call is given equal weight, regardless of how many parts it itself is made up of. So, for example, "1/3 HotFootSpin" is simply "FanTheTop", and "2/3 HotFootSpin" is "FanTheTop" followed by "CenterTwoTrade". Other fractionalizations of "HotFootSpin" are also possible. For example, even though the call has three parts, the dancers could do "1/2 HotFootSpin" by doing the first part, followed by 1/2 of the second part. So "1/2 HotFootSpin" is "FanTheTop" followed by "CenterTwoHinge".

Now consider "3/4 HotFootSpin". After doing the first 2/3 of the call, the dancers would have 1/12 (3/4 - 2/3) left to do. This final 1/12 of the call is 1/4 of the final third: "1/4 SpinTheTop". "SpinTheTop" has only two parts, so 1/4 of it is 1/2 of its first part: "1/2 Trade", which is "Hinge". Therefore, "3/4 HotFootSpin" is "FanTheTop", followed by "CenterTwoTrade", followed by "Hinge".

You will be given a String[] definitions, a fraction m/n, and a String danceCall. Each element of definitions will be formatted as follows: the name of the call being defined, followed by a single colon (':'), followed by a single space, and then a list of 2 or more calls each separated by a single space. The name of each call will consist solely of lowercase and uppercase letters and is case-sensitive. Calls that appear in the definitions of other calls, but do not have a definition themselves, are atomic units and cannot be fractionalized. No definition can refer to a call that is defined later in the list of definitions.

You are to return the list of calls as a String[] that the dancers should perform in order to execute "m/n danceCall". Whenever the dancers are to execute a call in its entirety, simply name that call rather than listing its parts. Do not use other definitions to simplify the list of calls you return. For example, given the following definitions:

    A: One Two
    B: One Two Three
    C: One Two Three Four

for "3/4 C", you should return { "One", "Two", "Three" }, and not { "B" }. If the given fractionalization is not possible, return a String[] with the single element: "ILLEGAL".