说明

时间限制：3 Sec 内存限制：256 MB 输入文件：superset.in 输出文件：superset.out

给定由 $N$ 个自然数组成的序列 $A = [A_1,A_2,\dots,A_N]$，以及一个整数 $K$。

接下来进行 $Q$ 次操作：

- 将序列的第 $x_i$ 个元素修改为 $v_i$。

每次修改之后，请判断是否可以选出序列中的若干元素，使得它们的和恰好等于 $K$。

每个元素最多只能被选一次。

例如，序列为 $[4,4,9]$ 时，可以凑出的和为 $0,4,8,9,13,17$。

输入格式

第一行给出两个整数 $N$ 和 $K$。

第二行给出 $N$ 个整数 $A_1,A_2,\dots,A_N$。

第三行给出一个整数 $Q$。

接下来 $Q$ 行，每行给出两个整数 $x_i$ 和 $v_i$。

输出格式

输出共 $Q$ 行。

第 $i$ 行，如果第 $i$ 次操作结束后存在和为 $K$ 的子集，输出 $1$，否则输出 $0$。

样例

样例 1

3 8
4 4 9
3
1 4
2 5
3 3

1
0
1

样例说明：

第一次操作后序列为 $[4,4,9]$，可以选 $4+4=8$。

第二次操作后序列为 $[4,5,9]$，无法凑出 $8$。

第三次操作后序列为 $[4,5,3]$，可以选 $5+3=8$。

样例 2

6 26
8 6 9 1 2 0
6
1 9
2 6
3 8
4 5
5 2
6 6

1
1
1
0
0
1

数据范围

对于 20% 的数据，$N \le 10$，$Q \le 50$，$K \le 50$，$v_i \le 50$。

对于 44% 的数据，$N \le 20$。

另有 8% 的数据，$v_i \le 2$。

对于 100% 的数据：$1\le N\le 15000$，$1\le Q\le 15000$，$1\le K\le 15000$，$0\le A_i\le 15000$，$1\le x_i\le N$，$0\le v_i\le 15000$。