Kevin and the Remote Car

Interview

Time limit2sMemory limit1024 MB

Summary

Given two digit strings, decide whether the first can be reduced to the second by repeatedly replacing adjacent digits with their sum modulo 10.

Level: Medium5 of 10
Topics: Greedy, String, Math
Solved: No attempts yet

Problem

Mrs. Hess gave Kevin a remote-controlled car as a thank-you for helping shovel snow. She had picked it up by mistake at the airport.

After playing with it for a while, Kevin wanted to see what was inside. Taking it apart turned out to be harder than he expected. Inside were a tricky electronic lock and two strings of digits. The instructions said he had to solve a difficult puzzle to open the case. The lock lets him choose any two adjacent digits in the first string and replace them with a single digit equal to the remainder of their sum divided by ten. If the first string ends up exactly equal to the second string, the lock opens. Each operation shortens the first number, and there is no way to undo a step, so Kevin gets only one attempt.

Help Kevin figure out whether the lock can be opened, at least in theory.

Input

The first line contains a string $a$ ( $1 \le |a| \le 200\,000$ ), the first number. The second line contains a string $b$ ( $1 \le |b| \le 200\,000$ ), the second number. Both strings may contain leading zeros.

Output

Print YES if the first number can be turned into the second, and NO otherwise.

Examples2

Example 1
Input
```
123456
326
```
Expected output
```
YES
```
Example 2
Input
```
123456
12345
```
Expected output
```
NO
```