Morphic is a tree that grows very rapidly, bringing happiness to its owner. It has a single trunk consisting of a number of cells stacked one on top of another. Each cell has one of n possible colors which determine the way it mutates during the night, while nobody can see it. Florists denote these colors by the first n small letters of the English alphabet and know exactly into how many cells, and of what colors, a cell of each color divides. In fact, they have wrote their knowledge down simply with n nonempty words, each word representing the resulting sequence of colors.
A seed of a Morphic has a single cell of color a and is rooted firmly in the ground. As long as the Morphic is still alive, each night all its cells simultaniously morph according to the aforementioned rules, possibly causing an exponential growth because each new cell is of the same size as the original one.
For example, if rules say that a becomes ab, and b becomes ca, then after two nights a seed will evolve to a trunk consisting of 4 cells: abca.
Therefore the top of a Morphic is usually hidden in clouds. The only way to tell if it is still alive is to check if visible part of the trunk is changing colors. In order to do so, one can build enormously high (yet still of constant height) tower, and watch from its top a fixed fragment of the trunk.
As you can easily see, it is either suficient to observe first k cells from the bottom for some fixed k, or no matter how high the tower is, you will not be able to tell for sure if a Morphic died. The latter happens when for every k, rules cause the k-th cell to eventually stop changing colors, even though the
tree is still alive and mutating.
To prevent waste of money on building such enormous towers, you are to write a program that
determines if it is possible to monitor health of a Morphic.