Ghi chú song ngữ

Bối cảnh và bài toán

Một sinh viên tham dự bài giảng chuyên ngành bằng ngôn ngữ thứ nhất, nhưng đã chuẩn bị một bảng m cặp từ đồng nghĩa (a,b) giữa hai ngôn ngữ. Khi giảng viên nói từ a, sinh viên muốn ghi phiên bản ngắn hơn để tiết kiệm thời gian viết mà vẫn giữ đúng nghĩa.

Với mỗi cặp (a,b), nếu a và b có cùng độ dài thì sinh viên ưu tiên giữ a.

Bài giảng gồm n từ, và mọi từ trong bài giảng đều là một từ a đã xuất hiện trong bảng từ điển.

Yêu cầu

In chuỗi ghi chú sau khi thay mỗi từ bằng lựa chọn phù hợp, giữ nguyên thứ tự bài giảng.

Input

• Dòng 1: n m.
• m dòng tiếp theo: một cặp a b.
• Dòng cuối: n từ của bài giảng.

Output

n từ sau khi lựa chọn.

Ràng buộc

• 1 <= n, m <= 3000
• Mỗi từ dài từ 1 đến 20 ký tự thường.

Chấm điểm

Ví dụ 1

Input

4 3
codeforces codesecrof
contest round
letter message
codeforces contest letter contest

Output

codeforces round letter round

Giải thích. round ngắn hơn contest; letter ngắn hơn message; codeforces và codesecrof bằng độ dài nên giữ từ thứ nhất.

Ví dụ 2

Input

3 2
alpha a
beta bet
alpha beta alpha

Output

a bet a

Giải thích. Với alpha, từ a ngắn hơn; với beta, từ bet ngắn hơn. Các lựa chọn đã xác định trong từ điển được dùng lại cho mọi lần xuất hiện.

Thông tin bài tập

• Yêu cầu: Decision Note ngắn.

Nguồn: Phỏng theo Codeforces — 499B Lecture.
Tham khảo: https://codeforces.com/problemset/problem/499/B
Ghi chú biên tập: Biên tập lại ngữ cảnh/constraints và chuẩn hóa theo lộ trình FULLHOUSE DEV; giữ bản chất yêu cầu của bài nguồn.