DNA Transformation#4176
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 , composed of characters from the set \{A, G, C, T\}. The basic transformation that the biologists can perform involves reversing a substring from the -th to the -th character (where integers and satisfy 1 \leq l \leq r \leq n). Thus, the sequence a_1 a_2 \ldots a_l a_{l+1} \ldots a_{r-1} a_r \ldots a_n becomes a_1 a_2 \ldots a_r a_{r-1} \ldots a_{l+1} a_l \ldots 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.
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 . 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.
On the first line of the output, print the number of transformations in your solution. The number must be non-negative and must not exceed .
Then, print 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 -th step, respectively.
Example 1