Bạn đã bao giờ nghe về bài toán khoảng cách chỉnh sửa (edit distance) chưa? Cho hai xâu gồm các chữ cái tiếng Anh viết thường, bạn phải xác định số lượng thao tác tối thiểu cần thiết để biến đổi xâu thứ nhất thành xâu thứ hai. Một thao tác đơn lẻ có thể là:
- chèn một ký tự vào chuỗi, tại bất kỳ vị trí nào,
- xóa bất kỳ ký tự nào khỏi chuỗi,
- thay thế một ký tự bằng một ký tự khác.
Mọi người ở trường đại học của chúng tôi rất thích bài toán này – có lẽ là hơi quá mức – vì vậy chúng tôi quyết định tạo ra một bài toán dễ hơn! Bạn được cho hai xâu $s = s_1 \dots s_n$, $t = t_1 \dots t_m$ và một số nguyên $k$. Hãy tìm xem khoảng cách chỉnh sửa giữa hai xâu có nhỏ hơn hoặc bằng $k$ hay không. Nếu có, bạn cũng được yêu cầu cung cấp bất kỳ chuỗi thao tác nào với số lượng tối thiểu để biến đổi xâu thứ nhất thành xâu thứ hai.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa số lượng bộ test $z$ ($1 \le z \le 100$). Tiếp theo là mô tả của các bộ test.
Dòng đầu tiên của mỗi bộ test chứa ba số nguyên $n, m, k$ ($1 \le n, m \le 1\,000\,000$, $0 \le k \le 1000$) – độ dài của các xâu và tham số từ mô tả bài toán.
Dòng thứ hai chứa một xâu có độ dài $n$ bao gồm các chữ cái tiếng Anh viết thường – xâu $s$ từ mô tả bài toán.
Dòng thứ ba chứa một xâu có độ dài $m$ bao gồm các chữ cái tiếng Anh viết thường – xâu $t$ từ mô tả bài toán.
Tổng độ dài của tất cả các xâu trong tất cả các bộ test sẽ không vượt quá $10^7$.
Dữ liệu ra
Đối với mỗi bộ test, nếu khoảng cách chỉnh sửa lớn hơn $k$, hãy in ra một dòng duy nhất chứa từ “NO”. Nếu không, dòng đầu tiên nên chứa từ “YES”, và các dòng tiếp theo nên mô tả câu trả lời như sau:
Ở dòng thứ hai, in ra số lượng thao tác tối thiểu $r$ cần thiết để biến đổi $s$ thành $t$. Trong $r$ dòng tiếp theo, in ra các thao tác, mỗi thao tác trên một dòng.
- Để chèn một ký tự tiếng Anh viết thường $c$ vào một chuỗi có kích thước $w$ tại vị trí $p$ ($1 \le p \le w + 1$), in ra
INSERT p c. - Để xóa một ký tự khỏi một chuỗi có kích thước $w$ tại vị trí $p$ ($1 \le p \le w$), in ra
DELETE p. - Để thay thế một ký tự trong một chuỗi có kích thước $w$ tại vị trí $p$ ($1 \le p \le w$) bằng một ký tự tiếng Anh viết thường $c$, in ra
REPLACE p c.
Ví dụ
Dữ liệu vào 1
2 3 4 3 kot plot 5 7 3 zycie porazka
Dữ liệu ra 1
YES 2 REPLACE 1 l INSERT 1 p NO