만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

닥터 스트레인지와 전시회

시간 제한1초메모리 제한1024 MB

요약
4096 미만의 정수 n개 중에서 k개를 골라 비트 AND 결과가 0이 되는 경우가 있는지 판별합니다.
난이도

보통10점 중 7점

유형
비트 연산, 조합론
정답자
아직 제출이 없습니다

문제

닥터 스트레인지의 정원에는 nn개의 화분이 일렬로 놓여 있다. 각 화분에는 수가 적혀 있다. ii번째 자리의 화분에 적힌 수는 aia_i이다. 즉, 화분들이 배열 aa를 이룬다.

곧 꽃 전시회가 열린다. 닥터 스트레인지는 전시회에 쓸 화분을 정확히 kk개 고른다. 그는 자신의 컬렉션이 가장 인상적이기를 바란다. 또한 그는 규칙을 좋아해서, 고른 화분에 적힌 수들의 비트 단위 AND가 0이면 그의 꽃이 모든 관람객에게 잊히지 않는 인상을 남길 것이라고 믿는다.

이 조건을 만족하도록 화분 kk개를 고를 수 있는지 판단하라.

비트 단위 AND는 두 피연산자의 이진 표현에서 같은 자리에 있는 비트끼리 논리곱을 취하는 이항 연산이다.

입력

첫 줄에 두 자연수 nn, kk가 주어진다 (1≤n≤2⋅1041 \le n \le 2 \cdot 10^4, 1≤k≤n1 \le k \le n).

다음 줄에는 음이 아닌 정수 aia_i nn개가 주어진다 (0≤ai<2120 \le a_i < 2^{12}).

출력

고른 화분 kk개의 비트 단위 AND가 0이 되도록 고를 수 있으면 첫 줄에 YES를 출력한다. 그렇지 않으면 NO를 출력한다.

예제3

  1. 예제 1

    입력
    3 1
    5 4 3
    
    예상 출력
    NO
    
  2. 예제 2

    입력
    3 2
    5 4 3
    
    예상 출력
    YES
    
  3. 예제 3

    입력
    6 3
    6 12 7 8 5 13
    
    예상 출력
    YES