Doctor Strange and the Exhibition

Time limit1sMemory limit1024 MB

Summary

Given n numbers below 4096, decide whether some k of them have a bitwise AND equal to zero.

Level: Medium7 of 10
Topics: Bit manipulation, Combinatorics
Solved: No attempts yet

Statement

Doctor Strange has a garden where $n$ flower pots are placed in a row. Each pot has a number written on it. The pot at position $i$ has the number $a_i$ . In other words, the pots form an array $a$ .

A flower exhibition is coming up. Doctor Strange will choose exactly $k$ pots for it. He wants his collection to be the most memorable. He also likes patterns, so he believes that if the bitwise AND of the numbers on the chosen pots equals zero, his flowers will leave a lasting impression on everyone.

Help Doctor Strange determine whether he can choose $k$ pots that satisfy this condition.

The bitwise AND is a binary operation that applies logical AND to each pair of bits in the same positions of the binary representations of the operands.

Input

The first line contains two positive integers $n$ and $k$ ( $1 \le n \le 2 \cdot 10^4$ , $1 \le k \le n$ ).

The next line contains $n$ non-negative integers $a_i$ ( $0 \le a_i < 2^{12}$ ).

Output

If there is a way to choose $k$ pots whose bitwise AND equals zero, print YES on the first line. Otherwise, print NO.

Examples3

Example 1
Input
```
3 1
5 4 3
```
Expected output
```
NO
```
Example 2
Input
```
3 2
5 4 3
```
Expected output
```
YES
```
Example 3
Input
```
6 3
6 12 7 8 5 13
```
Expected output
```
YES
```