시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.3 초 512 MB 3 2 2 66.667%

문제

Researchers have discovered a new form of life they have named Gnalcats. Gnalcats have a very strange form of DNA and proteins but the researchers have understood how they work. They are now trying to classify species of Gnalcats by comparing their DNA.

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 − . . .). 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):

base input protein output protein
C a − X a − a − X
D a − X X
L a − X b − X (if a is the complex amino-acid <b, c>)
fail (if a is a simple amino-acid)
P a − b − X c − X where c is the complex amino-acid <a, b>
R a − X c − X (if a is the complex amino-acid <b, c>)
fail (if a is a simple amino-acid)
S a − b − X b − a − X
U a − X b − c − X (if a is the complex amino-acid <b, c>)
fail (if a is a simple amino-acid)

For example, the gene PSDSPCRPSDUL transforms a protein like this:

  • the input protein is a − b − c − d − e − f − . . .
  • then applying the rule for the first P produces: <a, b> − c − d − e − f − . . .
  • then applying the rule for S produces: c − <a, b> − d − e − f − . . .
  • then D gives: <a, b> − d − e − f − . . .
  • then S gives: d − <a, b> − e − f − . . .
  • then P gives: <d,<a, b>> − e − f − . . .
  • then C gives: <d,<a, b>> − <d,<a, b>> − e − f − . . .
  • then R gives: <a, b> − <d,<a, b>> − e − f − . . .
  • then P gives: <<a, b>,<d,<a, b>>> − e − f − . . .
  • then S gives: e − <<a, b>,<d,<a, b>>> − f − . . .
  • then D gives: <<a, b>,<d,<a, b>>> − f − . . .
  • then U gives: <a, b> − <d,<a, b>> − f − . . .
  • and finally L gives: a − <d,<a, b>> − f − . . .

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.

입력

The input consists of two lines, each representing a Gnalcats gene.

출력

The output consists of a single word: “True” if the genes are equivalent, “False” otherwise.

제한

Each gene contains at least one base. The sum of the length of input genes is not greater than 104.

예제 입력 1

PU
SS

예제 출력 1

True

These genes do nothing: they always transforms a protein into the exact same protein.

예제 입력 2

L
R

예제 출력 2

True

These genes always fail because both L and R bases fail on simple amino acids.

예제 입력 3

PSPCRSL
PS

예제 출력 3

True

예제 입력 4

U
C

예제 출력 4

False

예제 입력 5

PL
PR

예제 출력 5

False