#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
mt19937_64 rng(1);
clock_t END; ///end of execution
char *pos, BUFFER[1300006]; ///fread char buffer
inline int getnum()
{
   char C;
   while ((C = *pos++) < '0');
   int RET = C -= '0';
   while ((C = *pos++) >= '0') RET = 10 * RET + C - '0';
   return RET;
}
int N, M, S; ///number of actors, scenes and the sum of actors in all scenes
int L[10006], R[10006]; ///first and last scenes of each actor
int C[10006]; ///cost of each actor
int* D[5006]; ///pointers for each scene to the jagged array of actors
int A[205006]; ///used for storing the jagged array of actors
float k1, k2; ///bounding function coefficients
int W; ///width of each bitset matrix row
ull B[800096]; ///bitset matrix which determines when each actor plays, stored using row-major order
struct DELTA ///used for storing changes to arrays L, R and B
{
  int i; ///index of each changed element
  ull X; ///old value of each changed element
}dL[20006], dR[20006], dB[40006];
int cL, cR, cB; ///counters for number of changed elements
ll ScoreC, Score; ///current and final scores
int SOLC[5006], SOL[5006]; ///current and final solutions
inline ll GetScore(int* SOL)
{
  ll RET = 0;
  __builtin_memset(L, 0, sizeof(L[0]) * (N + 1));
  for(int i = 1; i <= M; i++) for(int *x = D[SOL[i]]; *x; x++) {L[*x] += i * (!L[*x]); R[*x] = i;}
  for(int x = 1; x <= N; x++) RET += (R[x] - L[x] + 1LL) * C[x];
  return RET;
}
inline void CheckScore(bool flag)
{
  if(flag) ScoreC = GetScore(SOLC);
  if(ScoreC >= Score) return;
  swap(SOL, SOLC);
  Score = ScoreC;
  return;
}
inline void Setup()
{
  k1 = 1.0, k2 = 3.0;
  k1 += 0.5 * (S <= 20000);
  k2 += 2.0 * (S < 200000);
  W = (M >> 6) + 1;
  for(int i = 1; i <= M; i++) SOLC[i] = SOL[i] = i;
  return;
}
inline void Reset(bool flag)
{
  shuffle(SOLC + 1, SOLC + M + 1, rng); ///shuffling is used to possibly open an unexplored branch of the search space
  ScoreC = GetScore(SOLC); ///this sets L and R for every actor
  if(flag) __builtin_memset(B, 0, sizeof(B[0]) * ((N + 1) * W));
  for(int i = 1; i <= M; i++) for(int *x = D[SOLC[i]]; *x; x++) B[(*x * W) + ((i - 1) >> 6)] |= 1ULL << ((i - 1) & 63);
  return;
}
inline int GetL(int i) {for(; !B[i]; i++); return (i << 6) + __builtin_ffsll(B[i]);}
inline int GetR(int i) {for(; !B[i]; i--); return 1 + (i << 6) + __lg(B[i]);}
inline void Random()
{
  int iterations = 0;
  int i, j, reset = M * M;
  ll temp, bound;
  Setup();
  RESET: Reset(reset != (M * M)), reset = M * M, bound = k1 * ScoreC;
  while((clock() < END) && reset)
  {
    iterations++;
    i = (rng() % M) + 1;
    j = (rng() % M) + 1;
    if(i == j) continue;
    if(i > j) swap(i, j);
//    if(ScoreC != GetScore(SOLC)) {exit(333);}
    temp = ScoreC;
    cL = cR = cB = 0;
    for(int *x = D[SOLC[i]], c = *x * W; *x; x++, c = *x * W)
    {
      temp -= (R[*x] - L[*x] + 1LL) * C[*x];
      dB[++cB] = {c + ((i - 1) >> 6), B[c + ((i - 1) >> 6)]};
      dB[++cB] = {c + ((j - 1) >> 6), B[c + ((j - 1) >> 6)]};
      B[c + ((i - 1) >> 6)] ^= 1ULL << ((i - 1) & 63);
      B[c + ((j - 1) >> 6)] ^= 1ULL << ((j - 1) & 63);
      if(L[*x] == i) dL[++cL] = {*x, L[*x]}, L[*x] = GetL(c + ((L[*x] - 1) >> 6)) - (c << 6);
      if(R[*x] <= j) dR[++cR] = {*x, R[*x]}, R[*x] = j;
      temp += (R[*x] - L[*x] + 1LL) * C[*x];
    }
    for(int *x = D[SOLC[j]], c = *x * W; *x; x++, c = *x * W)
    {
      temp -= (R[*x] - L[*x] + 1LL) * C[*x];
      dB[++cB] = {c + ((i - 1) >> 6), B[c + ((i - 1) >> 6)]};
      dB[++cB] = {c + ((j - 1) >> 6), B[c + ((j - 1) >> 6)]};
      B[c + ((i - 1) >> 6)] ^= 1ULL << ((i - 1) & 63);
      B[c + ((j - 1) >> 6)] ^= 1ULL << ((j - 1) & 63);
      if(L[*x] >= i) dL[++cL] = {*x, L[*x]}, L[*x] = i;
      if(R[*x] == j) dR[++cR] = {*x, R[*x]}, R[*x] = GetR(c + ((R[*x] - 1) >> 6)) - (c << 6);
      temp += (R[*x] - L[*x] + 1LL) * C[*x];
    }
    if(temp < bound)
    {
      if((M <= 500) && (ScoreC < Score) && (temp > ScoreC)) {Score = ScoreC; __builtin_memcpy(SOL, SOLC, sizeof(SOL[0]) * (M + 1));}
      bound -= ((ScoreC - temp) / k2) * (ScoreC > temp); ///arbitrary function for bounding the search space
      swap(SOLC[i], SOLC[j]);
      reset += (M * M - reset) * (temp < ScoreC);
      ScoreC = temp;
      continue;
    }
    reset--;
    for(; cL + 1; cL--) L[dL[cL].i] = dL[cL].X;
    for(; cR + 1; cR--) R[dR[cR].i] = dR[cR].X;
    for(; cB + 1; cB--) B[dB[cB].i] = dB[cB].X;
  }
  CheckScore(false);
  if(!reset) goto RESET;
  cout << "Tries: " << iterations << '\n';
  return;
}
inline void Input()
{
  freopen("star.in", "r", stdin);
  fread(pos = BUFFER, 1, 1300000, stdin);
  N = getnum();
  M = getnum();
  for(int x = 1; x <= N; x++) C[x] = getnum();
  int k, *temp = A;
  for(int i = 1; i <= M; i++)
  {
    k = getnum();
    S += k;
    D[i] = temp + 1;
    while(k--) *(++temp) = getnum();
    *(++temp) = 0;
  }
  return;
}
inline void Output()
{
  freopen("star.out", "w", stdout);
  for(int i = 1; i <= M; i++) printf("%d%c", SOL[i], " \n"[i == M]);
  return;
}
int main()
{
  END = clock() + 4.8 * CLOCKS_PER_SEC;
  Input();
  Score = 1LL << 60; ///arbitrary large number
  Random();
  cout << "Final: " << Score << '\n';
  Output();

  return 0;
}