Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P143SUMG - ROUND 3G - Sửa lỗi chính tả

Ngày nay, xu hướng sử dụng smart phone đã trở thành rất phổ biến trên thế giới. Thay vì phải bấm từng phím cứng, người dùng chỉ cần chạm vào màn hình. Tuy nhiên, việc nhập sai nội dung từ xảy ra thường xuyên do không gian cho mỗi phím trên màn hình là hạn chế.

Một phần mềm sửa lỗi chính tả được người dùng khá ưa chuộng có chức năng như sau: khi người dùng nhập một từ trên màn hình, phần mềm này sẽ đưa ra danh sách các từ đúng để người dùng có thể lựa chọn. Tuy nhiên, bạn vẫn có thể cải thiện thêm tính năng cho phần mềm này, bằng cách sắp xếp các từ gợi ý theo độ ưu tiên “gần giống” với từ đã nhập nhất. Khoảng cách giữa 2 chữ cái được tính bằng tổng sai khác theo chiều ngang và chiều dọc của 2 chữ cái trên màn hình. Khoảng cách giữa 2 từ được tính bằng tổng khoảng cách của tất cả các chữ cái.

Bàn phím querty trên màn hình của điện thoại như sau:

qwertyuiop

asdfghjkl

zxcvbnm

Ví dụ, khoảng cách giữa kí tự ‘w’ và kí tự ‘e’ bằng 1, giữa ‘w’ và ‘z’bằng 3.

Input

Dòng đầu tiên là số lượng bộ test T (T <= 20).

Mỗi bộ test bằng đầu bằng một từ  (là chuỗi kí tự được nhập trên màn hình) và số nguyên n (n <= 10), là số từ gợi ý của phần mềm kiểm tra lỗi chính tả. n dòng tiếp theo, mỗi dòng là một từ gợi ý. Các từ gợi ý có chiều dài bằng với từ đã nhập ban đầu, và khác nhau đôi một.

Tất cả các chữ cái đều là chữ thường, và các từ có độ dài nhỏ hơn 10 000.

Output

Với mỗi test, in ra danh sách các từ gợi ý theo thứ tự ưu tiên tăng dần (khoảng cách so với từ đã nhập là nhỏ nhất). Nếu có nhiều từ có cùng khoảng cách với từ đã nhập, in ra theo thứ tự từ điển.

Example

Input:
2
qwertyuiopasdfghjklzxcvbnm 3
qwertyuiopsdfghjklzxcvbnma
mnbvcxzlkjhgfdsapoiuytrewq
mnbvcxzlkjhgfdsapoiuytrewa
edc 5
wsx
edc
rfv
plm
qed Output: qwertyuiopsdfghjklzxcvbnma 30
mnbvcxzlkjhgfdsapoiuytrewa 109
mnbvcxzlkjhgfdsapoiuytrewq 110
edc 0
rfv 3
wsx 3
qed 4
plm 17

Được gửi lên bởi:adm
Ngày:2014-07-08
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2015-05-21 14:02:38 Nguyễn Vĩnh Thịnh
cay quá không kiểm tra kĩ viết j nhầm thành i thế là mất 1 đấm AC @@
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.