Algorithms and Data Structures

Equivalent strings

Let’s have a new definition of string equivalence (~). Two strings a and b are equivalent if they have the same length and one of the two cases holds:
  1. a is identical to b (a == b)
  1. If we split a into two strings of the same size a1 and a2, and string b into two strings of the same size b1 and b2, then:
    1. a1 is equivalent to b1, and a2 is equivalent to b2 (a1 ~ b1 and a2 ~ b2)
    2. a1 is equivalent to b2, and a2 is equivalent to b1 (a1 ~ b2 and a2 ~ b1)
Given two strings a and b, you are asked to find out if these two strings are equivalent.

Input

The first line of the input contains the string a (1 ≤ |a| ≤ ).
The second line of the input contains the string b (1 ≤ |b| ≤ ).
Both of the lengths |a| and |b| are a power of 2.

Output

The program should print Yes if a is equivalent to b, and No otherwise.

Examples

Input
Output
bbcb bcbb
Yes
bbaa baba
No

Explanation

  1. bbcb → bb + cb, bcbb → bc + bb ⇒ bb is equivalent to bb, while cb is equivalent to bc as we can split cb → c + b, and bc → b + c ⇒ they are equivalent.
  1. bbaa → bb + aa, baba → ba + ba ⇒ no pairs are equivalent because if we split them further, we’ll need to compare aa to any of the ba-s, and therefore, as there are no b-s in aa, the two strings will not be equivalent.
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue