Problem B. Banner scrolling

Author:A. Klenin, I. Tuphanov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Young web developer Vasya was hired by "Dalstolb" company. Company maintains a popular news website with many advertisement banners. Marketing department of "Dalstolb" has proposed a new idea for animated transition between two text messages on the banner.

Message is a single line of characters. First message has length L1, second has length L2 ≥ L1. Since the banner width is only enough to fit L1 characters, the message after the transition should contain any substring the second message of length L1. Transition should be performed as a series of animation frames. Each frame, message is either scrolled to the right by removing leftmost character and appending arbitrary new character from the right, or scrolled to the left by removing rightmost character and appending arbitrary new character from the left.

You program must, given two messages, find a shortest possible transition between them.

Input file format

First line of the input file contains the first message. Second line of the input file contains the second message. Messages are composed of small Latin letters.

Output file format

First line of output file must contain integer N — minimum number of frames. Following N lines must contain two-character string each — frame descriptions. First character must be either L or R, denoting right or left scrolling correspondingly. Second character must be a small Latin letter which should be appended to the message.

Constraints

1 ≤ L1 ≤ L2 ≤ 2000;

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
acm
solutionaccepted
1
Ln
2
vvostoker
vladivostok
4
Rz
Li
Ld
La

0.077s 0.009s 13