33484번 - 합의 수열 서브태스크

풋살 악귀 동우는 주위 사람들에게 항상 풋살을 하자며 사람을 모은다. 동우가 모은 풋살 멤버 중에는 재우, 종우, 현철, 준혁, 용명, 재현, 동현, 근형, 도훈, 민성, 문성, 세준이 등이 다양한 사람들이 있었고, 이 중 많은 사람들은 작년 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$에 대해서도 만약 $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=\left[ 6,16,27,36,46,57,66,75,\cdots \right]$이다.

$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을 한 줄에 한 개씩 출력한다.