KHÔI PHỤC DỮ LIỆU

Điểm số: 1

Giới hạn thời gian: 3s

Giới hạn bộ nhớ: 512 MB

Người đăng: admin

Bạn có một từ gồm N chữ cái in thường và trong đó có M chữ cái bị mờ đi không thể đọc được. Ngoài ra, bạn còn có M dòng gợi ý dùng để khôi phục lại từ ban đầu. Dòng thứ i sẽ có K chữ cái là những chữ có thể xuất hiện ở vị trí chữ cái bị mờ thứ i. Từ những gợi ý này bạn có thể tạo ra được một dãy các từ, sắp xếp dãy các từ này tăng dần theo thứ tứ chữ cái và từ ban đầu bạn cần tìm sẽ nằm ở vị trí thứ X. Các bạn hãy viết một chương trình để khôi phục lại từ này nhé!

 

Input

  • Dòng đầu tiên gồm các số tự nhiên N, M, K và X
  • Dòng thứ hai gồm một xâu gồm các chữ cái in thường và dấu # đại diện cho những vị trí bị mờ.
  • M dòng tiếp theo, mỗi dòng gồm K chữ cái mà bạn có thể điền vào vị trí bị mờ
  • Giới hạn

Output

Gồm một dòng duy nhất là từ mà bạn tìm được. Dữ liệu luôn đảm bảo bài toán có kết quả.

Ví dụ

Input

Output

10 2 4 8

gtl#fith#u

dtyz

fhlo

gtltfithou

 

 

 

Giải thích

8 từ đầu tiên lần lượt là: gtldfithfu, gtldfithhu, gtldfithlu, gtldfithou, gtltfithfu, gtltfithhu, gtltfithlu, gtltfithou