D. Получаем строку
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Дана строка 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. Так же требуется найти последовательность действий, приводящую к нужному результату.

Входные данные

В первой строке записана s, во второй строке записана t. Строки состоят только из больших латинских букв, их длины — положительные числа от 1 до 1000.

Выходные данные

В первую строку выведите количество ходов k в найденной последовательности операций. Это число должно быть наименьшим возможным. Далее выведите k строк по одной операции в каждой. Операции выводите в описанном выше формате. Если решений несколько, выведите любое.

Примеры
Входные данные
ABA
ABBBA
Выходные данные
2
INSERT 3 B
INSERT 4 B
Входные данные
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