연봉 998244353원 주세요

사원이 무수히 많은 거대기업 "Monthly PS Inc."에서 연봉협상 날이 다가오고 있다. 이 회사의 사원에게는 $0$번부터 차례대로 고유한 사원 번호가 부여되어 있고, 모든 사원은 자신보다 사원 번호가 $1$ 큰 사원의 직속 부하이다.

$0$번 사원을 제외한 모든 사원이 다음과 같이 요구하기 시작했다.

그래도 명색이 상사인데, 적어도 제 부하보다 연봉을 더 받고 싶어요.. 또, 제가 받는 연봉이 제 사원 번호의 배수이면 좋겠어요.

이 회사의 CEO인 당신은 돈을 최대한 아끼면서 사원들의 요구를 모두 들어주려 한다. 또 0번 사원이 연봉 $X$를 받을 때, 특정 사원 번호에 배정된 사원이 받게 될 연봉에 대한 질문이 $Q$개 생겼다.

이 질문에 답하는 프로그램을 작성하자.

첫째 줄에 $0$번 사원이 받는 연봉 $X$와 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. ($1 \le X \le 10^9$; $1 \le Q \le 100\,000$)

둘째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. $i$번째 쿼리로 연봉이 궁금한 사원 번호 $A_i$가 주어진다. ($1 \le A_i \le 10^9$)

입력으로 주어지는 모든 수는 정수다.

쿼리마다 한 줄에 하나씩, 해당 사원 번호에 배정된 사원이 받게 될 연봉을 출력한다.