M and A

Decide whether S can be interleaved character by character from a subsequence of S and a subsequence of T, both of the same length as S.

Medium6Dynamic programmingStringInterviewNo attempts yetTime limit5sMemory limit512 MB

Problem

The head of company S is preparing an M&A with company T. M&A is short for "Mergers and Acquisitions". He claims in public that the two company names get mixed into a new one, but what he actually wants is to keep the original name S after the merger.

By his rule, the name after the M&A is built as follows.

Let s be a subsequence of S and let t be a subsequence of T. The name after the M&A is a string of length S|S| made by laying out the characters of s and t alternately, that is s0t0s1t1s_0 t_0 s_1 t_1 \cdots or t0s0t1s1t_0 s_0 t_1 s_1 \cdots, where sks_k is the kk-th (0-based) character of the string s. Positions 0, 2, 4, and so on of the result are filled in order by one of the two subsequences, and positions 1, 3, 5, and so on are filled in order by the other. When S|S| is odd, the lengths of the two subsequences differ by 1.

A subsequence is a string obtained by erasing zero or more characters from the original string. For example "abe", "abcde" and "" (the empty string) are all subsequences of "abcde".

You are a programmer at the acquiring company. Write a program that decides whether the original name S can be produced by mixing the two company names.

Input

The input is a single test case on two lines.

The first line contains the name S of the company you work for. The second line contains the name T of the company targeted by the M&A. S and T are non-empty and have the same length, and that length is at most 1,000. Both names consist of lowercase English letters only.

Output

Print Yes on the first line if the original company name S can be produced by mixing the two names. Otherwise print No.