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\).

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\).

3 5
1 2 3
bed
cad

eab

4 5
1 0 0 1
cacb
adbc

cddc