Вы когда-нибудь слышали о проблеме расстояния редактирования? По двум строкам из английских букв необходимо найти минимальное количество операций, необходимых для преобразования первой строки во вторую. Одной операцией может быть:

• вставка символа в последовательность в любом месте,
• удаление любого символа из последовательности,
• замена одного символа другим.

Все в нашем университете очень любят эту задачу, может быть, даже слишком, поэтому мы решили создать задачу попроще! Вам даны две строки s = s1...sn, t = t1...tm и целое число k. Определите, меньше или равно k расстояние редактирования между строками. Если это так, вас также просят указать любую последовательность минимально возможного количества операций для преобразования первой строки во вторую.

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

Первая строка содержит количество тестов z (1 ≤ z ≤ 100). Далее следуют описания тестов.

Первая строка каждого теста содержит три целых числа n, m, k (1 ≤ n, m ≤ 106, 0 ≤ k ≤ 1000) — длины строк и параметр из описания задачи.

Во второй строке находится строка длины n, состоящая из строчных латинских букв - строка s из описания задачи.

В третьей строке находится строка длины m, состоящая из строчных латинских букв - строка t из описания задачи.

Суммарная длина всех строк во всех тестах не превышает 107.

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

Для каждого теста, если расстояние редактирования больше k, выведите одну строку, содержащую слово "NO". В противном случае первая строка должна содержать слово "YES", а следующие строки должны описывать ответ следующим образом:

Во второй строке выведите минимальное количество r операций, необходимых для преобразования s в t. В следующих r строках выведите операции, по одной в строке.

• Чтобы вставить символ c в последовательность размером w в позицию p (1 ≤ p ≤ w + 1), выведите INSERT p c.
• Чтобы удалить символ из последовательности размера w в позиции p (1 ≤ p ≤ w), выведите DELETE p .
• Чтобы заменить символ в последовательности размером w в позиции p (1 ≤ p ≤ w) символом c, выведите REPLACE p c.