Snark and Philip are preparing the problemset for the upcoming pre-qualification round for semi-quarter-finals. They have a bank of n problems, and they want to select any non-empty subset of it as a problemset.

k experienced teams are participating in the contest. Some of these teams already know some of the problems. To make the contest interesting for them, each of the teams should know at most half of the selected problems.

Determine if Snark and Philip can make an interesting problemset!


-----Input-----

The first line contains two integers n, k (1 ≤ n ≤ 10^5, 1 ≤ k ≤ 4) — the number of problems and the number of experienced teams.

Each of the next n lines contains k integers, each equal to 0 or 1. The j-th number in the i-th line is 1 if j-th team knows i-th problem and 0 otherwise.


-----Output-----

Print "YES" (quotes for clarity), if it is possible to make an interesting problemset, and "NO" otherwise.

You can print each character either upper- or lowercase ("YeS" and "yes" are valid when the answer is "YES").


-----Examples-----
Input
5 3
1 0 1
1 1 0
1 0 0
1 0 0
1 0 0

Output
NO

Input
3 2
1 0
1 1
0 1

Output
YES



-----Note-----

In the first example you can't make any interesting problemset, because the first team knows all problems.

In the second example you can choose the first and the third problems.

Difficulty: competition

Starter code:

Solutions:
def bel(mask, bit):
    return (mask & (1 << bit)) != 0
read = lambda: map(int, input().split())
n, k = read()
f = [0] * 100
for i in range(n):
    cur = int(''.join(input().split()), 2)
    cur ^= (1 << k) - 1
    f[cur] = 1
ans = 'NO'
if k == 1:
    if f[1]:
        ans = 'YES'
if k == 2:
    f1 = f2 = 0
    for i in range(4):
        if f[i]:
            if bel(i, 0): f1 = 1
            if bel(i, 1): f2 = 1
    if f1 and f2:
        ans = 'YES'
if k == 3:
    p = [0] * 3
    for i in range(8):
        if f[i]:
            for j in range(3):
                if bel(i, j): p[j] = 1
    for i in range(8):
        if f[i]:
            if bel(i, 0) and bel(i, 1) and p[2]: ans = 'YES'
            if bel(i, 0) and p[1] and bel(i, 2): ans = 'YES'
            if p[0] and bel(i, 1) and bel(i, 2): ans = 'YES'
if k == 4:
    for i in range(16):
        if f[i]:
            for j in range(16):
                if f[j]:
                    if (i | j) == 15:
                        ans = 'YES'
print(ans)

n,k=list(map(int,input().split()))
a=[int(input().replace(" ",""),2) for i in range(n)]

# https://stackoverflow.com/questions/374626/how-can-i-find-all-the-subsets-of-a-set-with-exactly-n-elements
from itertools import chain, combinations

def powerset(iterable):
    xs = list(iterable)
    return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1))

for s in powerset([x for x in range(1<<k) if x in a]):
    if len(s) == 0: continue
    good = True
    for i in range(k):
        c = [(p >> i) & 1 for p in s]
        if c.count(1) > c.count(0):
            good = False
    if good:
        print("YES")
        return

print("NO")


n, k = map(int, input().split())
a = set()
yes = False
for i in range(n):
	a.add(input())
for w in a:
	for w2 in a:
		x = list(map(int, w.split()))
		y = list(map(int, w2.split()))
		count = 0
		for i in range(k):
			if x[i] + y[i] != 2:
				count += 1
		if count == k:
			yes = True
if yes:
	print("YES")
else:
	print("NO")

n,k = list(map(int,input().split()))
probs = list([0]*n for _ in range(k))
pbtype = [0]*2**k
e = [False]*2**k
ei = [False]*k

for i in range(n):
    x = list(map(int,input().split()))
    sum = 0
    for j in range(k):
        if x[j] == 0:
            sum += 2**j
            ei[j] = True
    pbtype[sum] += 1
    e[sum] = True

success = False
if e[2**k-1]:
    success = True
for i in range(k):
    if e[2**k-1-2**i] and ei[i]:
        success = True
if k == 4:
    if e[3] and e[12]:
        success = True
    if e[6] and e[9]:
        success = True
    if e[5] and e[10]:
        success = True

if success:
    print("YES")
else:
    print("NO")


# -*- coding: utf-8 -*-
"""
Created on Thu Oct  5 13:30:23 2017

@author: savit
"""

n,k=list(map(int,input().split()))
s=[]
A=[]
for i in range(16):
    A.append(False)
for i in range(n):
    s.append(input())
    s[i]=s[i].replace(' ','')
    s[i]=s[i] + '0'*(4-k)
    s[i]=int(s[i],2)
    A[s[i]]=True
fl=False
if(A[0]):
    fl=True
if(A[1]):
    for i in range(2,16,2):
        if(A[i]):
            fl=True
if(A[2] and (A[4] or A[5] or A[8] or A[9] or A[12] or A[13] or A[1])):
    fl=True
if(A[4] and (A[8] or A[9] or A[10] or A[11] or A[3] or A[1] or A[2])):
    fl=True
if(A[8]):
    for i in range(8):
        if(A[i]):
            fl=True
if(A[3] and A[12]):
    fl=True
if(A[6] and A[9]):
    fl=True
if(A[5] and A[10]):
    fl=True
if(fl):
    print('YES')
else:
    print('NO')




n,k=list(map(int,input().split()))
sp=[0]*(2**k)
for i in range(n):
    ci=list(map(int,input().split()))
    c=0
    for j in range(k-1,-1,-1):
        c+=(1-ci[j])*(2**j)
    sp[c]+=1
ed=[False]*k
for i in range(2**k-1,-1,-1):
    ci=[]
    t=i
    for j in range(k-1,-1,-1):
        ci.append(t//(2**j))
        t%=2**j
    if sp[i]>0:
        for j in range(k):
            if ci[j]==1:
                ed[j]=True
        break
p=i-1
for i in range(p,-1,-1):
    ci=[]
    t=i
    for j in range(k-1,-1,-1):
        ci.append(t//(2**j))
        t%=2**j
    if sp[i]>0:
        for j in range(k):
            if not(ci[j]==1 or ed[j]):
                break
        else:
            print('YES')
            return
if sp[2**k-1]>0:
    print('YES')
else:
    print('NO')
            
    


# IAWT
n, k = list(map(int, input().split()))
cnt = {}
for i in range(2 ** k):
    cnt[bin(i)[2:].zfill(k)] = 0

for i in range(n):
    l = input().split()
    s = ''
    for x in l:
        s += x
    cnt[s] += 1

def f1():
    if cnt['0'] > 0:
        print('YES')
    else:
        print('NO')

def f2():
    if cnt['00'] > 0:
        print('YES')
        return
    if cnt['01'] > 0 and cnt['10'] > 0:
        print('YES')
        return
    print('NO')

def f3():
    if cnt['000'] > 0:
        print('YES')
        return
    a = int(cnt['100'] > 0)
    b = int(cnt['010'] > 0)
    c = int(cnt['001'] > 0)
    if a + b + c > 1:
        print('YES')
        return
    if a and cnt['011']:
        print('YES')
        return
    if b and cnt['101']:
        print('YES')
        return
    if c and cnt['110']:
        print('YES')
        return
    print('NO')


def f4():
    if cnt['0000'] > 0:
        print('YES')
        return
    ms = ['0001', '1110', '0010', '1101',
          '0100', '1011', '1000', '0111',
          '1100', '0011', '1010', '0101',
          '1001', '0110']
    
    for i in range(len(ms) // 2):
        if cnt[ms[2*i]] > 0 and cnt[ms[2*i+1]] > 0:
            print('YES')
            return
    x = 0
    for i in range(4):
        if cnt[ms[i * 2]] > 0:
            x += 1
    if x > 1:
        print('YES')
        return
    ind = []
    if cnt['0001'] > 0:
        ind.append(3)
    if cnt['0010'] > 0:
        ind.append(2)
    if cnt['0100'] > 0:
        ind.append(1)
    if cnt['1000'] > 0:
        ind.append(0)
    
    for i in range(len(ms)):
        b = False
        for x in ind:
            if ms[i][x] == '0':
                b = True
        if not b: continue
        if cnt[ms[i]] > 0:
            print('YES')
            return
    print('NO')
    return

[f1, f2, f3, f4][k - 1]()


import sys

def ReadInput():
  return sys.stdin.read().splitlines()

def GetIA(s, delim=' '):
  return [int(x) for x in s.split(delim)]

def GetKey(flags):
  key = 0
  for a in flags:
    key <<= 1
    key += a
  # print(flags)
  # print(key)
  return key

def main():
  input = ReadInput()
  seen = dict()
  for s in input[1:]:
    seen[GetKey(GetIA(s))] = True

  for a in seen.keys():
    for b in seen.keys():
      if (a & b) == 0:
        print('YES')
        return

  print('NO')

main()

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def main():
    n,k = LI()
    s = set()
    for _ in range(n):
        t = LI()
        c = sum(t)
        if c == 0:
            return 'YES'
        s.add(tuple(t))

    l = list(s)
    ll = len(s)
    for i in range(ll):
        for j in range(i+1,ll):
            f = True
            for li in range(k):
                if l[i][li] == 1 and l[j][li] == 1:
                    f = False
                    break
            if f:
                return 'YES'

    return 'NO'


print(main())




n, k = [int(i) for i in input().split()]
s = set([int("".join(input().split()), base=2) for j in range(n)])
for t in s:
    for m in range(1 << k):
        if m in s:
            for i in range(k):
                if ((t >> i) & 1) and ((m >> i) & 1):
                    break
            else:
                print("YES")
                return
print("NO")
    


n, k = [int(i) for i in input().split()]
s = set([int("".join(input().split()), base=2) for j in range(n)])
for t in s:
    for m in range(1 << k):
        if m in s:
            for i in range(k):
                if ((t >> i) & 1) and ((m >> i) & 1):
                    break
            else:
                print("YES")
                return
print("NO")
    


import sys
N,K= list(map( int,input().split() ))

states=set([(0,0)])

for _ in range(N):
	can_solve=list( map(int,input().split()) )

	next_states=set()
	for (selected,bm) in states:
		cnts =[(bm>>i)&1 for i in range(K)][::-1]

		next_cnts=[cnts[i]+can_solve[i] for i in range(K)]
		next_selected=selected+1

		if max(next_cnts)<=next_selected/2 and next_selected>0:
			print("YES")

			return
		
		if max(next_cnts)<=1 and next_selected<=4:
			bin_num= int(''.join( map(str,next_cnts) ) ,2)
			next_states.add( (next_selected,bin_num) )
			
	states|=next_states

print("NO")



n,k=map(int, input().split())
vis = [0] * 17
for _ in range(n):
	a = list(map(int, input().split()))
	vis[sum(a[i]*(1<<i) for i in range(k))] = 1
flag=0
for i in range(16):
	for j in range(16):
		if i&j==0 and vis[i] and vis[j]: flag=1
print("YES" if flag else "NO")

n, k = [int(z) for z in input().split()]
ans = [0] * 16
for i in range(n):
    problem = [int(z) for z in input().split()]
    s = 0
    for j in range(k):
        s = s * 2 + problem[j]
    ans[s] += 1
#print(ans)
for i in range(16):
    for j in range(16):
        if ans[i] > 0 and ans[j] > 0 and (i & j) == 0:
            print("YES")
            return
print("NO")


n, k = [int(i) for i in input().split()]
s = set([int("".join(input().split()), base=2) for j in range(n)])

for t in s:
    for m in range(1 << k):
        if m in s:
            for i in range(k):
                if ((t >> i) & 1) and ((m >> i) & 1):
                    break
            else:
                print("YES")
                return
                
print("NO")

n, k = [int(i) for i in input().split()]

K = 1 << k
p = [0] * K

for i in range(n):
    pi = [int(j) for j in input().split()]
    pc = sum(pi[j] << j for j in range(k))
    p[pc] += 1

s = [0] * k

def go(i0, used):
    if i0 >= K: return False
    if p[i0]:
        s0 = s[:]
        ok = True
        used += 1
        for j in range(k):
            f = (i0 >> j) & 1
            assert f == 0 or f == 1
            s[j] += (i0 >> j) & 1
            if s[j] * 2 > used: ok = False
        if ok: return True
        if go(i0+1, used): return True
        s[:] = s0
        used -= 1
    return go(i0+1, used)

ans = "YES" if go(0, 0) else "NO"
print(ans)

def bel(mask, bit):
    return (mask & (1 << bit)) != 0
read = lambda: map(int, input().split())
n, k = read()
f = [0] * 100
for i in range(n):
    cur = int(''.join(input().split()), 2)
    cur ^= (1 << k) - 1
    f[cur] = 1
ans = 'NO'
if k == 1:
    if f[1]:
        ans = 'YES'
if k == 2:
    f1 = f2 = 0
    for i in range(4):
        if f[i]:
            if bel(i, 0): f1 = 1
            if bel(i, 1): f2 = 1
    if f1 and f2:
        ans = 'YES'
if k == 3:
    p = [0] * 3
    for i in range(8):
        if f[i]:
            for j in range(3):
                if bel(i, j): p[j] = 1
    for i in range(8):
        if f[i]:
            if bel(i, 0) and bel(i, 1) and p[2]: ans = 'YES'
            if bel(i, 0) and p[1] and bel(i, 2): ans = 'YES'
            if p[0] and bel(i, 1) and bel(i, 2): ans = 'YES'
if k == 4:
    for i in range(16):
        if f[i]:
            for j in range(16):
                if f[j]:
                    if (i | j) == 15:
                        ans = 'YES'
print(ans)


inp = input().split(" ")
n = int(inp[0])
k = int(inp[1])

s = set()
for i in range(n):
    a = input().split(' ')
    x = 0
    for j in range(k):
        x = 2 * x + int(a[j])
    s.add(x)

for i in range(16):
    if i in s:
        for j in range(16):
            if j in s:
                if i & j == 0:
                    print("YES")
                    return


print("NO")


def main():
    m, k = list(map(int, input().split()))
    all = set()
    zeros = ''
    for _ in range(k):
        zeros += '0'

    for _ in range(m):
        line = input().replace(' ', '')
        if line == zeros:
            print('YES')
            return
        all.add(line)

    for s1 in all:
        for s2 in all:
            if s1 == s2:
                continue
            bad = False
            for i in range(0, len(s1)):
                if s1[i] == '1' and s2[i] == '1':
                    bad = True
            if not bad:
                print('YES')
                return
    print('NO')


def __starting_point():
    main()

__starting_point()

def test(masks, wanted):
    for w in wanted:
        if w not in masks:
            return False
    return True

def any_test(masks, tests):
    for t in tests:
        if test(masks, t):
            return True
    return False

def inflate(perm):
    count = max(perm)
    masks = [[0 for i in range(len(perm))] for j in range(count)]

    for i in range(len(perm)):
        if perm[i] == 0:
            continue
        masks[perm[i] - 1][i] = 1
    return [tuple(m) for m in masks]

def gen(st, lev, teams, tests):
    if lev >= teams:
        if max(st) > 1:
            tests.append(inflate(st))
        return

    for i in range(teams + 1):
        st[lev] = i
        gen(st, lev + 1, teams, tests)

def gen_tests(teams):
    tests = []
    st = [0 for i in range(teams)]

    gen(st, 0, teams, tests)
    return tests

def back(masks, teams):
    tests = gen_tests(teams)
    return any_test(masks, tests)

def main():
    probs, teams = list(map(int, input().split()))
    masks = set()
    
    for i in range(probs):
        conf = tuple(list(map(int, input().split())))
        if 1 not in conf:
            print('YES')
            return
        masks.add(conf)

    if teams == 1:
        print('NO')
        return

    if teams == 2:
        good = test(masks, [(0, 1), (1, 0)])
    else:
        good = back(masks, teams)

    print('YES' if good else 'NO')

main()


n,k = [int(i) for i in input().split()]
if k == 1:
    alert = 0
    for time in range(n):
        term = str(input())
        if term == "0":
            alert = 1
            break
    print("NO") if alert == 0 else print("YES")
elif k == 2:
    (s1,s2) = (0,0)
    for time in range(n):
        term = str(input())
        if term == "0 0":
            (s1,s2) = (1,1)
            break
        else:
            if term == "0 1":
                s1 = 1
            elif term == "1 0":
                s2 = 1
        if (s1,s2) == (1,1):
            break
    print("YES") if (s1,s2) == (1,1) else print("NO")
elif k == 3:
    alert = 0
    s = {str(input()) for i in range(n)}
    if "0 0 0" in s:
        alert = 1
    if "0 0 1" in s:
        if "1 1 0" in s or "1 0 0" in s or "0 1 0" in s:
            alert = 1
    if "0 1 0" in s:
        if "1 0 1" in s or "1 0 0" in s or "0 0 1" in s:
            alert = 1
    if "1 0 0" in s:
        if "0 0 1" in s or "0 1 0" in s or "0 1 1" in s:
            alert = 1
    print("YES") if alert == 1 else print("NO")
elif k == 4:
    alert = 0
    s = {str(input()) for i in range(n)}
    s = list(s)
    #print(s)
    if "0 0 0 0" in s:
        alert = 1
    if "1 1 0 0" in s:
        for i in range(len(s)):
            if (s[i])[0] == '0' and (s[i])[2] == '0':
                alert = 1
    if "1 0 1 0" in s:
        for i in range(len(s)):
            if (s[i])[0] == '0' and (s[i])[4] == '0':
                alert = 1
    if "1 0 0 1" in s:
        for i in range(len(s)):
            if (s[i])[0] == '0' and (s[i])[6] == '0':
                alert = 1
    if "0 1 1 0" in s:
        for i in range(len(s)):
            if (s[i])[2] == '0' and (s[i])[4] == '0':
                alert = 1
    if "0 1 0 1" in s:
        for i in range(len(s)):
            if (s[i])[2] == '0' and (s[i])[6] == '0':
                alert = 1
    if "0 0 1 1" in s:
        for i in range(len(s)):
            if (s[i])[4] == '0' and (s[i])[6] == '0':
                alert = 1
    if "1 0 0 0" in s:
        for i in range(len(s)):
            if (s[i])[0] == '0':
                alert = 1
    if "0 1 0 0" in s:
        for i in range(len(s)):
            if (s[i])[2] == '0':
                alert = 1
    if "0 0 1 0" in s:
        for i in range(len(s)):
            if (s[i])[4] == '0':
                alert = 1
    if "0 0 0 1" in s:
        for i in range(len(s)):
            if (s[i])[6] == '0':
                alert = 1
    print("YES") if alert == 1 else print("NO")




v = [0 for i in range(20)]
n,m = list(map(int ,input().split()))
for i in range(n):
    x = list(map(int, input().split()))
    sum = 0
    for j in range(m):
        sum += x[j] * (1<<j)
    v[sum] = 1
flag = 0
for i in range(16):
    for j in range(16):
        if i&j == 0 and v[i] and v[j]:
            flag = 1

if flag:
    print("YES")
else :
    print("NO")


n, k = map(int, input().split())
exist = [False] * 16
zero = [False] * 4
for i in range(n):
    part = list(map(int, input().split()))
    P = [0] * (4 - k)
    for elem in part:
        P.append(elem)
    num = 0
    for j in range(4):
        if P[j] == 0:
            zero[j] = True
    for j in range(4):
        if P[3 - j] == 1:
            num += 2 ** j
    exist[num] = True
ans = False
if exist[0] or (exist[1] and zero[3]) or (exist[2] and zero[2]) or (exist[4] and zero[1]) or (exist[8] and zero[0]) or (exist[3] and exist[12]) or (exist[5] and exist[10]) or (exist[6] and exist[9]):
    ans = True
if ans:
    print('YES')
else:
    print('NO')