406695: GYM102501 D Gnalcats
Description
A gene of their DNA is a sequence of bases. These genes operate on proteins, which are extremely long chains of amino-acids ($$$a - b - c - \ldots$$$). Amino-acids are either simple or complex (composed of two other amino-acids). Proteins always contain several billions of amino-acids.
Genes operate on proteins in the following way: the seven different bases (C, D, L, P, R, S, U) correspond to different transformations on the protein. The result of the operation of a gene on a protein is obtained as the combination of the individual transformations by each base of the gene: the first base of the gene transforms the input protein, the resulting protein is then transformed according to the second base of the gene, and so on. Life is not perfect and thus one of these transformations may fail, in which case the overall transformation fails. If, at any point in the transformation, the protein is reduced to a chain of three or fewer amino-acids (simple or complex) then the transformation fails.
The effect of each base is described in the following table where $$$X$$$ denotes the tail of the protein, while $$$a$$$, $$$b$$$, and $$$c$$$ are amino-acids (either simple or complex):
$$$$$$ \begin{array}{c r l} \hline \text{base} & \text{input protein} & \text{output protein} \\ \hline \textbf{C} & a-X & a-a-X\\ \textbf{D} & a-X & X\\ \textbf{L} & a-X & \left\{\begin{array}{l l} b-X & \text{if $a$ is the complex amino-acid $\langle b, c\rangle$} \\ \text{fail} & \text{if $a$ is a simple amino-acid} \end{array}\right. \\ \textbf{P} & a-b-X & c-X \text{ where $c$ is the complex amino-acid $\langle a, b\rangle$}\\ \textbf{R} & a-X & \left\{\begin{array}{l l} c-X & \text{if $a$ is the complex amino-acid $\langle b, c\rangle$} \\ \text{fail} & \text{if $a$ is a simple amino-acid} \end{array}\right. \\ \textbf{S} & a-b-X & b-a-X\\ \textbf{U} & a-X & \left\{\begin{array}{l l} b-c-X & \text{if $a$ is the complex amino-acid $\langle b, c\rangle$} \\ \text{fail} & \text{if $a$ is a simple amino-acid} \end{array}\right. \\ \hline \end{array} $$$$$$
For example, the gene PSDSPCRPSDUL transforms a protein like this:
- the input protein is $$$a - b - c - d - e - f - \ldots$$$
- then applying the rule for the first P produces: $$$\langle a, b \rangle - c - d - e - f - \ldots$$$
- then applying the rule for S produces: $$$c - \langle a, b \rangle - d - e - f - \ldots$$$
- then D gives: $$$\langle a, b\rangle - d - e - f - \ldots$$$
- then S gives: $$$d - \langle a, b\rangle - e - f - \ldots$$$
- then P gives: $$$\langle d, \langle a, b\rangle \rangle - e - f - \ldots$$$
- then C gives: $$$\langle d, \langle a, b\rangle \rangle - \langle d, \langle a, b\rangle \rangle - e - f - \ldots$$$
- then R gives: $$$\langle a, b\rangle - \langle d, \langle a, b\rangle \rangle - e - f - \ldots$$$
- then P gives: $$$\langle \langle a, b\rangle , \langle d, \langle a, b\rangle \rangle \rangle - e - f - \ldots$$$
- then S gives: $$$e - \langle \langle a, b\rangle , \langle d, \langle a, b\rangle \rangle \rangle - f - \ldots$$$
- then D gives: $$$\langle \langle a, b\rangle , \langle d, \langle a, b\rangle \rangle \rangle - f - \ldots$$$
- then U gives: $$$\langle a, b\rangle - \langle d, \langle a, b\rangle \rangle - f - \ldots$$$
- and finally L gives: $$$a - \langle d, \langle a, b\rangle \rangle - f - \ldots$$$
You are given two genes, and you must decide whether they are equivalent. Two genes are equivalent if for every input protein composed of at least one billion of simple amino-acids, either the application of both genes produces the same output protein, or both applications fail.
InputThe input consists of two lines, each representing a Gnalcats gene.
Limits
Each gene contains at least one base. The sum of the length of the input genes is not greater than $$$10^4$$$.
OutputThe output consists of a single word: "True" if the genes are equivalent, "False" otherwise.
ExamplesInputPU SSOutput
TrueInput
L ROutput
TrueInput
PSPCRSL PSOutput
TrueInput
U COutput
FalseInput
PL PROutput
FalseNote
Sample Explanation 1
These genes do nothing: they always transform a protein into the exact same protein.
Sample Explanation 2
These genes always fail because both L and R bases fail on simple amino acids.