Under construction

Still being built. Things may change

Bet

Time limit2sMemory limit1024 MB

Summary
Given two strings of letters and digits, decide whether both could come from one original string by replacing some Roman numeral substrings with Arabic numbers.
Level

Medium7 of 10

Topics
Dynamic programming, String matching, String
Solved
No attempts yet

Problem

To free Anakin Skywalker and acquire a hyperdrive, Qui-Gon Jinn made a bet with Watto about who would win the Boonta Eve race. Few people know that Watto did what is often done on Tatooine: he cheated when the bet was made.

To officially register a dispute on Tatooine, the parties must go to the appropriate official, who issues two identical receipts. Both receipts carry the same string of characters, which in a faraway galaxy, many years later, will be called Latin letters.

Watto's trick was this. His acquaintance, the official, drew up nonstandard receipts. To stay within the law, he first wrote two correct receipts and then altered them. He picked an arbitrary substring that is a valid representation of a natural number in Roman numerals. Then he replaced that substring with the same number written in Arabic numerals, with no leading zeros. The official repeated this until no suitable substrings remained.

Qui-Gon Jinn never got cheated by Watto, so nobody ever mentioned this trick. Can you, a resident of a faraway galaxy, check whether the texts on the two nonstandard receipts could have come from one string?

Input

The first and second lines of the input each contain a string of lowercase Latin letters and digits. The length of each string does not exceed 10510^5. It is guaranteed that no substring of these strings is a valid Roman numeral representation. It is guaranteed that every substring that is a natural number does not exceed 200200 in value. It is guaranteed that no all-digit substring starts with zero.

Output

Print YES if the two strings could have been obtained from one string, and NO otherwise.

Hint

In Roman numerals, I is 1, V is 5, X is 10, L is 50, C is 100, D is 500, and M is 1000. To write a number correctly, write the thousands first, then the hundreds, then the tens, and finally the units. Digits may repeat, but no more than three times. A smaller digit may be written to the left of a larger one, in which case it is subtracted from the larger one. In that case the smaller digit cannot be repeated. There are six subtractive forms: IV is 44, IX is 99, XL is 4040, XC is 9090, CD is 400400, and CM is 900900. No other subtractive forms are allowed.

Examples2

  1. Example 1

    Input
    skywa50kera21
    skywa50kera12
    
    Expected output
    YES
    
  2. Example 2

    Input
    qu1gonj20
    qu1gonj200
    
    Expected output
    NO