Bessie đang chạy một cuộc đua dài \(K\) mét (\(1\le K\le 10^9\)). Cô bắt đầu chạy với vận tốc \(0\) mét mỗi giây. Trong mỗi giây, cô có thể tăng vận tốc thêm \(1\) mét mỗi giây, giữ nguyên vận tốc hoặc giảm vận tốc đi \(1\) mét mỗi giây. Chẳng hạn, trong giây đầu tiên, cô có thể tăng vận tốc lên \(1\) mét mỗi giây và chạy được \(1\) mét, hoặc giữ vận tốc ở mức \(0\) mét mỗi giây và chạy được \(0\) mét. Vận tốc của Bessie không bao giờ được giảm xuống dưới \(0\).

Bessie luôn chạy về phía vạch đích và muốn hoàn thành cuộc đua sau một số nguyên giây (tại thời điểm nguyên này, cô kết thúc ở đúng vạch đích hoặc đã vượt qua vạch đích). Hơn nữa, cô không muốn chạy quá nhanh khi về đích: tại đúng thời điểm Bessie chạy đủ \(K\) mét, cô muốn vận tốc mà mình vừa di chuyển không vượt quá \(X\) mét mỗi giây (\(1\le X\le 10^5\)). Bessie muốn biết cô có thể hoàn thành cuộc đua nhanh đến mức nào ứng với \(N\) giá trị \(X\) khác nhau (\(1\le N\le 1000\)).

Phân nhóm

• Các test từ \(2\) đến \(4\) thỏa mãn \(N=X=1\).
• Các test từ \(5\) đến \(10\) không có ràng buộc bổ sung.

Dữ liệu vào

Dữ liệu vào được đọc từ tệp race.in.

Dòng đầu tiên chứa hai số nguyên \(K\) và \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa một số nguyên \(X\).

Dữ liệu ra

Ghi ra tệp race.out gồm \(N\) dòng, mỗi dòng chứa một số nguyên là thời gian nhỏ nhất Bessie cần để chạy \(K\) mét sao cho khi về đích, vận tốc của cô không vượt quá \(X\).

Ví dụ

10 5
1
2
3
4
5

6
5
5
4
4

Nguồn

• Kỳ thi: USACO 2020 January Contest, Bronze
• Tên bài: Race
• Đề bài chính thức: https://usaco.org/index.php?page=viewproblem2&cpid=989
• Tác giả đề: Nick Wu