# Make It Large

Limits 1s, 512 MB

You are given two string $S$ and $T$ of length $n$ and $m$ respectively.

Find a strictly increasing array of $m$ integers $A_1, A_2, …, A_m$ where $A_i$ is the index of the character in $S$ that matches with $T_i.$ $i.e$ $S_{A_i} = T_i$.

Among all possible arrays find the one where the summation of the absolute difference between each adjacent element is maximum. $i.e$ $\displaystyle\sum_{i = 1}^{i < m} A_{i+1} - A_{i }$ is maximum. If there are multiple answers find the one where the summation of the elements in the array is maximum. $i.e$ $\displaystyle\sum_{i = 1}^{i \leq m} {A_i}$ is maximum.

If such an array does not exist, print $-1$.

## Input

The first line of input will contain two integers $n$ and $m$ $(1 \leq n, m \leq 2 * 10^5)$.

The second line will contain a string $S$ of length $n$.

The third line will contain a string $T$ of length $m$.

## Output

Print $m$ integers $A_1, A_2, …, A_m$ the array you have found. If such an array does not exist, print $-1$.

## Samples

InputOutput
4 2
BABC
AC

2 4

InputOutput
5 2
ABCBC
BD

-1

InputOutput
6 3
AXZXYZ
AXZ

1 4 6


Login to submit.

### Statistics

62% Solution Ratio
FAHIM.ctgEarliest, Nov '22
jahid_hridoyFastest, 0.0s
nusuBotLightest, 4.9 MB
FAHIM.ctgShortest, 979B
Toph uses cookies. By continuing you agree to our Cookie Policy.