CodeEff/ECCO huggingface dataset:
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i&(-i)
        return s

    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += i&(-i)
            
left, right = 0, 10**9
geta = n+1
while right-left > 1:
    mid = (left+right)//2
    num = 0
    bit = BIT(2*n+1)
    sum_ = 0
    bit.add(sum_+geta, 1)
    for i in range(n):
        val = 1 if a[i] <= mid else -1
        sum_ += val
        num += bit.sum(sum_+geta-1)
        bit.add(sum_+geta, 1)

    if num > n*(n+1)//4:
        right = mid
    else:
        left = mid
print(right)


# Optimized solution
import math
n = int(eval(input()))
a = list(map(int, input().split()))

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i&(-i)
        return s

    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += i&(-i)
            
a_sorted = sorted(list(set(a)))
left, right = 0, len(a_sorted) # number of unique elements of a
while right-left > 1: # bisection search: O(logA)
    mid = (left+right)//2 # target index
    num = 0 # number of ranges with majority >= a_sorted[mid]
    bit = BIT(2*n+1) # initialize BIT: #regsum = bit.sum(regsum(+n))
    sum_ = 0 # region sum
    bit.add(sum_+n, 1)
    for i in range(n): # O(n)
        sum_ += 1 if a[i] >= a_sorted[mid] else -1 # update region sum by comaprison
        num += bit.sum(sum_+n) # add #ranges by sum_+n: O(logn)
        bit.add(sum_+n, 1) # increment BIT element at sum_+n(=count of interested regions)
    # print(bit.bit, left, right)

    # update search range
    if num >= math.ceil(n*(n+1)//4):
        left = mid
    else:
        right = mid
print((a_sorted[left]))
# Original solution
N=int(eval(input()))
A=[int(i) for i in input().split()]
sorted_A=sorted(A)

def add(B,a,n):
    x = a
    while x<=n:
        B[x]+=1
        x+=x&(-x)
        
def sums(B,a):
    x=a
    S=0
    while x!=0:
        S+=B[x]
        x-=x&(-x)
    return S
  
def invnumber(n,A):
  S=[0]*n
  A=sorted([(A[i],i) for i in range(n)])
  for i in range(1,n):
     S[A[i][1]]=i
  B=[0]*(n*2+1)
  invs=0
  for i in range(n):
      s=S[i]+n
      invs+=sums(B,s)
      add(B,s,n*2)
  return n*(n-1)//2-invs
  
def Check(x):
  S=[0]
  for i in range(N):
    if A[i]>sorted_A[x]:
      S.append(S[-1]+1)
    else:
      S.append(S[-1]-1)
  return invnumber(N+1,S)
      
l,r=0,N-1
while l<r:
  m=(l+r)//2
  if Check(m)>(N*(N+1)//4):
    r=m
  else:
    l=m+1
print((sorted_A[l]))


# Optimized solution
N=int(eval(input()))
A=[int(i) for i in input().split()]
sorted_A=sorted(A)

def add(B,a,n):
    x = a
    while x<=n:
        B[x]+=1
        x+=x&(-x)
        
def sums(B,a):
    x=a
    S=0
    while x!=0:
        S+=B[x]
        x-=x&(-x)
    return S
  
  
  
def invnumber(n,A):
  B=[0]*(n*2+1)
  invs=0
  for i in range(n):
      s=A[i]+n
      invs+=sums(B,s)
      add(B,s,n*2)
  return n*(n-1)//2-invs
  
def Check(x):
  S=[0]
  for i in range(N):
    if A[i]>sorted_A[x]:
      S.append(S[-1]+1)
    else:
      S.append(S[-1]-1)
  return invnumber(N+1,S)
      
l,r=0,N-1
while l<r:
  m=(l+r)//2
  if Check(m)>N*(N+1)//4:
    r=m
  else:
    l=m+1
print((sorted_A[l]))
# Original solution
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def init(bit, values):
    for i,v in enumerate(values):
        update(bit,i,v)

#A1 ~ Aiまでの和 O(logN)
def query(bit,i):
    res_sum = 0
    while i > 0:
        res_sum += bit[i]
        i -= i&(-i)
    return res_sum

#Ai += x O(logN)
def update(bit,i,x):
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return


n = int(eval(input()))
a = list(map(int, input().split()))
from collections import Counter
def sub(x):
    cumsum = [None] * n
    cumsum[0] = 1 if a[0]>=x else -1
    for i in range(1,n):
        cumsum[i] = cumsum[i-1] + (1 if a[i]>=x else -1)

    ### BIT 
    #A1 ... AnのBIT(1-indexed)
    bit = [0]*(2*n+2)
    update(bit, n+1, 1)
    ans = 0
    for v in cumsum:
        ans += query(bit, v+n+1)
        update(bit, n+v+1, 1)
    return ans

l = 0
r = 10**9+1
tmp = (n+1)*n//2
thre = tmp//2 + tmp%2
while l<r-1:
    m = (l+r)//2
    if sub(m)>=thre:
        l = m
    else:
        r = m
print(l)

# Optimized solution
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n = int(eval(input()))
a = list(map(int, input().split()))
from collections import Counter
def sub(x):
    l = [1 if item>=x else -1 for item in a]
    count = [0] * (2*n+2)
    count[n] = 1
    i = n
    cumsum = 1
    ans = 0
    for item in l:
        i += item
        if item==1:
            cumsum += count[i]
        else:
            cumsum -= count[i+1]
        ans += cumsum
        count[i] += 1
        cumsum += 1
    return ans

l = 0
r = 10**9+1
tmp = (n+1)*n//2
thre = tmp//2 + tmp%2
while l<r-1:
    m = (l+r)//2
    if sub(m)>=thre:
        l = m
    else:
        r = m
print(l)
# Original solution
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def add(i):
        while i < len(bit):
            bit[i] += 1
            i += i&-i
    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n = I()
    a = LI()
    k = ((n*(n+1)) >> 1) >> 1
    l = 0
    r = max(a)+1
    while r-l > 1:
        m = (l+r) >> 1
        b = [2*(i < m)-1 for i in a]
        s = [0]
        for i in b:
            s.append(s[-1]+i)
        b = list(set([i for i in s]))
        b.sort()
        s = [bisect.bisect_left(b,i)+2 for i in s]
        bit = [0]*(max(s)+1)
        res = 0
        for i in s:
            res += sum(i)
            add(i+1)
        if res <= k:
            l = m
        else:
            r = m
    print(l)
    return

#Solve
if __name__ == "__main__":
    solve()


# Optimized solution
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def add(i):
        while i < len(bit):
            bit[i] += 1
            i += i&-i
    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n = I()
    a = LI()
    f = list(set(a))
    f.sort()
    c = [bisect.bisect_left(f,i) for i in a]
    k = ((n*(n+1)) >> 1) >> 1
    l = 0
    r = len(f)
    while r-l > 1:
        m = (l+r) >> 1
        b = [2*(i < m)-1 for i in c]
        s = [0]
        for i in b:
            s.append(s[-1]+i)
        b = list(set([i for i in s]))
        b.sort()
        s = [bisect.bisect_left(b,i)+1 for i in s]
        bit = [0]*(max(s)+1)
        res = 0
        for i in s:
            res += sum(i)
            add(i+1)
        if res <= k:
            l = m
        else:
            r = m
    print((f[l]))
    return

#Solve
if __name__ == "__main__":
    solve()
# Original solution
from operator import itemgetter


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)



n =int(eval(input()))
a = list(map(int, input().split()))

def solve(val):
    ruiseki = [0] * (n + 1)
    for i, num in enumerate(a):
        if num >= val:
            ruiseki[i + 1] = ruiseki[i] + 1
        else:
            ruiseki[i + 1] = ruiseki[i] - 1
    b = sorted(enumerate(ruiseki), key = itemgetter(1))
    for i in range(n + 1):
        bit.bit[i] = 0
    res = 0
    for i, _ in b:
        bit.add(i, 1)
        res += bit.get_sum(0, i)
        if res >= cnt:
            return True
    return False


cnt = 0
for i in range(n):
    cnt += n - i
cnt = (cnt + 1) // 2

bit = BIT(n + 1)
ok = 0
ng = 10**9 + 1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

# Optimized solution
from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)



n =int(eval(input()))
a = list(map(int, input().split()))
a_sorted = sorted(a)


def solve(val):
    val = a_sorted[val]
    ruiseki = [0] * (n + 1)
    for i, num in enumerate(a):
        if num >= val:
            ruiseki[i + 1] = ruiseki[i] + 1
        else:
            ruiseki[i + 1] = ruiseki[i] - 1
    b = sorted(enumerate(ruiseki), key = itemgetter(1))
    for i in range(n + 1):
        bit.bit[i] = 0
    res = 0
    for i, _ in b:
        bit.add(i, 1)
        res += bit.get_sum(0, i)
        if res >= cnt:
            return True
    return False


cnt = 0
for i in range(n):
    cnt += n - i
cnt = (cnt + 1) // 2

bit = BIT(n + 1)
ok = 0
ng = n
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print((a_sorted[ok]))
# Original solution
N=int(eval(input()))
alist=list(map(int,input().split()))
numlist=[]
if len(alist)==1:
  print((alist[0]))
  exit()
i=1
for x in range(0,((N+1)//2)):
  numlist+=[alist[x]]*i
  i+=2
i=2
for x in range(N-1,((N+1)//2)-1,-1):
  numlist+=[alist[x]]*i
  i+=2
numlist.sort()
print((numlist[len(numlist)//2+1]))

# Optimized solution
N=int(eval(input()))
alist=list(map(int,input().split()))
numdict={}
amount=0
if len(alist)==1:
  print((alist[0]))
  exit()

for x in alist:
  if x in numdict:
    numdict[x]+=1
  else:
    numdict[x]=1

medilist=alist.copy()

newmedilist=[]
for i in range(1,N):
  if i%2:
    for x in range(0,N-i):
      num=max(medilist[x],alist[x+i])
      numdict[num]+=1
      newmedilist.append(num)
  else:
    for x in range(0,N-i):
      num=min(medilist[x],alist[x+i])
      numdict[num]+=1
      newmedilist.append(num)
  medilist=newmedilist

b=N*(N+1)//4+1

numlist=sorted(numdict.keys())

c=0
for x in numlist:
  c+=numdict[x]
  if c>=b:
    break

print(x)
# Original solution
from itertools import combinations

S = str(eval(input()))
pos = [i for i in range(len(S)-1)]
insert_indices = [comb for i in range(len(S)) for comb in combinations(pos, i)]

ans = 0

for inds in insert_indices:
    cur_ix = 0
    cur_ans = 0
    while cur_ix < len(S):
        cur_ans += int(S[cur_ix])
        if cur_ix == len(S)-1:
            break
        if cur_ix in inds:
            ans += cur_ans
            cur_ans = 0
        else:
            cur_ans *= 10
        cur_ix += 1
    ans += cur_ans
    
print(ans)


# Optimized solution
from itertools import combinations

S = str(eval(input()))
n = len(S)

ans = 0
for i in range(1 << (n-1)):
    cur_ans = int(S[0])
    for j in range(n-1):
        add_plus = (i >> (n-2-j)) & 1
        if add_plus:
            ans += cur_ans
            cur_ans = 0
        else:
            cur_ans *= 10
        cur_ans += int(S[j+1])
    ans += cur_ans
print(ans)
# Original solution
from itertools import permutations
import sys, re
inp = sys.stdin.readline().strip()
perms = []
used = []
total = 0
#orig = inp

def checkOrder(check, inp):
    count = 0
    for i in range(len(check)):
        if check[i] == '+':
            continue
        elif check[i] == inp[count]:
            count += 1
        else:
            return False
    return True


for i in range(0, len(inp)):
    withPlus = inp + '+' * i
    perms = [''.join(p) for p in permutations(withPlus)]

    for perm in perms:
        if not re.match(r'.*\+\+.*', perm) and not perm[0] == '+' and not perm[-1] == '+':
            if checkOrder(perm, inp) and not perm in used:
                total += eval(perm)
                used.append(perm)

print(total)


# Optimized solution
import sys
perm = sys.stdin.readline().strip()
total = 0

# Add n * '+' to inp
def addPlus(inp, n):
    total = 0
    possible = [inp]
    orig = inp

    for i in range(1, len(orig)):
        possible.append(orig[:i] + '+' + perm[i:])

    for i in range(1, n):
        curr = possible[:]
        for item in curr:
            for j in range(1, len(item)):
                processed = item[:j] + '+' + item[j:]
                if processed not in possible:
                    if '++' not in processed:
                        possible.append(processed)

    for item in possible:
        total += eval(item)

    return total


print((addPlus(perm, len(perm) - 1)))
# Original solution
import itertools

N, M = list(map(int,input().split()))


def main():
	k = []
	s = []
	answers = []

	for i in range(M + 1):
		inputs = list(map(int,input().split()))
		if i == M:
			answers = inputs.copy()
		else:
			k.append(inputs[0])
			s.append(inputs[1:])

	allCandidates = []
	for i in range(N + 1):
		candidates = [1] * i + [0] * (N - i)
		allCandidates.extend(list(itertools.permutations(candidates)))

	result = []
	for c in allCandidates:
		ok = True
		for i, ss in enumerate(s):
			sumBulk = 0
			for sNumber in ss:
				sumBulk += c[sNumber - 1]
			if sumBulk % 2 != answers[i]:
				ok = False
		if ok:
			result.append(c)

	print((len(list(set(result)))))

if __name__ == '__main__':
	main()

# Optimized solution
import itertools

N, M = list(map(int,input().split()))


def main():
	k = []
	s = []
	answers = []

	for i in range(M + 1):
		inputs = list(map(int,input().split()))
		if i == M:
			answers = inputs.copy()
		else:
			k.append(inputs[0])
			s.append(inputs[1:])

	allCandidates = (list(itertools.product(list(range(2)), repeat=N)))

	result = []
	for c in allCandidates:
		ok = True
		for i, ss in enumerate(s):
			sumBulk = 0
			for sNumber in ss:
				sumBulk += c[sNumber - 1]
			if sumBulk % 2 != answers[i]:
				ok = False
		if ok:
			result.append(c)

	print((len(list(set(result)))))

if __name__ == '__main__':
	main()
# Original solution
n, m = list(map(int, input().split()))
k = [list(map(int, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
answer = 0
## k = sorted(k, reverse=True, key=lambda x: len(x))

all = [] # 全てのスイッチの状態
for i in range(0, 2**n):
  all.append(list(str(format(i, 'b').zfill(n))))

for a in all:
  for index in range(len(k)):
    switch_count = 0 
    for switch in k[index]: #1,2
        switch_count+=int(a[switch-1])
    #一つの電球に繋がってる全てのスイッチ確認終了
    if switch_count%2 == p[index]:
      if index == len(k)-1:
      	answer+=1
      continue
    break

print(answer)
    

# Optimized solution
#!/usr/bin/env python3

def main():
    N,M = list(map(int,input().split()))
    K = []
    s = []
    answer = 0
    for _ in range(M):
        ks = list(map(int,input().split()))
        K.append(ks[0])
        s.append(ks[1:])
    p = list(map(int,input().split()))

    for switch in range(0,2**N):

        for j in range(M):
            count = 0
            for k in s[j]:
                if 1 << k-1 & switch:
                    count += 1
            if count%2 == p[j]:
                continue
            else:
                break
        else:
            answer +=1

        
    print(answer)


if __name__ == '__main__':
    main()
# Original solution
n,m = list(map(int,input().split()))
l_list = [list(map(int,input().split())) for i in range(m)] 
p = list(map(int,input().split()))
output = 0

for i in range(2 ** n):
  lights = []
  for j in range(n+1):
    if ((i >> j) & 1):
      lights.append(j+1)
      
  for inde, l in enumerate(l_list):
    if len(set(l[1:]) & set(lights)) % 2 != p[inde]:
      break
  else:
    output += 1
print(output)

# Optimized solution
n,m = list(map(int,input().split()))
l_list = [list(map(int,input().split())) for i in range(m)] 
p = list(map(int,input().split()))
output = 0

for i in range(2 ** n):
  lights = []
  for j in range(n+1):
    if ((i >> j) & 1):
      lights.append(j+1)
      
  for k, l in enumerate(l_list):
    if len(set(l[1:]) & set(lights)) % 2 != p[k]:
      break
  else:
    output += 1
print(output)
# Original solution
n, m = list(map(int, input().split()))
bits = '0b' + '1' * n
s = []

for _ in range(m):
    i = [int(i) for i in input().split()]
    s.append(i[1:])

p = [int(i) for i in input().split()]
c = 0
for i in range(2**n):
    l = bin(i)[2:]
    b = (n - len(l)) * '0' + l
    addable = True
    for h, j in enumerate(s):
        d = 0
        for k in j:
            d += int(b[k - 1])
        if addable:
            addable = d % 2 == p[h]
    if addable:
        c += 1
print(c)

# Optimized solution
n, m = list(map(int, input().split()))
s = [[int(i) for i in input().split()[1:]] for _ in range(m)]
p = [int(i) for i in input().split()]
c = 0

for i in range(2**n):
    addable = True
    for j in range(m):
        d = sum(2 ** (k - 1) for k in s[j])
        if bin(i & d).count('1') % 2 != p[j]:
            addable = False
            break
    if addable:
        c += 1
print(c)
# Original solution
N, M = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(M)]
P = list(map(int, input().split()))

ans = 0
for bit in range(2 ** N):
    ons = set([i + 1 for i in range(N) if bit >> i & 1])
    flg = True
    for i in range(M):
        k, *s = X[i]
        p = P[i]
        flg &= len(set(s) & ons) % 2 == p
    ans += int(flg)
    
print(ans)


# Optimized solution

N, M = list(map(int, input().split()))
K = []
X = []
for _ in range(M):
    k, *x = list(map(int, input().split()))
    K.append(k)
    X.append(x)
P = list(map(int, input().split()))

ans = 0
for bit in range(2 ** N):
    light_on = [False] * M
    for i in range(M):
        tmp = 0
        for s in X[i]:
            tmp += bit >> (s - 1) & 1
        light_on[i] = tmp % 2 == P[i]

    ans += all(light_on)

print(ans)
# Original solution
# -*- coding: utf-8 -*-
"""
Created on Sun May 26 20:56:00 2019

@author: Yamazaki Kenichi
"""

N,M = list(map(int,input().split()))
ks = [list(map(int,input().split())) for i in range(M)]
p = list(map(int,input().split()))

ans = 0
for i in range(2**N):
    t = '{:010b}'.format(i)
    flg = True
    for j in range(M):
        tmp = 0
        for k in range(ks[j][0]):
            tmp += int(t[-ks[j][k+1]])
#        print(i,j,t,tmp,ans)
        if tmp%2 == p[j]:
            continue
        else:
            flg = False
            break
#    print(i,j,t,tmp,ans,flg)
    if flg:
        ans += 1

            
print(ans)

# Optimized solution
# -*- coding: utf-8 -*-
"""
Created on Mon May 27 21:28:42 2019

@author: Yamazaki Kenichi
"""

N, M = list(map(int,input().split()))
ks = [list(map(int,input().split())) for i in range(M)]
p = list(map(int,input().split()))

S = [0 for i in range(M)]
for i in range(M):
    for j in range(1,ks[i][0]+1):
        S[i] += 2**(ks[i][j]-1)

ans = 0
for i in range(2**N):
    flg = True
    for j in range(M):
        if ('{:010b}'.format(S[j]&i)).count('1') % 2 == p[j]:
            continue
        else:
            flg = False
            break
    if flg:
        ans += 1
print(ans)
# Original solution
n, m = list(map(int, input().split()))


lst_sw = []
for _ in range(m):
    lst_sw.append(list(map(int, input().split())))
lst_p = list(map(int, input().split()))


ans = 0
for bits in range(2 ** n):
    judge = True
    for i in range(m):
        cnt = 0
        for j in range(1, len(lst_sw[i])):
            sw = lst_sw[i][j]
            if (bits >> (sw - 1)) & 1:
            # if (1 << (sw - 1)) & bits: # こちらの判定でも良い
                cnt += 1
        if cnt%2 != lst_p[i]:
            judge = False
    if judge:
        ans += 1


print(ans)


# Optimized solution
n, m = list(map(int, input().split()))


lst_sw = []
for _ in range(m):
    lst_sw.append(list(map(int, input().split())))
lst_p = list(map(int, input().split()))


ans = 0
for bits in range(2 ** n):
    judge = True
    for i in range(m):
        cnt_sw_on = 0
        for j in range(1, len(lst_sw[i])):
            sw = lst_sw[i][j]
            if (bits >> (sw - 1)) & 1:
                cnt_sw_on += 1
        if cnt_sw_on % 2 != lst_p[i]:
            judge = False
            break
    if judge:
        ans += 1


print(ans)
# Original solution
n, m = list(map(int, input().split()))


lst_sw = []
for _ in range(m):
    lst_sw.append(list(map(int, input().split())))
lst_p = list(map(int, input().split()))


ans = 0
for bits in range(2 ** n):
    judge = True
    for i in range(m):
        cnt_sw_on = 0
        for j in range(1, len(lst_sw[i])):
            sw = lst_sw[i][j]
            if (bits >> (sw - 1)) & 1:
                cnt_sw_on += 1
        if cnt_sw_on % 2 != lst_p[i]:
            judge = False
            break
    if judge:
        ans += 1


print(ans)


# Optimized solution
n, m = list(map(int, input().split()))


lst_sw = []
for _ in range(m):
    lst_sw.append(list(map(int, input().split())))
lst_p = list(map(int, input().split()))


ans = 0
for bits in range(2 ** n):
    judge = True
    for i in range(m):
        cnt_sw_on = 0
        for j in range(1, len(lst_sw[i])):
            sw = lst_sw[i][j]
            if (1 << (sw - 1)) & bits:
                cnt_sw_on += 1
        if cnt_sw_on % 2 != lst_p[i]:
            judge = False
            break
    if judge:
        ans += 1


print(ans)
# Original solution
n,m = list(map(int, input().split()))
S = [list(map(int, input().split())) for i in range(m)]
P = list(map(int, input().split()))
c = 0
a = 0
for a in range(2**n):
  a2 = format(a, 'b').zfill(n)
  d = 0
  for i in range(m):
    o = 0
    for j in range(S[i][0]):
      o += int(a2[S[i][j+1]-1])
    if o % 2 == P[i]:
      d += 1
  if d == m:
    c += 1
print(c)

# Optimized solution
N,M = list(map(int,input().split()))
B = [tuple(map(int,input().split())) for _ in range(M)]
P = tuple(map(int,input().split()))

ans = 0

for i in range(2**N):
    flag = True
    for k in range(M):
        on = 0
        
        for j in range(B[k][0]):
            if i>>(B[k][j+1]-1) & 1:
                on += 1
        
        if on%2 != P[k]:
            flag = False
            
    if flag:
        ans += 1
        
print(ans)