Задано две строки \(s\) и \(t\). Обе строки имеют длину \(n\) и состоят из строчных букв латинского алфавита. Символы в строках пронумерованы от \(1\) до \(n\).
Вы можете последовательно применять следующую операцию любое количество раз (возможно, нулевое):
- поменять местами любые два смежных (соседних) символа строки \(s\) (то есть для любого \(i = \{1, 2, \dots, n - 1\}\) можно поменять местами \(s_i\) и \(s_{i + 1})\).
Нельзя применять операции к строке \(t\). Операции применяются к строке \(s\) одна за другой.
Ваша задача — получить строку \(t\) из строки \(s\). Необходимо найти любой способ сделать это с любым количеством операций, не превышающим \(10^4\).
Нет необходимости минимизировать количество операций, необходимо найти любую последовательность операций длины \(10^4\) или меньше, чтобы превратить строку \(s\) в строку \(t\).
Выходные данные
Если невозможно при получить строку \(t\) при помощи применения описанных выше операций, выведите «-1».
Иначе в первой строке выведите одно целое число \(k\) — количество ходов, необходимое для того, чтобы превратить \(s\) в \(t\). Заметьте, что \(k\) должно быть целым числом от \(0\) до \(10^4\) включительно.
Во второй строке выведите \(k\) целых чисел \(c_j\) (\(1 \le c_j < n\)), где \(c_j\) означает, что \(j\)-й операций вы меняете местами \(s_{c_j}\) и \(s_{c_j + 1}\).
Если нет необходимости применять операции вообще, выведите одно целое число \(0\) и либо оставьте вторую строку пустой, либо не выводите ее вообще.
Примечание
В первом тестовом примере строка \(s\) изменяется следующим образом: «abcdef» \(\rightarrow\) «abdcef» \(\rightarrow\) «abdcfe» \(\rightarrow\) «abdfce» \(\rightarrow\) «abdfec».
Во втором тестовом примере невозможно получить из строки \(s\) строку \(t\) при помощи применения любых допустимых операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
abcdef
abdfec
|
4
3 5 4 5
|
|
2
|
4
abcd
accd
|
-1
|