You are given two string and of length and respectively.
Find a strictly increasing array of integers where is the index of the character in that matches with .
Among all possible arrays find the one where the summation of the absolute difference between each adjacent element is maximum. is maximum. If there are multiple answers find the one where the summation of the elements in the array is maximum. is maximum.
If such an array does not exist, print .
The first line of input will contain two integers and .
The second line will contain a string of length .
The third line will contain a string of length .
Print integers the array you have found. If such an array does not exist, print .
Input | Output |
---|---|
4 2 BABC AC | 2 4 |
Input | Output |
---|---|
5 2 ABCBC BD | -1 |
Input | Output |
---|---|
6 3 AXZXYZ AXZ | 1 4 6 |