#include <bits/stdc++.h>
#include <chrono>
#include <cmath>
using namespace std;
using ll = long long;

// ---------------------------
// Data Structures
// ---------------------------

// Scene: holds an id and the list of actors (0-indexed)
struct Scene {
    ll id;
    vector<ll> actors;
};

// Particle: for PSOBM. Each particle represents a candidate ordering (a permutation) of scenes.
struct Particle {
    vector<ll> order;       // current ordering (0-indexed)
    double fitness;         // cost of the ordering
    vector<ll> best_order;  // personal best ordering
    double best_fitness;
};

// Move: used in the TSBM phase; we record a move (either 2-swap or 2-opt) together with an expiration (tabu tenure)
struct Move {
    int type; // 0 for 2-swap, 1 for 2-opt
    int i, j;
    int expire;  // iteration count at which the move expires
};

// ---------------------------
// Global Variables and Parameters
// ---------------------------
ll n, m;                           // n: number of actors, m: number of scenes
vector<ll> wages;                  // wages[i] is the hourly wage for actor i
vector<Scene> scenes;              // scenes[i] stores the data for scene i

// PSOBM parameters
const ll swarm_size = 50;          // number of particles
const ll pso_max_iterations = 10000;   // (not directly used – we limit by time)
vector<Particle> swarm;
vector<ll> global_best_order;      // best ordering found overall (0-indexed)
double global_best_fitness = 1e18;

// TSBM parameters
const int TABU_TENURE = 10;          // number of iterations a move remains tabu
const int CANDIDATE_COUNT = 20;      // number of candidate moves generated per TS iteration

// Time limits (in seconds)
const double PHASE_DURATION = 0.07;   // each PSOBM or TSBM phase lasts about 70ms
const double TOTAL_TIME = 3.5;       // overall time for the alternating PSOBM/TSBM phase
const double IMPROVEMENT_TIME = 1.35;  // additional time (in seconds) for iterative improvement

// Random number generator
mt19937 rng((unsigned) chrono::steady_clock::now().time_since_epoch().count());

// ---------------------------
// Input Function
// ---------------------------
void input(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    wages.resize(n);
    for (ll i = 0; i < n; i++){
        cin >> wages[i];
    }
    scenes.resize(m);
    for (ll i = 0; i < m; i++){
        ll numActors;
        cin >> numActors;
        scenes[i].id = i;
        scenes[i].actors.resize(numActors);
        for (ll j = 0; j < numActors; j++){
            cin >> scenes[i].actors[j];
            // convert from 1-indexed to 0-indexed
            scenes[i].actors[j]--;
        }
    }
}

// ---------------------------
// Cost Evaluation Function
// ---------------------------
//
// Given an ordering (a permutation of scene indices), an actor appears from the first scene
// (in the ordering) in which he appears to the last one. His cost is wage * (last - first + 1).
// The total cost is the sum over all actors.
double calculate_cost(const vector<ll>& order){
    vector<ll> actor_first(n, -1), actor_last(n, -1);
    for (ll pos = 0; pos < m; pos++){
        ll sceneIndex = order[pos];
        if (sceneIndex < 0 || sceneIndex >= m)
            return 1e18;
        for (ll actor : scenes[sceneIndex].actors){
            if (actor < 0 || actor >= n)
                return 1e18;
            if (actor_first[actor] == -1)
                actor_first[actor] = pos;
            actor_last[actor] = pos;
        }
    }
    double total_cost = 0;
    for (ll i = 0; i < n; i++){
        if (actor_first[i] != -1)
            total_cost += wages[i] * (actor_last[i] - actor_first[i] + 1);
    }
    return total_cost;
}

// ---------------------------
// PSOBM Functions
// ---------------------------

// initialize_swarm(): Create 'swarm_size' particles with random orderings.
void initialize_swarm(){
    swarm.clear();
    global_best_fitness = 1e18;
    global_best_order.clear();
    for (ll i = 0; i < swarm_size; i++){
        Particle p;
        p.order.resize(m);
        iota(p.order.begin(), p.order.end(), 0); // identity permutation
        shuffle(p.order.begin(), p.order.end(), rng);

        p.fitness = calculate_cost(p.order);
        p.best_order = p.order;
        p.best_fitness = p.fitness;

        if (p.fitness < global_best_fitness){
            global_best_fitness = p.fitness;
            global_best_order = p.order;
        }
        swarm.push_back(p);
    }
}

// update_swarm(): Perform one PSOBM iteration on each particle.
// A particle’s new order is obtained by a 2‑opt reversal and, with 50% chance, nudging it toward the global best.
void update_swarm(){
    for (auto &particle : swarm){
        vector<ll> new_order = particle.order;

        // 2-opt reversal: choose two random positions and reverse that segment.
        uniform_int_distribution<ll> dist(0, m - 1);
        ll i = dist(rng), j = dist(rng);
        if (i > j) swap(i, j);
        if (i < j){
            reverse(new_order.begin() + i, new_order.begin() + j + 1);
        }

        // With 50% probability, nudge toward the global best.
        uniform_int_distribution<int> coin(0, 1);
        if (coin(rng) == 1 && !global_best_order.empty()){
            uniform_int_distribution<ll> dist_idx(0, m - 1);
            ll idx = dist_idx(rng);
            if (new_order[idx] != global_best_order[idx]){
                // Find the position in new_order containing the scene that global_best_order has at position idx.
                ll pos = -1;
                for (ll k = 0; k < m; k++){
                    if (new_order[k] == global_best_order[idx]){
                        pos = k;
                        break;
                    }
                }
                if (pos != -1){
                    swap(new_order[idx], new_order[pos]);
                }
            }
        }

        double new_fitness = calculate_cost(new_order);

        // Update the particle’s personal best.
        if(new_fitness < particle.best_fitness){
            particle.best_fitness = new_fitness;
            particle.best_order = new_order;
        }

        // Update the global best.
        if(new_fitness < global_best_fitness){
            global_best_fitness = new_fitness;
            global_best_order = new_order;
        }

        particle.order = new_order;
        particle.fitness = new_fitness;
    }
}

// runPSOPhase(): Runs PSOBM updates repeatedly for a duration of phase_duration seconds.
void runPSOPhase(double phase_duration) {
    auto phase_start = chrono::steady_clock::now();
    while (true) {
        auto now = chrono::steady_clock::now();
        double elapsed = chrono::duration_cast<chrono::milliseconds>(now - phase_start).count() / 1000.0;
        if (elapsed > phase_duration)
            break;
        update_swarm();
    }
}

// ---------------------------
// TSBM Functions
// ---------------------------

// isTabu(): Returns true if the candidate move is in the tabu list (i.e. its expire time is later than the current iteration).
bool isTabu(const Move &candidate, const vector<Move>& tabuList, int current_iter) {
    for (const auto &mv : tabuList) {
        if (mv.type == candidate.type && mv.i == candidate.i && mv.j == candidate.j) {
            if (current_iter < mv.expire)
                return true;
        }
    }
    return false;
}

// runTabuPhase(): Performs a tabu search (local neighborhood search) on the current_order for phase_duration seconds.
// The function updates current_order (and the global best if an improvement is found).
void runTabuPhase(vector<ll>& current_order, double phase_duration) {
    auto phase_start = chrono::steady_clock::now();
    int iter = 0;
    vector<Move> tabuList; // local tabu list for this phase
    while (true) {
        auto now = chrono::steady_clock::now();
        double elapsed = chrono::duration_cast<chrono::milliseconds>(now - phase_start).count() / 1000.0;
        if (elapsed > phase_duration)
            break;
        iter++;

        // Remove expired moves from the tabu list.
        vector<Move> newTabu;
        for (const auto &mv : tabuList) {
            if (iter < mv.expire)
                newTabu.push_back(mv);
        }
        tabuList = newTabu;

        // Generate candidate moves.
        bool foundCandidate = false;
        vector<ll> best_candidate_order;
        double best_candidate_fitness = 1e18;
        Move best_move = { -1, -1, -1, -1 };

        for (int k = 0; k < CANDIDATE_COUNT; k++){
            vector<ll> candidate_order = current_order;
            Move candidate_move;
            // Randomly choose move type: 0 for 2-swap, 1 for 2-opt.
            uniform_int_distribution<int> moveType(0, 1);
            candidate_move.type = moveType(rng);

            if (candidate_move.type == 0) {
                // 2-swap: choose two distinct indices.
                uniform_int_distribution<int> dist(0, m - 1);
                int i = dist(rng), j = dist(rng);
                while(i == j) { j = dist(rng); }
                if(i > j) swap(i, j);
                candidate_move.i = i;
                candidate_move.j = j;
                swap(candidate_order[i], candidate_order[j]);
            } else {
                // 2-opt: choose two indices and reverse the segment between them.
                uniform_int_distribution<int> dist(0, m - 1);
                int i = dist(rng), j = dist(rng);
                if(i > j) swap(i, j);
                if(i == j) continue; // skip if identical
                candidate_move.i = i;
                candidate_move.j = j;
                reverse(candidate_order.begin() + i, candidate_order.begin() + j + 1);
            }

            double candidate_fitness = calculate_cost(candidate_order);

            // If the move is tabu and does not improve upon the global best (aspiration), skip it.
            if (isTabu(candidate_move, tabuList, iter) && candidate_fitness >= global_best_fitness)
                continue;

            if(candidate_fitness < best_candidate_fitness){
                best_candidate_fitness = candidate_fitness;
                best_candidate_order = candidate_order;
                best_move = candidate_move;
                foundCandidate = true;
            }
        } // end candidate loop

        if (!foundCandidate) {
            // Diversify: if no acceptable candidate was found, randomize current_order and clear the tabu list.
            shuffle(current_order.begin(), current_order.end(), rng);
            tabuList.clear();
            continue;
        }

        // Accept the best candidate move.
        current_order = best_candidate_order;
        double curCost = calculate_cost(current_order);
        if(curCost < global_best_fitness) {
            global_best_fitness = curCost;
            global_best_order = current_order;
        }

        // Add the chosen move to the tabu list.
        best_move.expire = iter + TABU_TENURE;
        tabuList.push_back(best_move);
    }
}

// ---------------------------
// Iterative Improvement Functions (Hill Climbing)
// ---------------------------

// small_change: perform a simple 2-swap on the solution.
void small_change(vector<ll>& sol) {
    int len = sol.size();
    if (len < 2) return;
    int i = rng() % len;
    int j = rng() % len;
    while(i == j)
        j = rng() % len;
    swap(sol[i], sol[j]);
}

// big_change: perform a 2-opt reversal on a segment of the solution.
void big_change(vector<ll>& sol) {
    int len = sol.size();
    if (len < 2) return;
    int i = rng() % len;
    int j = rng() % len;
    if (i > j) swap(i, j);
    // Ensure the segment is non-trivial:
    if (j - i < max(1, len / 10))
        j = min(len - 1, i + max(1, len / 10));
    reverse(sol.begin() + i, sol.begin() + j + 1);
}

// iterative_improvement: starting from an initial solution, make small or big changes
// and if the change improves the cost, accept the change.
vector<ll> iterative_improvement(double time_limit_seconds, vector<ll> init_solution) {
    vector<ll> current_solution = init_solution;
    double current_cost = calculate_cost(current_solution);
    vector<ll> best_solution = current_solution;
    double best_cost = current_cost;

    auto start_time = chrono::steady_clock::now();

    while (chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start_time).count() / 1000.0 < time_limit_seconds) {
        vector<ll> candidate = current_solution;
        double p = (double)rng() / rng.max();
        if (p < 0.8)
            small_change(candidate);
        else
            big_change(candidate);

        double candidate_cost = calculate_cost(candidate);
        if (candidate_cost < current_cost) {
            current_solution = candidate;
            current_cost = candidate_cost;
            if (current_cost < best_cost) {
                best_cost = current_cost;
                best_solution = current_solution;
            }
        }
    }

    return best_solution;
}

// ---------------------------
// Main Solving Routine: Alternating PSOBM/TSBM
// ---------------------------

void solve(){
    // Initialize the swarm for PSOBM.
    initialize_swarm();
    // Set a "current_order" for the TSBM phase from the best found so far.
    vector<ll> current_order = global_best_order;

    auto overall_start = chrono::steady_clock::now();
    bool usePSO = true;  // alternate: start with PSOBM phase
    while (true) {
        auto now = chrono::steady_clock::now();
        double overall_elapsed = chrono::duration_cast<chrono::milliseconds>(now - overall_start).count() / 1000.0;
        if (overall_elapsed > TOTAL_TIME)
            break;

        if (usePSO) {
            // Run PSOBM phase for PHASE_DURATION seconds.
            runPSOPhase(PHASE_DURATION);
        } else {
            // Run TSBM phase for PHASE_DURATION seconds.
            runTabuPhase(current_order, PHASE_DURATION);
            double curCost = calculate_cost(current_order);
            if (curCost < global_best_fitness) {
                global_best_fitness = curCost;
                global_best_order = current_order;
            }
        }
        usePSO = !usePSO; // alternate phase
    }

    // After the alternating phase, perform iterative improvement (hill climbing).
    // Use IMPROVEMENT_TIME seconds on the best solution so far.
    vector<ll> improved_solution = iterative_improvement(IMPROVEMENT_TIME, global_best_order);
    double improved_cost = calculate_cost(improved_solution);
    if (improved_cost < global_best_fitness) {
        global_best_fitness = improved_cost;
        global_best_order = improved_solution;
    }
}

// ---------------------------
// Main Function
// ---------------------------

int main(){
    // Redirect input and output.
    freopen("star.in", "r", stdin);
    freopen("star.out", "w", stdout);

    input();
    solve();
    // Output the best scene order (convert from 0-indexed to 1-indexed).
    for (ll scene : global_best_order)
        cout << scene + 1 << " ";
    cout << "\n";
    return 0;
}