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

n, x, m = map(int, input().split())
a = [x]
if n == 1:
    print(x)
    exit()
for i in range(n-1):
    ad = (a[-1]**2) % m
    if ad in a:
        roop_s = a.index(ad)
        roop_e = len(a)
        break
    else:
        a.append(ad)
    if i == n-2:
        print(sum(a))
        exit()
roop_t = (n-roop_s) // (roop_e - roop_s)
left = n - roop_t*(roop_e - roop_s) - roop_s
ans = sum(a[:roop_s]) + roop_t*sum(a[roop_s : roop_e]) + sum(a[roop_s:roop_s+left])
print(ans)

### FIXED CODE ###

n, x, m = map(int, input().split())
a = [x]
if n == 1:
    print(x)
    exit()
for i in range(n-1):
    ad = (a[-1]**2) % m
    if ad in a:
        roop_s = a.index(ad)
        roop_e = len(a)
        break
    else:
        a.append(ad)
    if i == n-2:
        print(sum(a))
        exit()
roop_t = (n-roop_s) // (roop_e - roop_s)
left = n - roop_t*(roop_e - roop_s) - roop_s
ans = sum(a[:roop_s]) + roop_t*sum(a[roop_s : roop_e]) + sum(a[roop_s:roop_s+left])
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import math
N = int(input())
x = [list(map(int, input().split())) for _ in range(N)]
nlst = '01234567'
xlst = []
a = [-1] * N
def dfs(cnt):
    if cnt == N:
        tmpF = True
        for i in range(N):
            if a.count(int(nlst[i])) != 1:
                tmpF = False
                break
        if tmpF:
            tmp = 0
            for i in range(1, N):
                tmp += math.sqrt(((x[a[i - 1]][0] - x[a[i]][0]) ** 2) + (x[a[i - 1]][1] - x[a[i]][1]) ** 2)
            xlst.append(tmp)
        return

    for i in range(N):
        a[cnt] = i
        dfs(cnt + 1)

dfs(0)

kain = 1
for i in range(1, N + 1):
    kain *= i

print(sum(xlst) / kain)

### FIXED CODE ###

import itertools
import math
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
p = []
cnt = 0

for v in itertools.permutations(xy, N):
    p.append(v)

ans = 0
for i in range(len(p)):
    for j in range(N - 1):
        ans += math.sqrt((p[i][j][0] - p[i][j + 1][0]) ** 2 + (p[i][j][1] - p[i][j + 1][1]) ** 2)

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

N = int(input())
P = list(map(int,input().split()))
a = []
ans = 0
for i in range(N):       
    if i == 0:
        ans += 1
    elif P[i] != N:
        a = P[0:i]
        a = sorted(a)
        if a[0] >= P[i]:
            ans += 1
        a = []
print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 0
x = P[0]


for i in P:
    if i == 1:
        ans += 1
        x = 1
    else:
        if x >= i:
            ans += 1
            x = i



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

n,k = map(int,input().split())
p = list(map(int,input().split()))
maxsum = 0
for i in range(n-k+1):
	cnt = sum(p[i:i+k])+k
	if cnt >= maxsum:
		maxsum = cnt
print(maxsum/2)

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
u = sum(p[0:k])
maxsum = u
for i in range(1, n-k+1):
	u = u + p[i+k-1] - p[i-1]
	if u >= maxsum:
		maxsum = u
print((maxsum+k)/2)
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()
ans = 0
if P in [2, 5]:
    for l, s in enumerate(S, 1):
        if int(s) % P == 0: ans += l
else:
    counter = [0] * P
    counter[0] = 1
    for i in range(N-1, -1, -1):
        num = int(S[i:]) % P
        ans += counter[num]
        counter[num] += 1
print(ans)

### FIXED CODE ###

N, P = map(int, input().split())
S = input()
ans = 0
if P in [2, 5]:
    for l, s in enumerate(S, 1):
        if int(s) % P == 0: ans += l
else:
    counter = [0] * P
    counter[0] = 1
    prev = 0
    temp = 1
    for i, s in reversed(list(enumerate(S))):
        num = (int(s) * temp + prev) % P
        ans += counter[num]
        counter[num] += 1
        prev = num
        temp = (temp * 10) % P
print(ans)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
nr=n//r
nb=n//b
ans=0
lb=[b*k for k in range(nb+1)]
lst=lb.copy()

for i in lb:
  ng=(n-i)//g
  for j in range(1,ng+1):
    lst.append(i+g*j)

lst.sort()
l=len(lst)

import bisect
for i in range(nr+1):
  res=n-r*i
  idx=bisect.bisect_left(lst,res)
  if idx<l and lst[idx]==res:
    ans+=lst.count(res)
print(ans)


### FIXED CODE ###

r,g,b,n=map(int,input().split())
nr=n//r
ans=0
for i in range(nr+1):
  ng=(n-i*r)//g
  for j in range(ng+1):
    res=n-r*i-g*j
    if res%b==0:
      ans+=1
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(M)]

z = [set({})] * (N // 2)
k = 0


def func1(x, y):
    global z, k
    px = -1
    py = -1
    for i, s in enumerate(z[:k]):
        if x in s:
            if py > -1:
                lx = len(z[py])
                ly = len(z[i])
                z[py] |= z[i]
                z[i] = set({})
                return (lx + ly)*(lx + ly - 1) // 2 - lx * (lx - 1) // 2 - ly * (ly - 1) // 2
            elif y in s:
                return 0
            else:
                px = i
        elif y in s:
            if px > -1:
                lx = len(z[px])
                ly = len(z[i])
                z[px] |= z[i]
                z[i] = set({})
                return (lx + ly)*(lx + ly - 1) // 2 - lx * (lx - 1) // 2 - ly * (ly - 1) // 2
            else:
                py = i

    if px > -1:
        lx = len(z[px])
        z[px].add(y)
        return lx

    if py > -1:
        lx = len(z[py])
        z[py].add(x)
        return lx

    z[k] = {x, y}
    k += 1
    return 1


ans = [0] * (M - 1)
p = 0
for i in range(M - 1, 0, -1):
    p += func1(A[i][0], A[i][1])
    ans[i - 1] = p

nall = N * (N - 1) // 2
for a in ans:
    print(nall - a)
print(nall)

### FIXED CODE ###

N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]


class UnionFind:
    def __init__(self,size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

    def find(self,x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.number[px] * uf.number[py]
            uf.union(px, py)
        ans.append(p)

    for a in reversed(ans[:-1]):
        print(a)


main()
### BUGGY CODE ###

import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

t = set([v for v in range(1, N + 1)])
L = [None] * M
for i in range(M):
    A, B, = map(int, input().split())
    C = [int(v) for v in input().split()]
    
    L[i] = (A, C)
    t = t - set(C)

if len(t) > 0:
    print(-1)
    exit()

ans = 10 ** 18
for i in range(1, 1 << M):
    t = set()

    for j in range(M):
        if (i >> j) & 1:
            t.add(j)

    m = set([v for v in range(1, N + 1)])
    score = 0
    for p in t:
        a = L[p]
        score += a[0]
        m = m - set(a[1])

    if len(m) == 0:
        ans = min(ans, score)

print(ans)


### FIXED CODE ###

import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

L = []
v = 0
for _ in range(M):
    a, b = map(int, input().split())
    l = sum([1 << (int(v) - 1) for v in input().split()])
    L.append([a, b, l])
    v = v | l
if v != (1 << N) - 1:
     print(-1)
     exit()

dp = [[10 ** 18 for _ in range(1 << N)] for _ in range(M + 1)]
dp[0][0] = 0

for i in range(M):
     for j in range(1 << N):
          dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

          dp[i + 1][j | L[i][2]] =  min(dp[i + 1][j | L[i][2]], dp[i][j] + L[i][0])

print(dp[M][(1 << N) - 1])
### BUGGY CODE ###

time = int(input())
p = 1
for i in range(time):
    p *= i + 1
mod = p % (10**9+7)
print(mod)


### FIXED CODE ###

import math
time = int(input())
p = math.factorial(time)
mod = p % (10**9+7)
print(mod)
### BUGGY CODE ###

def main():
    length = int(input())
    numbers = list(map(int, input().split()))
    answer = []
    for num in numbers:
        answer.append(num)
        answer = list(reversed(answer))
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    length = int(input())
    numbers = list(map(int, input().split()))
    answer = [0] * length
    if length % 2:
        answer[:length // 2 + 1] = numbers[::-2]
        answer[length // 2 + 1:] = numbers[1::2]
    else:
        answer[:length // 2] = numbers[::-2]
        answer[length // 2:] = numbers[::2]
    print(" ".join(list(map(str, answer))))


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

s=[int(x) for x in input()]
L=[]
sum=0
for i in range(len(s)):
    t=s[i]*(10**(len(s)-i))
    sum += t
    L.append(sum%2019)
import collections
L=collections.Counter(L)
L=L.most_common()
ans=0
for i in L:
    if i[0]==0:
        ans += i[1]*(i[1]+1)//2
    elif i[1]>1:
        ans += i[1]*(i[1]-1)//2
print(ans)


### FIXED CODE ###

from collections import deque
s=input()[::-1]
l=[0]*2019
ten=1
sm=0
cnt=0
l[0]=1
for i in range(len(s)):
    sm += int(s[i])*ten
    sm %= 2019
    cnt += l[sm]
    l[sm] += 1
    ten = ten *10 %2019
print(cnt)
### BUGGY CODE ###

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

x = input()

frag = True
while frag:
    frag = False
    if x[0: 2] == "ST":
        x = x[2:]
        frag = True
        continue
    for i in range(1, len(x)):
        if x[i: i+2] == "ST":
            x = x[0: i] + x[i+2:]
            frag = True
            break

print(len(x))


### FIXED CODE ###

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

x = input()

# ペアになっていないSの数（ペアができたら-1）
sc = 0
# ペアにならなかったTの数
tc = 0

for c in x:
    if c == 'S':
        sc += 1
    elif sc >= 1:
        sc -= 1
    else:
        tc += 1

print(sc + tc)
### BUGGY CODE ###

N,M = map(int,input().split())
requests = []
for _ in range(M):
        a,b = map(int,input().split())
        requests.append([a,b])

ans = 0
requests = sorted(requests, key=lambda x:x[0])
while requests:
        ans += 1
        bridge = min(requests, key=lambda x:x[1])[1]
        while requests:
                if requests[0][0] < bridge:
                        del requests[0]
                else:
                        break

print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
requests = []
for _ in range(M):
        a,b = map(int,input().split())
        requests.append([a,b])

ans = 1
requests = sorted(requests, key=lambda x:x[1])
b = requests[0][1]
for i in range(M):
        if requests[i][0] < b:
                continue
        else:
                ans += 1
                b = requests[i][1]

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

# E - Knapsack 2
from collections import defaultdict


def main():
    N, W, *WV = map(int, open(0).read().split())
    dp = defaultdict(int)
    dp[0] = 0
    for w, v in zip(*[iter(WV)] * 2):
        for cur_w, cur_v in tuple(dp.items()):
            if w + cur_w <= W:
                dp[w + cur_w] = max(dp[w + cur_w], v + cur_v)
    print(max(dp.values()))


if __name__ == "__main__":
    main()


### FIXED CODE ###

# temp
n,w = map(int,input().split())
wv = [tuple(map(int,input().split())) for i in range(n)]

dp = [0] + [float("inf")]*(10**5)
for i in range(n):
    for j in range(10**5,wv[i][1]-1,-1):
        dp[j] = min(dp[j],dp[j-wv[i][1]]+wv[i][0])

res = 0
for v,e in enumerate(dp):
    if e <= w:
        res = v
print(res)
### BUGGY CODE ###

n = int(input())

slist = []
for h in range(n):
  slist.append(input())

newlist = []
word=[]
wordy = ""
for i in range(n):
  word = list(slist[i])
  word.sort()
  for jk in range(len(word)):
	  wordy = wordy+word.pop()
  newlist.append(wordy)
  wordy=""
new2list = sorted(newlist)

count= 0
for j in range(n):
  for k in range(j+1,n):
    if new2list[j] == new2list[k]:
      count += 1

print(count)

### FIXED CODE ###

n = int(input())

slist = []
for h in range(n):
  slist.append(input())

newlist = []
word=[]
wordy = ""
for i in range(n):
  word = list(slist[i])
  word.sort()
  for jk in range(len(word)):
	  wordy = wordy+word.pop()
  newlist.append(wordy)
  wordy=""

resdic = {}
count = 0
for item in newlist:
  if not item in resdic:
    resdic[item] = 1
  else:
    count += resdic[item]
    resdic[item] += 1
    
print(count)
### BUGGY CODE ###

import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
import networkx as nx
def resolve():
    m, n = map(int, input().split())
    # row = 0, ..., m - 1, col = m, ..., m + n - 1, source = m + n, terminartion = m + n + 1
    G = nx.Graph()
    G.add_nodes_from(range(m + n + 2))
    grid = [input() for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 'S':
                si, sj = i, j
            elif grid[i][j] == 'T':
                ti, tj = i, j

    G.add_edge(m + n, si, capacity = INF)
    G.add_edge(m + n, m + sj, capacity = INF)
    G.add_edge(ti, m + n + 1, capacity = INF)
    G.add_edge(m + tj, m + n + 1, capacity = INF)
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '.':
                continue
            for nj in range(n):
                if grid[i][nj] != '.':
                    G.add_edge(i, m + nj, capacity = 1)
            for ni in range(m):
                if grid[ni][j] != '.':
                    G.add_edge(ni, m + j, capacity = 1)

    ans = nx.algorithms.flow.maximum_flow_value(G, m + n, m + n + 1)
    if ans >= INF:
        ans = -1
    print(ans)
resolve()

### FIXED CODE ###

import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
import networkx as nx
def resolve():
    m, n = map(int, input().split())
    # source = -1, row = 0, ..., m - 1, col = m, ..., m + n - 1, terminartion = m + n
    G = nx.Graph()
    G.add_nodes_from(range(m + n + 2))
    for i in range(m):
        for j, c in enumerate(input()):
            if c == '.':
                continue
            elif c == 'o':
                G.add_edge(i, m + j, capacity = 1)
            elif c == 'S':
                G.add_edge(-1, i, capacity = INF)
                G.add_edge(-1, m + j, capacity = INF)
            elif c == 'T':
                G.add_edge(i, m + n, capacity = INF)
                G.add_edge(m + j, m + n, capacity = INF)

    ans = nx.algorithms.flow.maximum_flow_value(G, -1, m + n)
    if ans >= INF:
        ans = -1
    print(ans)
resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
D = {0:0,1:0,2:0,3:0}

for a in A :
    D[a] += 1

dp = [[[0]*(N+1) for j in range(N+1)] for i in range(N+1)]

flag = [[[0]*(N+1) for j in range(N+1)] for i in range(N+1)]

def f(c1, c2, c3) :
    if flag[c1][c2][c3] :
        return dp[c1][c2][c3]
    elif c1 + c2 + c3 == 0 :
        return 0
    else :
        flag[c1][c2][c3] = 1
        res = N / (c1 + c2 + c3)

        if c1 > 0 :
            res += f(c1-1, c2, c3) * (c1 / (c1 + c2 + c3))
        if c2 > 0 :
            res += f(c1+1, c2-1, c3) * (c2 / (c1 + c2 + c3))
        if c3 > 0 :
            res += f(c1, c2+1, c3-1) * (c3 / (c1 + c2 + c3))
        
        dp[c1][c2][c3] = res
        return res

ans = f(D[1], D[2], D[3])

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
D = {0:0,1:0,2:0,3:0}
for a in A :
    D[a] += 1

one = D[1]
two = D[2]
three = D[3]

dp = [[[0.0]*(N+1) for j in range(N+1)] for i in range(N+1)]

def f(c1, c2, c3) :
    res = N
    if (c1 > 0) :
        res += dp[c1-1][c2][c3] * c1
    if (c2 > 0) :
        res += dp[c1+1][c2-1][c3] * c2
    if (c3 > 0) :
        res += dp[c1][c2+1][c3-1] * c3
    
    dp[c1][c2][c3] = res/(c1 + c2 + c3)

for k in range(three+1) :
    for j in range(two+three+1 - k) :
        for i in range(one+two+three+1 - (j+k)) :
            if i+j+k == 0 :
                continue
            f(i, j, k)

print(dp[one][two][three])
### BUGGY CODE ###

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

score = a[0]
newscore = 0
for i in range(1, n):
    if i < k:
        score = score*a[i]
    else:
        newscore = score*a[i]//a[i-k]
        if newscore > score:
            print("Yes")
        else:
            print("No")
            

### FIXED CODE ###

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

score = a[0]
newscore = 0
for i in range(1, n):
    if i >= k:
        if a[i] > a[i-k]:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

n = int(input())
s = input()

ch = n - 1
for i in range(n):
  ch = min(ch, sum(x == "W" for x in s[:i]) + sum(x == "E" for x in s[i + 1:]))
print(ch)

### FIXED CODE ###

n = int(input())
s = input()

w = [0] * n
e = [0] * n

cnt_w = 0
cnt_e = 0
for i in range(n):
  if s[i] == "W":
    cnt_w += 1
    w[i] = cnt_w
    e[i] = cnt_e
  else:
    w[i] = cnt_w
    cnt_e += 1
    e[i] = cnt_e
    
ch = n - 1
for i in range(n):
  if i >= 1:
    ch = min(ch, w[i - 1] + e[-1] - e[i])
  else:
    ch = min(ch, e[-1] - e[0])
print(ch)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())

    anss = []
    for _ in range(Q):
        v, w = map(int, input().split())
        v, w = v-1, w-1
        while v != w:
            if v > w:
                v = (v-1)//N
            else:
                w = (w-1)//N
        anss.append(v + 1)

    print('\n'.join(map(str, anss)))

solve()


### FIXED CODE ###

N, Q = map(int, input().split())
vws = [tuple(map(int, input().split())) for _ in range(Q)]

anss = []
if N == 1:
    anss = [min(v, w) for v, w in vws]
else:
    for v, w in vws:
        v, w = v-1, w-1
        while v != w:
            if v > w:
                v = (v-1)//N
            else:
                w = (w-1)//N
        anss.append(v + 1)

print('\n'.join(map(str, anss)))
### BUGGY CODE ###

INF=float('inf')
n,m=map(int,input().split())
a=[0]*m
c=[0]*m
for i in range(m):
    a[i],_=map(int,input().split())
    c[i]=sum(map(lambda x:2**(int(x)-1),input().split()))
dp=[INF]*(2**n)
dp[0]=0
for i in range(m):
    for j in range(2**n):
        dp[c[i]|j]=min(dp[c[i]|j],dp[j]+a[i])
print(-1 if dp[-1]==INF else dp[-1])

### FIXED CODE ###

n,m=map(int,input().split())
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=sum(map(lambda x:2**(int(x)-1),input().split()))

dp=[-1]*(2**n)
for i in range(m):
    for j in range(2**n):
        if j|c[i]==c[i]:
            if dp[j]<0:
                dp[j]=a[i]
            else:
                dp[j]=min(dp[j],a[i])
for i in range(m):
    for j in range(2**n):
        if dp[j]<0:
            continue
        if dp[c[i]|j]<0:
            dp[c[i]|j]=dp[j]+a[i]
        else:
            dp[c[i]|j]=min(dp[c[i]|j],dp[j]+a[i])
print(dp[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    A = inputList()
    
    ans = [0 for i in range(N)]
    ans_cnt = 0
    ans_str = ""
    for i in range(N, 0, -1):
        cons = 0
        for j in range(i*2, N+1, i):
            if ans[j-1] == 1:
                cons += 1
        if A[i-1] == 1 and cons % 2 == 0:
            ans[i-1] = 1
            ans_cnt += 1
            ans_str = ans_str + str(i) + " "
            continue
        if A[i-1] == 0 and cons % 2 == 1:
            ans[i-1] = 1
            ans_cnt += 1
            ans_str = ans_str + str(i) + " "
            continue
            
    print(ans_cnt)
    print(ans_str)
            	
if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
 
N=INT()
A=LIST()
 
# その位置にボールを入れるかを保持するA2
A2=[0]*N
B=[]
# 後ろから決めていく
for i in range(N-1, -1, -1):
    cur=i+1
    cnt=0
    # curの倍数を全部見に行く
    for j in range(cur*2, N+1, cur):
        cnt^=A2[j-1]
    # ボールを入れるべきかどうか
    if A[i]!=cnt:
        B.append(cur)
        A2[i]=1
 
print(len(B))
print(*B)
### BUGGY CODE ###

n, m = map(int, input().split())
dp = [[float("inf"), set([])]  for _ in range(2 ** m)]
dp[0][0] = 0
a_list = []
c_list = []
for i in range(m):
    a, b = map(int, input().split())
    a_list.append(a)
    c_list.append([int(i) for i in input().split()])

for i in range(1, 2 ** m):
    for j in range(m):
        c = c_list[j]
        a = a_list[j]
        if (i & (1 << j) == 1 << j):
            if len(set(c) - dp[i - (1 << j)][1]) > 0:
                if len(set(c) - dp[i][1]) > 0:
                    dp[i][0] = dp[i - (1 << j)][0] + a
                    dp[i][1] = dp[i - (1 << j)][1] | set(c)
                else:
                    if dp[i][0] > dp[i - (1 << j)][0] + a:
                        dp[i][0] = dp[i - (1 << j)][0] + a
                    else:
                        continue
            elif len(dp[i - (1 << j)][1]) == n:
                if len(dp[i][1]) == n:                    
                    dp[i][0] = min(dp[i - (1 << j)][0], dp[i][0])
                elif len(set(c) | dp[i][1]) == n:
                    dp[i][1] = dp[i - (1 << j)][1] | set(c)
                    dp[i][0] = min(dp[i - (1 << j)][0], dp[i][0] + a)
if len(dp[-1][1]) == n:
    print(dp[-1][0])
else:
    print(-1)

### FIXED CODE ###

n, m = map(int, input().split())
dp = [[float('inf')] * 2 ** n for _ in range(m + 1)]
dp[0][0] = 0
for i in range(1, m + 1):
    a, b = map(int, input().split())
    c = [int(i_) for i_ in input().split()]
    temp = 0
    for kk in c:
        temp += 1 << (kk - 1)
    for j in range(2 ** n):
        if j == 0:
            dp[i][temp | j] = a
        else:
            dp[i][temp | j] = min(dp[i - 1][j] + a, dp[i][temp | j])
        if (i > 1):
            dp[i][j] = min(dp[i - 1][j], dp[i][j])

if dp[-1][-1] < float("inf"):
    print(dp[-1][-1])
else:
    print(-1)