DNA Transformation
Biologists at the Advanced Cellular Mechanics Lab. (ACM Lab.) are conducting research in genomics and DNA. Recently, they have developed a technology that enables relatively inexpensive transformations of a DNA strand.
Consider a DNA strand as a sequence of length n, composed of characters from the set {A, G, C, T}. The basic transformation that the biologists can perform involves reversing a substring from the l-th to the r-th character (where integers l and r satisfy 1 ≤ l ≤ r ≤ n). Thus, the sequence a_1a_2...a_la_{l+1}...a_{r−1}a_r...a_n becomes a_1a_2...a_ra_{r−1}...a_{l+1}a_l...a_n.
The biologists are now developing a software-hardware system to perform these DNA transformations. One of its functions is to convert an initial DNA strand into a desired one.
Your task is to write a program that, given the initial and desired DNA strands, determines the sequence of elementary transformations needed to achieve this.
Input
The first line of the input contains the initial DNA strand, and the second line contains the desired DNA strand. Both strands have the same length, which does not exceed 5000. Each strand consists solely of characters from the set {A, G, C, T}.
It is guaranteed that a sequence of transformations exists to achieve the desired strand.
Output
On the first line of the output, print the number k of transformations in your solution. The number k must be non-negative and must not exceed 4999.
Then, print k lines, each describing a transformation. Each line should contain two numbers: l_i and r_i, which are the left and right endpoints of the segment to be reversed at the i-th step, respectively.