Một ngày nọ, sau khi Tus thi VOI xong thì Tus nhận ra mình quá gà vì không giải được bất kì một bài nào cả. Do vậy, Tus quyết định mỗi ngày học 180 phút. Quá trình tự học của Tus rất vất vả nên để Tus đỡ buồn thì anh Qa đã đến trò chuyện, tán gẫu cùng Tus.

Tus là một người không muốn lãng phí thời gian cho nên Tus chỉ muốn nghe những câu chuyện bổ ích. Biết được điều đó, anh Qa đã kể cho Tus nghe sự tích về những con số. Nhưng không may Tus chỉ biết các số ở hệ cơ số ~10~. Vì thế để Tus hiểu được câu chuyện anh Qa đã tốn rất nhiều công sức giảng lại cho Tus về khái niệm và cả ví dụ về các hệ cơ số. Thế nhưng trong lúc đang lấy ví dụ cho Tus thì anh Qa nhận được cuộc gọi từ Zun. Thế là anh Qa đành phải đi, để Tus ở lại tự tìm hiểu. Trước khi anh Qa rời đi anh đã viết ra giấy số ~n~ trong hệ cơ số ~10~ và số ~n~ trong hệ cơ số ~X~ nào đó. Vì anh Qa bận việc gấp nên chưa kịp bảo Tus hệ cơ số anh dùng là hệ nào. Tus đành nhờ các bạn giúp nhé!

Dữ liệu

• Dòng đầu tiên là ~2~ số nguyên ~n, m~ ~(0 \le n \le 10^{18},\ 1 \le m \le 5 \cdot 10^5)~ — số được viết trong hệ cơ số ~10~ và độ dài của số đó sau khi chuyển sang hệ cơ số mới.

• Dòng thứ hai gồm ~m~ số nguyên ~a_0, a_1, \ldots, a_{m-1}~ ~(0 \le a_i \le 10^{18})~, trong đó ~a_i~ là chữ số thứ ~i~ (tính từ phải sang trái, bắt đầu từ ~0~) của số ~n~ sau khi chuyển sang hệ cơ số mới.

Kết quả

In ra ~1~ số nguyên duy nhất là hệ cơ số mà anh Qa đã sử dụng. Nếu có nhiều hệ cơ số ~X~ thỏa thì xuất ra ~X~ nhỏ nhất có thể. Còn nếu không tồn tại ~X~, in ra ~-1~.

Ví dụ

Sample Input

2532 3
4 14 9

Sample Output

16

Subtask

• Subtask 1: ~80\%~ số tests đảm bảo ~1 \le X \le 16~ và ~1 \le n \le 10^4~.

• Subtask 2: ~20\%~ còn lại không có điều kiện gì thêm.