Khánh Dung có một dãy số nguyên không âm \(\delta=(\delta_0, \delta_1,...,\delta_{n-1})\) thỏa mãn \(|\delta_i-\delta_{i-1}|\leq 1\) với mọi \(1\leq i < n\) và một số nguyên dương \(m\). Trong bài toán này, Khánh Dung chỉ quan tâm đến các xâu ký tự chỉ gồm các ký tự trong số \(m\) ký tự đầu tiên trong bảng chữ cái in thường.

Dung gọi một xâu \(\sigma=\sigma_0\sigma_1...\sigma_{n-1}\) là xâu lý thú khi và chỉ khi: với mọi \(i, j\) \((0\leq i, j < n)\) mà \(0 < |i-j|\leq \delta_i\) thì \(\sigma_i\ne \sigma_j\). Với mỗi xâu lý thú \(\sigma\), cô ấy gọi \(\text{rank}(\sigma)\) là số lượng xâu lý thú có cùng độ dài với xâu \(\sigma\) và có thứ tự từ điển nhỏ hơn hẳn \(\sigma\).

Với hai xâu thú vị \(\alpha\) và \(\beta\) có cùng độ dài \(n\), Dung muốn tìm xâu thú vị \(\gamma\) có cùng độ dài \(n\) thỏa mãn \(\text{rank}(\gamma)=\text{rank}(\alpha)+\text{rank}(\beta)\) hoặc kết luận không tồn tại xâu ký tự nào như vậy.

Cho biết giá trị \(n\), \(m\), dãy \(\delta\), và hai xâu \(\alpha\), \(\beta\), bạn hãy lập trình giúp Dung xác định xâu \(\gamma\) nhé!

Input

• Dòng đầu chứa hai số nguyên dương \(n\), \(m\) \(\left(1\leq n\leq 10^5, 1\leq m\leq 5\right)\).
• Dòng tiếp theo chứa \(n\) số nguyên không âm \(\delta_0, \delta_1,...,\delta_{n-1}\).
• Dòng tiếp theo chứa xâu \(\alpha\) độ dài \(n\).
• Dòng tiếp theo chứa xâu \(\beta\) độ dài \(n\).

Dữ liệu đảm bảo \(\alpha\) và \(\beta\) là hai xâu lý thú hợp lệ.

Output

• Gồm một xâu lý thú \(\gamma\) độ dài \(n\) thỏa mãn \(\text{rank}(\gamma)=\text{rank}(\alpha)+\text{rank}(\beta)\). Nếu không tồn tại xâu thỏa mãn thì in ra \(-1\).

Ví dụ

Sample input 01

3 5
1 2 3
bed
cad

Sample output 01

eab

Giải thích

Xâu lý thú \(\gamma\) cần tìm gồm có \(3\) ký tự đôi một khác nhau, đồng thời \(\text{rank}(\gamma)=\text{rank}(\alpha)+\text{rank}(\beta)=23+25=48\).

Sample input 02

4 5
1 0 0 1
cacb
adbc

Sample output 02

cddc

Giải thích

Xâu lý thú \(\gamma\) cần tìm có dạng \(\sigma_0\sigma_1\sigma_2\sigma_3\) với \(\sigma_0\ne \sigma_1\) và \(\sigma_2\ne \sigma_3\), đồng thời \(\text{rank}(\gamma)=\text{rank}(\alpha)+\text{rank}(\beta)=169+45=214\).

Ràng buộc

• Subtask 1 (20% số điểm): \(n\leq 10\).
• Subtask 2 (20% số điểm): \(n\leq 25\).
• Subtask 3 (20% số điểm): Không có giới hạn gì thêm.

Nguồn bài: Đơn giản hóa bài toán số 2 của đề VN TST 2024.