4D - Soal Tambahan

Correction

Batas Waktu 	1 detik
Batas Memori 	64 MB

Pernahkan Anda memakai iPhone versi 2.0.2? Fitur paling menyebalkan yang tidak bisa (setidaknya, Pak Dengklek belum bisa) dimatikan pada iPhone versi ini adalah correction suggestion saat pengguna mengetik SMS.

Pak Dengklek ingin membuat program correction suggestion ini, dengan sedikit modifikasi. Penjelasan dari algoritma ini adalah sebagai berikut. Terdapat sebuah kamus yang berisi K (1 ≤ K ≤ 3.000) buah kata yang sah, masing-masing antara 1 sampai 3.000 huruf alfabet. Setiap kali Anda menuliskan sebuah huruf, program akan mengecek potongan kata yang sah yang paling dekat dengan (potongan) kata yang Anda tulis, dan mengembalikan saran potongan kata yang sah tersebut. Bila ada beberapa kata yang sama dekatnya, tuliskan kata yang lebih dahulu muncul pada masukan.

Kedekatan dua buah potongan kata dengan panjang sama adalah jumlah kedekatan antar dua huruf yang terletak di posisi yang sama. Kedekatan antar dua huruf ditentukan oleh jarak minimal keduanya dalam urutan alphabet 'a'-'z' (sirkular, sehingga kedekatan 'a' dan 'z' adalah 1). Misalnya, kedekatan antara "dara" dan "carb" adalah 1+0+0+1 = 2.

Bantulah Pak Dengklek membuat program correction suggestion yang menyebalkan ini.
Format Masukan

Baris pertama berisi sebuah bilangan bulat K. K baris berikutnya berisi kata-kata sah yang ada dalam kamus tersebut. Baris berikutnya berisi sebuah kata (query) antara 1 sampai 3.000 karakter. Dijamin selalu ada kata dalam kamus dengan panjang lebih dari atau sama dengan query.
Format Keluaran

Baris-baris sebanyak panjang kata query. Baris ke-i berisi saran yang akan diberikan program saat pengguna sudah mengetik i huruf pertama dari query.
Contoh Masukan

5
character
charade
cats
cabaret
blade
chabter

Contoh Keluaran

c
ch
cha
blad
cabar
cabare
cabaret