Kì thi duyên hải và đồng bằng bắc bộ năm 2017 được tổ chức tại Ninh Bình – một trong 3 địa điểm quay bộ phim Kong: Đảo Đầu Lâu làm mọi người rất phấn khích. Bờm cũng quyết để dành tiền để sau khi thi xong có thể khám phá các địa điểm du lịch đó. Bờm có mua một két sắt nhưng em trai Bờm lại rất hay nghịch phá và mày mò các password của Bờm. Vì vậy, Bờm sẽ liên tục thay đổi mật khẩu. Mật khẩu mới chắc chắn phải đảm bảo các quy tắc an toàn nhưng Bờm cũng thích mật khẩu này gần giống với mật khẩu cũ để dễ ghi nhớ.

Mật khẩu cũ là một số nguyên dương ~S~ không quá 16 chữ số khác 0 được đánh số từ 1 đến ~n~ (~n~ là độ dài mật khẩu) theo chiều từ trái qua phải (chữ số hàng đơn vị sẽ được đánh số ~n~).

Mật khẩu mới ~t~ chính là hoán vị ~n~ chữ số của ~S~. Để an toàn, chữ số thứ ~i~ của mật khẩu mới sẽ phải khác số ~H_i~. Và do có nhiều cách chọn nên Bờm sẽ chọn mật khẩu ~t~ có ~|t - s|~ nhỏ nhất, nếu vẫn có nhiều hơn một cách chọn thì sẽ chọn cách có ~t~ nhỏ hơn.

Yêu cầu: Tìm mật khẩu mới ~t~ thỏa mãn các điều kiện trên.

Input

• Dòng 1: Ghi số nguyên dương ~S~ (~1 \le S < 10^{16}~, gồm toàn các chữ số khác 0).
• Dòng 2: Ghi ~N~ số nguyên dương trong đoạn ~[1, 9]~, số thứ ~i~ là ~H_i~.

Output

• Ghi ra kết quả tìm được.

Sample Input 1

548
5 1 8

Sample Output 1

485