Дана строка s, состоящая из больших латинских букв. Обозначим ее текущую длину как |s|. За один ход разрешается применить к ней одну из следующих операций:
- INSERT pos ch — вставить букву ch в строку s в позицию pos (1 ≤ pos ≤ |s| + 1, A ≤ ch ≤ Z). Буква ch становится pos-ым символом строки s, при этом буквы сдвигаются, и длина строки увеличивается на 1.
- DELETE pos — удалить из строки s символ с номером pos (1 ≤ pos ≤ |s|) При этом буквы сдвигаются, и длина строки уменьшается на 1.
- REPLACE pos ch — буква в позиции pos строки s заменяется на ch (1 ≤ pos ≤ |s|, A ≤ ch ≤ Z). При этом длина строки не меняется.
Ваша задача — найти, за какое наименьшее количество ходов можно получить из строки s строку t. Так же требуется найти последовательность действий, приводящую к нужному результату.
Выходные данные
В первую строку выведите количество ходов k в найденной последовательности операций. Это число должно быть наименьшим возможным. Далее выведите k строк по одной операции в каждой. Операции выводите в описанном выше формате. Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
ABA
ABBBA
|
2
INSERT 3 B
INSERT 4 B
|
|
2
|
ACCEPTED
WRONGANSWER
|
10
REPLACE 1 W
REPLACE 2 R
REPLACE 3 O
REPLACE 4 N
REPLACE 5 G
REPLACE 6 A
INSERT 7 N
INSERT 8 S
INSERT 9 W
REPLACE 11 R
|