問題文

$N$ 個の自然数から成る数列 $A = [A_1, A_2, A_3, ..., A_N]$ が与えられます。また、整数 $K$ が与えられます。

さて、これについて $Q$ 回の操作を行います。

• 数列の $x_i$ 番目の要素を $v_i$ に変更する。

各変更の後について、数列のいくつかの要素を選んで合計を $K$ にする事が出来るか求めてください。
ただし、数列の各要素は $1$ 回しか選べないものとします。
例えば、数列が $[4, 4, 9]$ の場合、合計を $0, 4, 8, 9, 13, 17$ にする事が出来ます。

制約

全ての入力データは以下の制約を満たします。

• $N$ は $1$ 以上 $15 \ 000$ 以下の整数
• $Q$ は $1$ 以上 $15 \ 000$ 以下の整数
• $K$ は $1$ 以上 $15 \ 000$ 以下の整数
• $A_i$ は $0$ 以上 $15 \ 000$ 以下の整数
• $x_i$ は $1$ 以上 $N$ 以下の整数
• $v_i$ は $0$ 以上 $15 \ 000$ 以下の整数

入力

$N$ $K$
$A_1$ $A_2$ $A_3$ ... $A_N$
$Q$
$x_1$ $v_1$
$x_2$ $v_2$
$x_3$ $v_3$
...
$x_Q$ $v_Q$

出力

$Q$ 行に渡って出力してください。
$i$ 行目には、$i$ 回目の操作が終わった後で部分和が $K$ となるようなものが存在する場合 $1$、そうでない場合 $0$ と出力してください。

サンプル

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

1
0
1

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