Score : $300$ points

问题陈述

你有两个由小写英文字母组成的字符串 $S$ 和 $T$。这里，$S$ 和 $T$ 的长度相等。

设 $X$ 为一个空数组，并重复以下操作直到 $S$ 等于 $T$：

• 改变 $S$ 中的一个字符，并将 $S$ 追加到 $X$ 的末尾。

找到以这种方式获得的元素数量最少的字符串数组 $X$。如果有多个这样的数组具有最少的元素数量，请找到它们中字典序最小的一个。

字典序在字符串数组上是如何定义的？

长度为 $N$ 的字符串 $S = S_1 S_2 \ldots S_N$ 比长度为 $N$ 的字符串 $T = T_1 T_2 \ldots T_N$ 字典序更小，如果存在一个整数 $1 \leq i \leq N$ 满足以下两个条件：

• $S_1 S_2 \ldots S_{i-1} = T_1 T_2 \ldots T_{i-1}$
• $S_i$ 在字母顺序中比 $T_i$ 更早。

具有 $M$ 个元素的字符串数组 $X = (X_1,X_2,\ldots,X_M)$ 比具有 $M$ 个元素的字符串数组 $Y = (Y_1,Y_2,\ldots,Y_M)$ 字典序更小，如果存在一个整数 $1 \leq j \leq M$ 满足以下两个条件：

• $(X_1,X_2,\ldots,X_{j-1}) = (Y_1,Y_2,\ldots,Y_{j-1})$
• $X_j$ 比 $Y_j$ 字典序更小。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given two strings $S$ and $T$ consisting of lowercase English letters. Here, $S$ and $T$ have equal lengths.

Let $X$ be an empty array, and repeat the following operation until $S$ equals $T$:

• Change one character in $S$, and append $S$ to the end of $X$.

Find the array of strings $X$ with the minimum number of elements obtained in this way. If there are multiple such arrays with the minimum number of elements, find the lexicographically smallest one among them.

What is lexicographical order on arrays of strings?

A string $S = S_1 S_2 \ldots S_N$ of length $N$ is lexicographically smaller than a string $T = T_1 T_2 \ldots T_N$ of length $N$ if there exists an integer $1 \leq i \leq N$ such that both of the following are satisfied:

• $S_1 S_2 \ldots S_{i-1} = T_1 T_2 \ldots T_{i-1}$
• $S_i$ comes earlier than $T_i$ in alphabetical order.

An array of strings $X = (X_1,X_2,\ldots,X_M)$ with $M$ elements is lexicographically smaller than an array of strings $Y = (Y_1,Y_2,\ldots,Y_M)$ with $M$ elements if there exists an integer $1 \leq j \leq M$ such that both of the following are satisfied:

• $(X_1,X_2,\ldots,X_{j-1}) = (Y_1,Y_2,\ldots,Y_{j-1})$
• $X_j$ is lexicographically smaller than $Y_j$.

Constraints

• $S$ and $T$ are strings consisting of lowercase English letters with length between $1$ and $100$, inclusive.
• The lengths of $S$ and $T$ are equal.

Input

The input is given from Standard Input in the following format:

$S$

$T$

Output

Let $M$ be the number of elements in the desired array. Print $M + 1$ lines.

The first line should contain the value of $M$.

The $i + 1$-th line $(1 \leq i \leq M)$ should contain the $i$-th element of the array.

Sample Input 1

adbe
bcbc

Sample Output 1

3
acbe
acbc
bcbc

Initially, $S =$ adbe.

We can obtain $X = ($ acbe $,$ acbc $,$ bcbc $)$ by performing the following operations:

• Change $S$ to acbe and append acbe to the end of $X$.

• Change $S$ to acbc and append acbc to the end of $X$.

• Change $S$ to bcbc and append bcbc to the end of $X$.

Sample Input 2

abcde
abcde

Sample Output 2

0

Sample Input 3

afwgebrw
oarbrenq

Sample Output 3

8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq