28143번 - k번째 이진십진수

문제

십진법으로 표현했을 때 0과 1로만 이뤄진 양의 정수를 이진십진수라고 합시다. 예를 들어 101001은 이진십진수이고, 102002는 이진십진수가 아닙니다.

집합 A_n은 양의 정수 n에 대해 이진십진수인 n의 배수 중 자릿수가 가장 작은 것들의 집합으로 정의됩니다. 만약 이진십진수이면서 n의 배수인 수가 존재하지 않는다면, A_n은 공집합입니다.

양의 정수 n과, 양의 정수 m개로 이루어진 수열 {k₁, k₂, ⋯, k_m}이 주어지면, 수열의 각 값 k_i (1 ≤ i ≤ m)에 대해 A_n의 원소 중에서 k_i번째로 작은 수를 계산하는 프로그램을 작성하세요.

입력

첫 번째 줄에 두 양의 정수 n과 m이 공백을 사이에 두고 주어집니다. (1 ≤ n ≤ 10⁶, 1 ≤ m ≤ 10⁴)

두 번째 줄부터 m개의 줄에 걸쳐, i+1번째 줄에 k_i의 값이 주어집니다. (1 ≤ i ≤ m, 1 ≤ k_i ≤ 10¹⁸)

출력

m개의 줄에 걸쳐 i번째 줄에, A_n의 원소가 k_i개 이상이라면 A_n에서 k번째로 작은 수를 출력하고 그렇지 않다면 X를 출력합니다.

제한

힌트