Cutting into three pieces

Interview

Time limit0.2sMemory limit256 MB

Summary

Decide whether the second string can be cut into three non-empty pieces and reordered to equal the first string, printing the shortest-first valid split.

Level: Medium5 of 10
Topics: String, Brute force, Implementation
Solved: No attempts yet

Problem

You are given two strings. Cut the second string into three non-empty pieces, then concatenate the three pieces in an order of your choice. Decide whether the result can equal the first string.

Each piece is a contiguous part of the second string, and the three pieces may be placed in any order.

Input

The first line contains the first string. The second line contains the second string.

Both strings are non-empty, have the same length, and consist of lowercase latin letters only. The length is at most $5\,000$ . Every letter occurs the same number of times in both strings.

Output

If the first string can be built this way, print YES on the first line, then print the three pieces on the next three lines, one per line, in the order that concatenates to the first string. No piece may be empty. Otherwise print NO on a single line.

If several cuts work, print the one whose first piece is shortest. If several of those remain, print the one whose second piece is shortest.

Examples2

Example 1
Input
```
beast
betas
```
Expected output
```
YES
be
as
t
```
Example 2
Input
```
royalitem
romeitaly
```
Expected output
```
NO
```