합의 수열

풋살 악귀 동우는 주위 사람들에게 항상 풋살을 하자며 사람을 모은다. 동우가 모은 풋살 멤버에는 재우, 종우, 현철, 준혁, 용명, 재현, 동현, 근형, 도훈, 민성, 문성, 세준 등 다양한 사람이 있었다. 이 중 많은 사람이 작년 2024 ICPC Seoul Regional이 끝난 뒤 열린 일산 풋살 모임에서 이번 <제6회 MatKor Cup:2025 Winter>의 출제자 또는 검수자로 영입되었다.

도훈이에게 수열을 선물 받은 재우는 수열의 합이 아닌 합의 수열을 다시 선물하려 한다. 재우는 다음 과정으로 합의 수열을 만든다.

처음에 모든 양의 정수가 들어 있는 집합 $A=\mathbb{Z}^+$가 있다. 이 집합에서 다음 과정을 $10^{1\,000\,000}$번 반복하여 새로운 수열 $B_M$을 만든다.

1. $A$에 있는 가장 작은 수 $M$개를 고르고, 그 수들의 합 $S$를 구한다.
2. 고른 $M$개의 수 각각에 대해, 그 수가 $A$에 있으면 $A$에서 지운다. 또 $S$가 $A$에 있으면 $A$에서 지운다.
3. $S$를 $B_M$에 추가한다.

예를 들어 $M=3$일 때 $1+2+3=6$, $4+5+7=16$, $8+9+10=27$, $11+12+13=36$, $14+15+17=46$과 같으므로 $B_3=[6, 16, 27, 36, 46, 57, 66, 75, \cdots]$이다.

$M$이 주어지고 $Q$개의 질문이 주어졌을 때, 각 질문에 대해 그 수가 $B_M$에 있는지 판단하라.

첫 번째 줄에 공백으로 구분된 $M(1\le M\le 10^{18})$과 $Q(1\le Q\le 10^5)$가 주어진다. 다음 $Q$개의 줄에 각각 질문할 정수 $N(1\le N\le 10^{18})$이 하나씩 주어진다.

각 질문에 대해 그 수가 $B_M$에 포함되어 있으면 1을, 아니면 0을 한 줄에 하나씩 출력한다.