Processing math: 100%

Problem B. Bouncing pairs

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

Let there be two strings A and B, consisting of digits and lowercase Latin characters.

On the string A, we define the operation SWAP(i,i+1), which consists in exchanging the characters at positions i and i+1.

It is required to determine the minimum number of such operations for transforming string A to string B.

Input format

Input contains two strings: A and B.

Output format

Output must contain a single integer.

Constraints

It is guaranteed that the required transformation can be performed.

Line lengths do not exceed 2105.

Sample tests

No. Standard input Standard output
1
abababababab
babababababa
6
2
abc
bca
2

0.058s 0.010s 13