니야의 행복

X나라의 화폐 제도는 조금 이상하다. 액면가가 $1$인 지폐부터 $M$인 지폐까지, 그 사이의 모든 정수 액면가 지폐가 있다. 가게에도 이상한 규칙이 하나 있다. 손님은 거스름돈을 받을 수 없고, 팁을 남길 수도 없다. 물건값과 정확히 같은 금액을 내야만 물건을 살 수 있고, 그 금액을 지폐로 정확히 만들 수 없으면 아무것도 살 수 없다.

니야는 X나라에 사는 소녀다. 니야는 자신이 가진 지폐를 항상 알고 있고, 그 액면가를 $a_1, a_2, \ldots, a_N$이라고 하자. 모든 값은 $1$ 이상 $M$ 이하이고, 같은 액면가의 지폐를 여러 장 가질 수도 있다. 액면가가 어떤 순서로 정렬되어 있지는 않다.

니야는 $1$ 이상 $a_1 + a_2 + \cdots + a_N$ 이하의 어떤 금액이든 자기 지폐 중 일부를 골라 정확히 낼 수 있을 때 행복하다. 그러면 가게에서 복잡한 계산을 할 필요 없이 가진 돈의 총액만 확인하면 된다. 지폐가 한 장도 없을 때도 니야는 행복하다. 그때는 쇼핑을 건너뛰고 달리기를 하러 가면 되기 때문이다.

참고: $a_1, a_2, \ldots, a_N$을 오름차순으로 정렬하고 $S_i = 1 + a_1 + a_2 + \cdots + a_i$라고 하자. $1$부터 $a_1 + a_2 + \cdots + a_N$까지의 모든 금액을 이 지폐 중 일부의 합으로 나타낼 수 있을 필요충분조건은 $a_1 = 1$이고, $1 \le i < N$인 모든 $i$에 대해 $a_{i+1} \le S_i$가 성립하는 것이다.

니야의 지폐 구성은 물건을 살 때마다, 그리고 월급을 받을 때마다 바뀐다. 그래서 니야의 행복도 계속 달라진다. 처음 지폐 구성과 그 뒤에 일어나는 사건이 모두 주어질 때, 처음 시점과 각 사건 직후에 니야가 행복한지 판정하는 프로그램을 작성하시오.

첫째 줄에 니야가 처음 가진 지폐의 개수 $N$과 지폐 한 장의 최대 액면가 $M$이 공백으로 구분되어 주어진다.

둘째 줄에 처음 지폐 $N$장의 액면가가 공백으로 구분되어 주어진다. $N$이 $0$이면 이 줄은 비어 있다.

셋째 줄에 사건의 개수 $Q$가 주어진다.

다음 $Q$개의 줄에 사건이 한 줄에 하나씩, 일어난 순서대로 주어진다. 각 줄은 사건의 종류를 나타내는 정수로 시작한다. $-1$은 쇼핑, $1$은 월급 수령이다. 그 다음에 니야의 지폐에서 빠지거나 더해지는 지폐의 개수 $K$가 주어지고, 이어서 그 지폐 $K$장의 액면가가 공백으로 구분되어 주어진다.

$Q+1$개의 줄을 출력한다. 첫째 줄에는 처음 시점의 상태를, 그 다음 $i$번째 줄에는 $i$번째 사건 직후의 상태를 출력한다. 니야가 행복하면 $1$을, 행복하지 않으면 $0$을 출력한다.

니야가 어느 시점에 가진 지폐의 개수를 $N_c$, 한 번의 쇼핑이나 월급에서 오가는 지폐의 개수를 $K$라고 하면 다음이 성립한다.

• $0 \le N_c \le 200\,000$
• $0 \le Q \le 100\,000$
• $1 \le M \le 10^{12}$
• $1 \le K \le 5$
• 모든 지폐의 액면가는 $1$ 이상 $M$ 이하의 정수이다.
• 쇼핑 사건에서 주어지는 지폐는 그 시점에 니야가 가진 지폐의 부분집합임이 보장된다.