Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from bisect import bisect_left
def main():
    N, Q = map(int, input().split())
    W = [tuple(map(int, input().split())) for _ in range(N)]
    W.sort(key=lambda x:x[2])
    
    D = [int(input()) for _ in range(Q)]
    ans = [-1]*Q
    skip = [-1]*Q
    for s, t, x in W:
        l = bisect_left(D, s-x)
        r = bisect_left(D, t-x)
        while l < r:
            if skip[l] == -1:
                ans[l] = x
                skip[l] = r
                l+=1
            else:
                l = skip[l]
    for a in ans:
        print(a)
main()  

### FIXED CODE ###

from bisect import bisect_left
def main():
    N, Q = map(int, input().split())
    W = [tuple(map(int, input().split())) for _ in range(N)]
    W.sort(key=lambda x:x[2])
    
    D = [int(input()) for _ in range(Q)]
    ans = [-1]*Q
    skip = [-1]*Q
    for s, t, x in W:
        l = bisect_left(D, s-x)
        r = bisect_left(D, t-x)
        while l < r:
            if skip[l] == -1:
                ans[l] = x
                skip[l] = r
                l+=1
            else:
                l = skip[l]
    for a in ans:
        print(a)
main()
### BUGGY CODE ###

import sys
input=sys.stdin.readline

S = input()
T = input()
DP = [[""]*(len(T)+1) for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            DP[i+1][j+1] = DP[i][j] + S[i]
        else:
            if len(DP[i+1][j]) > len(DP[i][j+1]):
                DP[i+1][j+1] = DP[i+1][j]
            else:
                DP[i+1][j+1] = DP[i][j+1]
print(DP[-1][-1])


### FIXED CODE ###

import sys
input=sys.stdin.readline

S = input().rstrip()
T = input().rstrip()
DP = [[0]*(len(T)+1) for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            DP[i+1][j+1] = DP[i][j]+1
        else:
            DP[i+1][j+1] = max(DP[i+1][j],DP[i][j+1])

m,n = len(S),len(T)
ans = ''
while m>0 and n>0:
    if DP[m][n] == DP[m][n-1]:
        n-=1
    elif DP[m][n] == DP[m-1][n]:
        m -= 1
    else:
        m,n = m-1,n-1
        ans = T[n]+ans
print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    S = 1
    for x in A:
        S *= x
    flag = True
    for x in A:
        if gcd(S//x, x) == 1:
            continue
        else:
            flag = False
            break
    if flag:
        print("pairwise coprime")
    else:
        g = A[0]
        for i in range(1, N):
            g = gcd(A[i], g)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    M = max(A)
    X = [i for i in range(M+1)]
    S = [True for i in range(M+1)]
    S[0] = False
    S[1] = False

    for i in range(1, M+1):
        if S[i]:
            for j in range(i, M+1, i):
                if S[j]:
                    S[j] = False
                    X[j] = i
    flag = True
    s = set()
    ls = 0
    for x in A:
        tmp = set()
        while(X[x] != 1):
            tmp.add(X[x])
            x //= X[x]
        l = len(tmp)
        s |= tmp
        if len(s) == ls + l:
            ls += l
            continue
        else:
            flag = False
            break

    if flag:
        print("pairwise coprime")
    else:
        for x in A[1:]:
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()
### BUGGY CODE ###

q=int(input())
b=[]
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
a=primes(100000)
for i in range(q):
    l,r=map(int,input().split())
    cnt=0
    for j in a:
        if l<=j<=r:
            if (j+1)//2 in a:
                cnt+=1
        if r<=j:
            break
    print(cnt)


### FIXED CODE ###

import math
p=[0 for k in range(100000)]
p[1]=1
for k in range(3,100000,2):
    f=1
    for l in range(2,int(math.sqrt(k))+1):
        if k%l==0:
            f=0
            break
    if f==1:
        p[k]=1
c=[0 for k in range(100000)]
c[3]=1
for k in range(3,100000,2):
    if p[k] and p[(k+1)//2]:
        c[k]=1
for k in range(1,100000):
    c[k]+=c[k-1]
for k in range(int(input())):
    l,r=map(int,input().split())
    print(c[r]-c[l-1])
### BUGGY CODE ###

# AtCoder Beginner Contest 134 E - Sequence Decomposing

import sys

N = int(input())
ans = []

for n in range(N):
    now = int(sys.stdin.readline().strip())
    for a in ans:
        if a[-1] < now:
            a.append(now)
            break
    else:
        appending = [now]
        ans.append(appending)

print(len(ans))


### FIXED CODE ###

# AtCoder Beginner Contest 134 E - Sequence Decomposing

import sys
import bisect

N = int(input())
now = int(sys.stdin.readline().strip())
ans = [now]

for n in range(N - 1):
    now = int(sys.stdin.readline().strip())

    if now > ans[0]:
        ans[0] = now
    elif ans[-1] >= now:
        ans.append(now)
    else:
        # 2部探査で行進位置を探る
        left = 0  # 挿入不可能
        right = len(ans) - 1  # 挿入可能

        while right - left > 1:
            mid = (right + left) // 2
            if now > ans[mid]:
                right = mid
            else:
                left = mid

        ans[right] = now

print(len(ans))

    # if ans:  # 最初の入力以外であり、すでに追加対象のリストが存在する
    #     if ans[0][-1] < now:
    #         ans[0].append(now)
    #     elif ans[-1][-1] >= now:
    #         appending = [now]
    #         ans.append(appending)
    #     else:
    #         # 二分探索で追加するリストの位置を特定する
    #         left = 0   # 追加できない  ans[left][-1] > now
    #         right = len(ans) - 1  # ans[right][-1] < now
    #
    #         while right - left > 1:
    #             mid = (right - left) // 2
    #             if ans[mid][-1] < now:
    #                 right = mid
    #             else:
    #                 left = mid
    #         ans[right].append(now)
    # else:
    #     appending = [now]
    #     ans.append(appending)

    # for a in ans:
    #     if a[-1] < now:
    #         a.append(now)
    #         break
    # else:
    #     appending = [now]
    #     ans.append(appending)

# print(len(ans))
### BUGGY CODE ###

import sys,math,copy
# import numpy as np
input = sys.stdin.readline
S = reversed(input().strip())

# dp = np.zeros((13), dtype=int)
# dp_ = np.zeros((13), dtype=int)
dp = [0] * 13
dp_ = [0] * 13
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for s in S:
    if s == '?':
        for d in range(10):
            m = mod13_list[(d * mul)]
            for pm in range(13):
                dp[mod13_list[(pm+m)]] += dp_[pm]

    else:
        si = int(s)
        m = mod13_list[(si * mul)]
        for pm in range(13):
            dp[mod13_list[(pm+m)]] = dp_[pm]

    # dp_ = dp % divisor
    # dp = dp * 0 # np.zeros((13), dtype=int)
    for i in range(13):
        dp_[i] = dp[i] % divisor
        dp[i] = 0
    mul = mod13_list[(mul * 10)]
print(dp_[5])

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import functools
import operator


def prod(arr):
    return functools.reduce(operator.mul, arr)


def main():
    N, K = (int(x) for x in input().split(" "))
    A = [int(x) for x in input().split(" ")]
    lastest_score = prod(A[0:K])
    for i in range(1, N-K+1):
        current_score = prod(A[i:i+K])
        if lastest_score < current_score:
            print("Yes")
        else:
            print("No")
        lastest_score = current_score


if __name__ == '__main__':
    main()


### FIXED CODE ###

def prod(arr):
    s = 0
    for x in arr:
        s += x
    return s


def main():
    N, K = (int(x) for x in input().split(" "))
    A = [int(x) for x in input().split(" ")]
    lastest_score = prod(A[0:K])
    result = ["No"] * (N-K+1)
    for i in range(1, N-K+1):
        current_score = lastest_score - A[i-1] + A[i + K-1]
        if lastest_score < current_score:
            result[i] = "Yes"
        lastest_score = current_score
    [print(x) for x in result[1:]]


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
mod=10**9+7
b,w=map(int,input().split())
n=b+w

def power(x,n):
    if n==0:
        return 1
    elif n%2:
        return power(x,n//2)**2*x%mod
    else:
        return power(x,n//2)**2%mod
def modinv(n):
    return power(n,mod-2)

factorial=[1]
for i in range(1,n+1):
    factorial.append(factorial[i-1]*i%mod)
inverse=[0]*(n+1)
inverse[-1]=modinv(factorial[-1])
for i in range(n)[::-1]:
    inverse[i]=inverse[i+1]*(i+1)%mod
def comb(n,r):
    if n<r:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod

Pb,Pw=[0]*n,[0]*n
inv2=modinv(2)
for i in range(1,n):
    Pb[i]=(Pb[i-1]+comb(i-1,b-1)*power(inv2,i))%mod
    Pw[i]=(Pw[i-1]+comb(i-1,w-1)*power(inv2,i))%mod
for i in range(n):
    print((1-Pb[i]+Pw[i])*inv2%mod)

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
mod=10**9+7
b,w=map(int,input().split())
n=b+w

def power(x,n):
    if n==0:
        return 1
    elif n%2:
        return power(x,n//2)**2*x%mod
    else:
        return power(x,n//2)**2%mod
def modinv(n):
    return power(n,mod-2)

factorial=[1]
for i in range(1,n+1):
    factorial.append(factorial[i-1]*i%mod)
inverse=[0]*(n+1)
inverse[-1]=modinv(factorial[-1])
for i in range(n)[::-1]:
    inverse[i]=inverse[i+1]*(i+1)%mod
def comb(n,r):
    if n<r or r<0:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod

Pb,Pw=[0]*n,[0]*n
inv2=modinv(2)
P=[1]*(n+1)
for i in range(1,n+1):
    P[i]=P[i-1]*inv2%mod
for i in range(1,n):
    Pb[i]=(Pb[i-1]+comb(i-1,b-1)*P[i])%mod
    Pw[i]=(Pw[i-1]+comb(i-1,w-1)*P[i])%mod
for i in range(n):
    print((1-Pb[i]+Pw[i])*inv2%mod)
### BUGGY CODE ###

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
A = list(map(int, input().split()))
A.sort()

ml = len(format(A[-1], 'b'))
bA = [list(format(val, '061b')) for val in A]
bAT = list(zip(*bA))
bAT = bAT[::-1]

cnt = 0
for i, bat in enu(bAT):
    z = bat.count('0')
    o = bat.count('1')
    cnt += z*o*(2**(i))
    cnt %= MOD

print(cnt)



### FIXED CODE ###

import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
A = np.array(input().split(), np.int)
#print(A)

cnt = 0
for i in range(61):
    B = (A>>i)&1
    z = np.count_nonzero(B)
    cnt += z*(N-z)*(2**(i))
    cnt %= MOD

print(cnt)
### BUGGY CODE ###

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

se = set()
dic = dict()
for i in range(N):
    if A[i] in se:
        dic[A[i]] += 1
    else:
        se.add(A[i])
        dic.update({A[i]: 1})
        
result = [0]*N
for i in range(N):
    for k in dic.keys():
        if A[i] == k:
            result[i] += (dic[k]-1)*(dic[k]-2)//2
        else:
            result[i] += (dic[k])*(dic[k]-1)//2

print("\n".join(list(map(str, result))))


### FIXED CODE ###

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

se = set()
dic = dict()

for i in range(N):
    if A[i] in se:
        dic[A[i]] += 1
    else:
        se.add(A[i])
        dic.update({A[i]: 1})

c = 0
for k in dic.keys():
    c += (dic[k])*(dic[k]-1)//2

result = [0]*N
for i in range(N):
    result[i] = c - (dic[A[i]])*(dic[A[i]]-1)//2 + (dic[A[i]]-1)*(dic[A[i]]-2)//2

print("\n".join(list(map(str, result))))
### BUGGY CODE ###

def main():
	n, k = map(int, input().split())
	costs = list(map(int, input().split()))
	before = [0 for i in range(k)]
	for step in range(1, n):
		nex_val = float("inf")
		for j in range(1,k+1):
			if j <= step: 
				nex_val = min( abs(costs[step] - costs[step-j]) + before[k-j], nex_val)
		before = before[1:] + [nex_val]
	return before[-1]
print(main())


### FIXED CODE ###

def main():
	n, k = map(int, input().split())
	costs = list(map(int, input().split()))
	v= [0] * n
	for step in range(1, n):
		v[step] = min([v[j] + abs(costs[step]-costs[j]) for j in range(max(0,step-k), step)])
	return v[-1]
print(main())
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def abc159d(n, arr):
    dic = {}
    for a in arr:
        if a in dic:
            dic[a] += 1
        else:
            dic[a] = 1
    
    # delete non-paired ball
    del_list = []
    for k, val in dic.items():
        if val == 1:
            del_list.append(k)
    for item in del_list:
        del dic[item]

    ans = []
    for a in arr:
        sum = 0
        for k, val in dic.items():
            n = val
            if k == a:
                n -= 1

            sum += n * (n-1) // 2

        ans.append(sum)

    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
    arr = input().split(" ")
    
    ans = abc159d(n, arr)
    
    # output
    for a in ans:
        print(a)
# else:
    # do nothing


### FIXED CODE ###

# -*- coding: utf-8 -*-

def abc159d(n, arr):
    dic = {}
    for a in arr:
        if a in dic:
            dic[a] += 1
        else:
            dic[a] = 1
    
    # delete non-paired ball
    del_list = []
    for k, val in dic.items():
        if val == 1:
            del_list.append(k)
    for item in del_list:
        del dic[item]

    typ_ans = 0
    for val in dic.values():
        typ_ans += val * (val-1) // 2
    
    ans = []
    for a in arr:
        sum = typ_ans
        if a in dic:
            sum -= dic[a] * (dic[a]-1) // 2
            new_val = dic[a] - 1
            sum += new_val * (new_val-1) // 2

        ans.append(sum)

    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
    arr = input().split(" ")
    
    ans = abc159d(n, arr)
    
    # output
    for a in ans:
        print(a)
# else:
    # do nothing
### BUGGY CODE ###

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

count = 0
for x in range(k+1):
    if s - x > 2 * k:
        continue
    for y in range(k+1):
        if x - (x+y) > k:
            continue
        for z in range(k+1):
            if x + y + z == s:
                count += 1

print(count)


### FIXED CODE ###

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

count = 0
for x in range(k+1):
    if s - x > 2 * k:
        continue
    for y in range(k+1):
        if s - (x+y) > k or s -(x+y) < 0:
            continue
        count += 1

print(count)
### BUGGY CODE ###

N=int(input())
X=[int(input())]
for i in range(N-1):
  a=int(input())
  if a>X[-1]:
    X[-1]=a
  elif X[0]>=a:
    X.insert(0,a)
  else:
    for j,x in enumerate(X):
      if x>=a:
        X[j-1]=a
        break
print(len(X))

### FIXED CODE ###

N=int(input())
from collections import deque
d = deque([int(input())]) 
import bisect

for i in range(N-1):
  a=int(input())
  if a>d[-1]:
    d[-1]=a
  elif d[0]>=a:
    d.appendleft(a)
  else:
    i=bisect.bisect_left(d,a)
    d[i-1]=a
print(len(d))
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
li2 = sorted(li)
for i in range(n):
    print(li.index(i+1) + 1, end = " ")

### FIXED CODE ###

import numpy as np
n=int(input())
a=list(map(int,input().split()))
  
x = np.argsort(a)
for i in range(n):
  print(x[i]+1)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import sys


def exhaustive(n, target, lst):
    if n == target:
        return True
    if n > target or lst == []:
        return False
    else:
        for i, val in enumerate(lst, 1):
            if exhaustive(n + val, target, lst[i:]):
                return True
    return False


def main(data, targets):
    for target in targets:
        if exhaustive(0, target, data):
            print("yes")
        else:
            print("no")


if __name__ == "__main__":
    lst = [val.split() for val in sys.stdin.read().splitlines()]
    data = [int(n) for n in lst[1]]
    targets = [int(n) for n in lst[3]]
    main(data, targets)

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys


def exhaustive(lst, size):
    result = []
    for i in range(0, 1 << size):
        total = 0
        for j in range(0, size):
            if (i & 0x01) == 1:
                total += lst[j]
            i = i >> 1
        result.append(total)
    return result


if __name__ == "__main__":
    lst = [val.split() for val in sys.stdin.read().splitlines()]
    n, data, m, targets = [[int(n) for n in inner_lst] for inner_lst in lst]
    result = exhaustive(data, int(n[0]))
    print("\n".join(["yes" if x in result else "no" for x in targets]))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N = int(input())
a = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            a = a + int(gcd(i,j,k))
print(a)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N = int(input())
a = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            a = a + int(gcd(i,j,k))
print(a)
### BUGGY CODE ###

n=int(input())

cnt=0

for i in range(n):
        for j in range(n):
                if 0<i*j<n:
                        cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
m=n-1

p=int(m**(1/2))
c=0

for i in range(1,p+1):
        c+=(m//i-(i-1))*2-1
        
print(c)
### BUGGY CODE ###

def main():
  _max = max
  h, w = map(int, input().split())
  s = [input() + '#' for _ in range(h)]
  s.append('#' * (w + 1))

  rt = [[-1] * w for _ in range(h)]

  tstart = [-1] * (w + 1)
  for i in range(h + 1):
    si = s[i]
    ystart = -1
    for j in range(w + 1):
      if si[j] == '#':
        if ystart != -1:
          for k in range(ystart, j):
            rt[i][k] += j - ystart
          ystart = -1
        if tstart[j] != -1:
          for k in range(tstart[j], i):
            rt[k][j] += i - tstart[j]
          tstart[j] = -1
      else:
        if ystart == -1:
          ystart = j
        if tstart[j] == -1:
          tstart[j] = i

  print(_max(_max(l) for l in rt))

main()

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)]
s.append('#' * w)

yoko = [[0] * w for _ in range(h)]
for i in range(h):
  if s[i][0] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, w + 1):
    if s[i][j] == '#':
      if start != -1:
        for k in range(start, j):
          yoko[i][k] = j - start
        start = -1
    else:
      if start == -1:
        start = j

tate = [[0] * w for _ in range(h)]
for i in range(w):
  if s[0][i] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, h + 1):
    if s[j][i] == '#':
      if start != -1:
        for k in range(start, j):
          tate[k][i] = j - start
        start = -1
    else:
      if start == -1:
        start = j
result = 0
for i in range(h):
  for j in range(w):
    t = yoko[i][j] + tate[i][j] - 1
    if t > result:
      result = t

print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

# dpの最小値を変更する関数
def chmin(a, b):
    if a > b:
        return b
    else:
        return a

# 無限大の値
f_inf = float('inf')

# DP テーブルを初期化　(最小化問題なので INF に初期化)
dp = [f_inf] * (10**5+10)

# 初期条件
dp[0] = 0

for i in range(1, n):
    for j in range(1, k+1):
        if i - j >= 0:
            dp[i] = chmin(dp[i], dp[i-j]+ abs(h[i] - h[i - j]))

print(dp[n-1])





### FIXED CODE ###

import sys
import numpy as np

input = sys.stdin.readline

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

dp = np.zeros(n, dtype=int)
h = np.array(h)


for i in range(1, n):
    start = max(0, i-k)
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

print(dp[n-1])
### BUGGY CODE ###

from collections import Counter
n = int(input())
dic = Counter(list(map(int,input().split())))
rslt = 1
if n % 2 == 0:
    if dic != Counter(sum([[i,i] for i in range(1, n, 2)], [])):
        rslt = 0
    else:
        for _ in range(n//2):
            rslt = rslt * 2 % (10**9+7)
else:
    if dic != Counter(abs(i) for i in range(-n+1, n, 2)):
        rslt = 0
    else:
        for _ in range(n//2):
            rslt = rslt * 2 % (10**9+7)
print(rslt)

### FIXED CODE ###

from collections import Counter
n = int(input())
ns = list(map(int, input().split()))
rslt = 0
a = 10 ** 9 + 7
cnt = Counter(ns)
if n % 2 == 0:
    for i in range(1, n, 2):
        if cnt[i] != 2:
            print(0)
            exit()
    rslt = pow(2, n // 2, a)
else:
    for i in range(2, n, 2):
        if cnt[i] != 2:
            print(0)
            exit()
    if cnt[0] == 1:
        rslt = pow(2, n // 2, a)
print(rslt)
### BUGGY CODE ###

N, M = map(int, input().split())
keys = []
for i in range(M):
    a, b = map(int, input().split())
    c = sum([2 ** (c - 1) for c in list(map(int, input().split()))])
    keys.append([a, c])


# dp[bs] := 鍵の集合bsを手に入れるのに必要な最小費用
dp = [float('inf')] * (1 << N)
dp[0] = 0

for i, (cost, key) in enumerate(keys):
    for bs in range(1 << N):
        dp[bs | key] = min(dp[bs | key], dp[bs] + cost)

print(dp[-1] if dp[-1] != float('inf') else -1)


### FIXED CODE ###

N, M = map(int, input().split())
Keys = []
keys_set = set()

for m in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    c = [2 ** (ci - 1) for ci in c]
    Keys.append([a, sum(c)])
    keys_set |= set(c)


# 不可能判定
if len(keys_set) != N:
    print(-1)
    exit()


dp = [[float('inf')] * (2 ** N) for i in range(M + 1)]
for i in range(M + 1):
    dp[i][0] = 0

for i, (a, c) in enumerate(Keys):
    for bs in range(2 ** N):
        dp[i + 1][bs] = min(dp[i + 1][bs], dp[i][bs])
        dp[i + 1][bs | c] = min(dp[i][bs | c], dp[i + 1][bs | c], dp[i][bs] + a)

ans = float('inf')
for d in dp:
    ans = min(ans, d[-1])
print(ans)