Brunhilda sắp tổ chức sinh nhật lần thứ bảy và nghĩ ra một trò chơi. Khi một số \(k\) được hô lên, các em nhỏ chia thành những nhóm có đúng \(k\) người. Chừng nào còn ít nhất \(k\) em chưa có nhóm, một nhóm mới tiếp tục được lập. Cuối cùng, số em dư ra, ít hơn \(k\), bị loại khỏi trò chơi. Những em còn lại tiếp tục chơi với các số được hô tiếp theo. Trò chơi kết thúc khi không còn em nào.

Cha của Brunhilda, Wotan, muốn kết thúc trò chơi càng sớm càng tốt để đi xem bóng đá. Brunhilda đưa cho ông một danh sách gồm \(m\) số nguyên tố khác nhau; mỗi lần ông chỉ được chọn một số trong danh sách, nhưng có thể chọn lại một số nhiều lần.

Với \(Q\) khả năng về số người tham gia ban đầu \(n_1,\ldots,n_Q\), hãy tìm số lần hô ít nhất để kết thúc trò chơi, hoặc xác định rằng không thể kết thúc.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(m\) và \(Q\). Dòng thứ hai chứa \(m\) số nguyên tố phân biệt \(p_1,\ldots,p_m\) theo thứ tự tăng dần. Mỗi dòng trong \(Q\) dòng tiếp theo chứa một số nguyên \(n_j\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) chứa số lần hô ít nhất để loại hết \(n_j\) người, hoặc xâu oo gồm hai chữ cái o thường nếu không thể kết thúc trò chơi.

Ràng buộc

• \(1 \le m,Q \le 100\,000\).
• \(2 \le p_i \le 10\,000\,000\); các \(p_i\) là số nguyên tố phân biệt, tăng dần.
• \(1 \le n_j \le 10\,000\,000\).

Phân nhóm

• \(20\) điểm: \(m,Q \le 10\,000\) và mọi \(n_j \le 10\,000\).
• Thêm \(20\) điểm: \(Q=1\).
• \(60\) điểm còn lại: không có ràng buộc bổ sung.

Ví dụ

2 2
2 3
5
6

3
oo