Deoxyribonucleic Acid

Interview

Time limit2sMemory limit1024 MB

Summary

Given one DNA chain s and a gene t, determine whether t appears in s or in its complementary chain read in the opposite direction.

Level: Easy3 of 10
Topics: String, String matching
Solved: No attempts yet

Statement

Deoxyribonucleic acid (DNA) is one of two types of nucleic acids. It stores genetic information, passes it from generation to generation, and carries out the genetic program that governs the development and functioning of living organisms.

DNA is a pair of polymer chains. Each link in a chain is a nucleotide of one of four kinds: adenine ( $A$ ), thymine ( $T$ ), guanine ( $G$ ), or cytosine ( $C$ ). Each chain has a direction, and the two chains of one DNA molecule always run in opposite directions. The last nucleotide of one chain lies opposite the first nucleotide of the other, the second-to-last lies opposite the second, and so on.

DNA always follows the complementarity principle. Adenine always pairs with thymine, and the reverse holds too. Guanine always pairs with cytosine. For example, the chain AGC is complementary to the chain GCT.

In a top-secret lab, the full DNA of Misha was read, but only one of the two chains, $s$ , was given to Misha. Help Misha find out whether he has the superman gene, which is written in the DNA as a substring $t$ . Keep in mind that the gene may be written on the chain that Misha did not receive from the lab.

Input

The first line contains a string $s$ of length at most 200. The second line contains a string $t$ of length at most 20. Both strings consist only of the letters A, T, G, and C.

Output

Print Yes if Misha has the superman gene in his DNA, and No otherwise.

Examples3

Example 1
Input
```
ATGCATGC
TGC
```
Expected output
```
Yes
```
Example 2
Input
```
ATGCATGC
GCATGCAT
```
Expected output
```
Yes
```
Example 3
Input
```
ATGCATGC
TTT
```
Expected output
```
No
```