import random
from time import *
from random import *

start = time()
fi = open("star.in")
N, M = map(int, fi.readline().split());
A, S, C = [0] * N, [set() for _ in range(N)], tuple(map(int, fi.readline().split()))
scene = lambda x: (next(x), tuple(y - 1 for y in x))
K, a = zip(*(scene(map(int, fi.readline().split())) for _ in range(M)))
for i, x in enumerate(a):
    for j in x: A[j] += 1; S[j].add(i)
SU = [sum(C[j] for j in x) for x in a]
pr, cnt, g = list(range(M)), [1] * M, M

def pre(a):
    global pr
    if pr[a] != a: pr[a] = pre(pr[a])
    return pr[a]

def uni(a, b):
    global pr, cnt, g
    aa, bb = pre(a), pre(b)
    if aa != bb:
        if cnt[aa] < cnt[bb]: t = aa; aa = bb; bb = t
        cnt[aa] += cnt[bb];
        pr[bb] = aa
        g-=1

for i, x in enumerate(a):
    for y in x:
        for j in S[y]:
            uni(i, j)
            if g == 1: break
        if g == 1: break
    if g == 1: break

ans = {}
if g>1:
    for i, x in enumerate(pr):
        ii = pre(i)
        if ii not in ans: ans[ii] = set()
        ans[ii].add(i)
else: ans={0:set(range(M))}

def srt(s):
    if len(s)<3: return list(s)
    if len(s)<50:
        ans = [[]]
        for x in s:
            t = []
            for y in ans:
                for j in range(len(y)+1):
                    l = list(y)
                    l.insert(j,x)
                    t.append(l)
            ans=[t[x] for _,x in sorted([(calc(t[i]), i) for i in range(len(t))])[:20]]
        return ans[0]
    if len(s)<100:
        ans = [[]]
        for x in s:
            t = []
            for y in ans:
                for j in range(len(y)+1):
                    l = list(y)
                    l.insert(j,x)
                    t.append(l)
            ans=[t[x] for _,x in sorted([(calc(t[i]), i) for i in range(len(t))])[:3]]
        return ans[0]

    l = sorted([(len(S[i]),C[j]/len(S[i]),j) for j in {y for x in s for y in a[x]}], reverse=True)
    first = S[l[0][2]]
    _, first = zip(*sorted([(SU[i], i) for i in first]))
    ans=list(first)
    for _,_,j in l[1:]:
        diff = S[j].difference(ans)
        if len(diff)>0:
            _, last = zip(*sorted([(SU[i], i) for i in diff], reverse=True))
        else: last = []
        ans.extend(last)
    return ans

def calc(l):
    curr, budg = {}, 0
    for i in l:
        for jj in a[i]:
            if not jj in curr: curr[jj] = A[jj]
        for jj in curr: budg += C[jj]
        for jj in a[i]:
            if curr[jj]==1: curr.pop(jj)
            else: curr[jj]-=1
    return budg

ans = sum([srt(ans[x]) for x in ans], []);
if sum(A)<100000:
    budget, i, j = calc(ans), M//2, M//2+1
    while M>4 and time()-start<4.7:
        l=list(ans)
        t=l[i]; l[i]=l[j]; l[j]=t
        t=calc(l)
        if t<budget:
            budget=t; ans=l;
            if i>j: i,j=j,i
            if time()-start>4.7: break
            l=list(ans)
            t=l[i]; l[i]=l[i+1]; l[i+1]=t
            t=calc(l)
            if t<budget: budget=t; ans=l; i=(i+1)%(M-1); j=i+1
            if time()-start>4.7: break
            l=list(ans)
            t=l[j-1]; l[j-1]=l[j]; l[j]=t
            t=calc(l)
            if t<budget: budget=t; ans=l; i=(i+M-2)%(M-1); j=i+1
        else: i,j = randint(0,M-1), randint(1,M-1)
#print(calc(ans))

with open("star.out", "w") as fo: print(*[x + 1 for x in ans], file=fo)