Problem D
Is It Even?

You are a leading programmer at $\text {Company}^\text {TM}$, and have been given the following task. Given a list of $N$ integers $x_1,\ldots , x_ N$, is their product $x_1\cdot x_2 \cdot \ldots \cdot x_ N$ even? You plug away at the problem using every trick in the book, and come up with a very elegant solution. Lo and behold, your supervisor then informs you that the task has changed! It turns out the higher ups want you to find out if the product $x_1 \cdot x_2 \cdot \ldots \cdot x_ N$ is divisible by $2^ K$ for some integer $K \geq 0$.

You just can’t catch a break!

Input

The input consists of two integers $N, K$ $(1 \leq N \leq 100\, 000$ and $0 \leq K \leq 1000$). These are followed by $N$ lines, each with a single value $x_1,\ldots , x_ N$ respectively ($1 \leq x_ i \leq 10^9$ for each $1 \leq i \leq N$) which form the product.

Output

Display 1 if $2^ K$ divides $x_1\cdot x_2 \cdot \ldots \cdot x_ N$, otherwise display 0.

4 2
3
2
1
1

0

5 4
3
30
6
4
7

1