편집 거리(edit distance) 문제에 대해 들어본 적이 있나요? 소문자 영어 알파벳으로 이루어진 두 문자열이 주어졌을 때, 첫 번째 문자열을 두 번째 문자열로 변환하는 데 필요한 최소 연산 횟수를 구해야 합니다. 단일 연산은 다음 중 하나일 수 있습니다:
- 문자열의 임의의 위치에 문자 삽입
- 문자열에서 임의의 문자 삭제
- 문자를 다른 문자로 대체
우리 대학의 모든 사람은 이 문제를 매우 좋아합니다. 어쩌면 지나치게 좋아할지도 모릅니다. 그래서 우리는 더 쉬운 문제를 만들기로 했습니다! 두 문자열 $s = s_1 \dots s_n$, $t = t_1 \dots t_m$과 정수 $k$가 주어집니다. 두 문자열 사이의 편집 거리가 $k$ 이하인지 확인하세요. 만약 그렇다면, 첫 번째 문자열을 두 번째 문자열로 변환하는 최소 횟수의 연산 순서도 함께 제시해야 합니다.
입력
입력의 첫 번째 줄에는 테스트 케이스의 수 $z$ ($1 \le z \le 100$)가 주어집니다. 각 테스트 케이스에 대한 설명이 이어집니다.
각 테스트 케이스의 첫 번째 줄에는 세 정수 $n, m, k$ ($1 \le n, m \le 1\,000\,000$, $0 \le k \le 1000$)가 주어지며, 이는 문제 설명에 나오는 문자열의 길이와 매개변수를 의미합니다.
두 번째 줄에는 문제 설명에 나오는 문자열 $s$인, 길이가 $n$인 소문자 영어 알파벳으로 이루어진 문자열이 주어집니다.
세 번째 줄에는 문제 설명에 나오는 문자열 $t$인, 길이가 $m$인 소문자 영어 알파벳으로 이루어진 문자열이 주어집니다.
모든 테스트 케이스의 문자열 길이의 합은 $10^7$을 넘지 않습니다.
출력
각 테스트 케이스에 대하여, 편집 거리가 $k$보다 크다면 "NO"를 한 줄에 출력합니다. 그렇지 않다면, 첫 번째 줄에 "YES"를 출력하고, 다음 줄부터는 다음과 같이 답을 설명합니다:
두 번째 줄에는 $s$를 $t$로 변환하는 데 필요한 최소 연산 횟수 $r$을 출력합니다. 다음 $r$ 줄에는 연산을 한 줄에 하나씩 출력합니다.
- 크기가 $w$인 문자열의 $p$ 위치 ($1 \le p \le w + 1$)에 소문자 영어 문자 $c$를 삽입하려면,
INSERT p c를 출력합니다. - 크기가 $w$인 문자열의 $p$ 위치 ($1 \le p \le w$)에 있는 문자를 삭제하려면,
DELETE p를 출력합니다. - 크기가 $w$인 문자열의 $p$ 위치 ($1 \le p \le w$)에 있는 문자를 소문자 영어 문자 $c$로 대체하려면,
REPLACE p c를 출력합니다.
예제
예제 입력 1
2 3 4 3 kot plot 5 7 3 zycie porazka
예제 출력 1
YES 2 REPLACE 1 l INSERT 1 p NO