Trên màn hình có một xâu ~S=S_1S_2\ldots S_N~ gồm các chữ cái tiếng Anh in hoa. Các vị trí của xâu được đánh số từ ~1~ đến ~N~. Một người chơi được giao một xâu mục tiêu ~R~. Ban đầu, người chơi có thể chọn một vị trí bất kỳ trên ~S~ làm vị trí xuất phát với chi phí bằng ~0~.

Khi đang đứng tại vị trí ~i~, người chơi có thể thực hiện một trong hai thao tác sau:

• Nếu ~i<N~, di chuyển sang vị trí ~i+1~. Chi phí của thao tác là ~\left|\operatorname{val}(S_{i+1})-\operatorname{val}(S_i)\right|,~ trong đó ~\operatorname{val}(\texttt{A})=1,\ldots,\operatorname{val}(\texttt{Z})=26~.</p>

• Nhảy đến một vị trí ~j>i~ sao cho ~S_j=S_i~. Chi phí của thao tác này bằng ~0~. Khi nhảy, người chơi chỉ đến vị trí ~j~ và không đi qua các vị trí nằm giữa ~i~ và ~j~.

Tại mỗi vị trí mà người chơi đứng, kể cả vị trí xuất phát, người chơi có thể chọn lấy hoặc không lấy ký tự tại vị trí đó. Các ký tự được lấy phải lần lượt tạo thành đúng xâu ~R~. Do người chơi chỉ có thể di chuyển về phía bên phải, các vị trí được dùng để lấy các ký tự của ~R~ phải tăng nghiêm ngặt.

Có ~Q~ xâu mục tiêu khác nhau cần được xử lý độc lập.

Yêu cầu:

Với mỗi xâu mục tiêu ~R~, hãy tìm chi phí nhỏ nhất để thu thập được toàn bộ ~R~. Nếu không thể thực hiện được, hãy in ra ~-1~.

Input

Dòng đầu tiên chứa hai số nguyên ~N,Q~ (~1\le N\le 5000~, ~1\le Q\le 200~).

Dòng thứ hai chứa xâu ~S~ gồm đúng ~N~ chữ cái tiếng Anh in hoa. ~Q~ dòng tiếp theo, mỗi dòng chứa một xâu mục tiêu ~R~ gồm các chữ cái tiếng Anh in hoa, với ~1\le |R|\le 50.~

Output

Với mỗi xâu mục tiêu, in ra trên một dòng chi phí nhỏ nhất để thu thập được toàn bộ xâu đó. Nếu không thể thực hiện được, in ra ~-1~.