/* #region Head */

// #include <bits/stdc++.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert> // assert.h
#include <cmath>   // math.h
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using vll = vc<ll>;
using vvll = vvc<ll>;
using vld = vc<ld>;
using vvld = vvc<ld>;
using vs = vc<string>;
using vvs = vvc<string>;
template <class T, class U> using um = unordered_map<T, U>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqa = priority_queue<T, vc<T>, greater<T>>;
template <class T> using us = unordered_set<T>;

#define TREP(T, i, m, n) for (T i = (m), i##_len = (T)(n); i < i##_len; ++(i))
#define TREPM(T, i, m, n) for (T i = (m), i##_max = (T)(n); i <= i##_max; ++(i))
#define TREPR(T, i, m, n) for (T i = (m), i##_min = (T)(n); i >= i##_min; --(i))
#define TREPD(T, i, m, n, d) for (T i = (m), i##_len = (T)(n); i < i##_len; i += (d))
#define TREPMD(T, i, m, n, d) for (T i = (m), i##_max = (T)(n); i <= i##_max; i += (d))

#define REP(i, m, n) for (ll i = (m), i##_len = (ll)(n); i < i##_len; ++(i))
#define REPM(i, m, n) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; ++(i))
#define REPR(i, m, n) for (ll i = (m), i##_min = (ll)(n); i >= i##_min; --(i))
#define REPD(i, m, n, d) for (ll i = (m), i##_len = (ll)(n); i < i##_len; i += (d))
#define REPMD(i, m, n, d) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; i += (d))
#define REPI(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define REPIR(itr, ds) for (auto itr = ds.rbegin(); itr != ds.rend(); itr++)
#define ALL(x) begin(x), end(x)
#define SIZE(x) ((ll)(x).size())
#define ISIZE(x) ((int)(x).size())
#define PERM(c)                                                                                                        \
    sort(ALL(c));                                                                                                      \
    for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))
#define UNIQ(v) v.erase(unique(ALL(v)), v.end());
#define CEIL(a, b) (((a) + (b)-1) / (b))

#define endl '\n'

constexpr ll INF = 1'010'000'000'000'000'017LL;
constexpr int IINF = 1'000'000'007LL;
constexpr ll MOD = 1'000'000'007LL; // 1e9 + 7
// constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.14159265358979323846;

template <typename T> istream &operator>>(istream &is, vc<T> &vec) { // vector 入力
    for (T &x : vec) is >> x;
    return is;
}
template <typename T> ostream &operator<<(ostream &os, const vc<T> &vec) { // vector 出力 (for dump)
    os << "{";
    REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "" : ", ");
    os << "}";
    return os;
}
template <typename T> ostream &operator>>(ostream &os, const vc<T> &vec) { // vector 出力 (inline)
    REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "\n" : " ");
    return os;
}

template <typename T, size_t _Nm> istream &operator>>(istream &is, array<T, _Nm> &arr) { // array 入力
    REP(i, 0, SIZE(arr)) is >> arr[i];
    return is;
}
template <typename T, size_t _Nm> ostream &operator<<(ostream &os, const array<T, _Nm> &arr) { // array 出力 (for dump)
    os << "{";
    REP(i, 0, SIZE(arr)) os << arr[i] << (i == i_len - 1 ? "" : ", ");
    os << "}";
    return os;
}

template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &pair_var) { // pair 入力
    is >> pair_var.first >> pair_var.second;
    return is;
}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &pair_var) { // pair 出力
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}

// map, um, set, us 出力
template <class T> ostream &out_iter(ostream &os, const T &map_var) {
    os << "{";
    REPI(itr, map_var) {
        os << *itr;
        auto itrcp = itr;
        if (++itrcp != map_var.end()) os << ", ";
    }
    return os << "}";
}
template <typename T, typename U> ostream &operator<<(ostream &os, const map<T, U> &map_var) {
    return out_iter(os, map_var);
}
template <typename T, typename U> ostream &operator<<(ostream &os, const um<T, U> &map_var) {
    os << "{";
    REPI(itr, map_var) {
        auto [key, value] = *itr;
        os << "(" << key << ", " << value << ")";
        auto itrcp = itr;
        if (++itrcp != map_var.end()) os << ", ";
    }
    os << "}";
    return os;
}
template <typename T> ostream &operator<<(ostream &os, const set<T> &set_var) { return out_iter(os, set_var); }
template <typename T> ostream &operator<<(ostream &os, const us<T> &set_var) { return out_iter(os, set_var); }
template <typename T> ostream &operator<<(ostream &os, const pq<T> &pq_var) {
    pq<T> pq_cp(pq_var);
    os << "{";
    if (!pq_cp.empty()) {
        os << pq_cp.top(), pq_cp.pop();
        while (!pq_cp.empty()) os << ", " << pq_cp.top(), pq_cp.pop();
    }
    return os << "}";
}

// tuple 出力
template <size_t N = 0, bool end_line = false, typename... Args> ostream &operator<<(ostream &os, tuple<Args...> &a) {
    if constexpr (N < std::tuple_size_v<tuple<Args...>>) {
        os << get<N>(a);
        if constexpr (N + 1 < std::tuple_size_v<tuple<Args...>>) {
            os << ' ';
        } else if constexpr (end_line) {
            os << '\n';
        }
        return operator<< <N + 1, end_line>(os, a);
    }
    return os;
}
template <typename... Args> void print_tuple(tuple<Args...> &a) { operator<< <0, true>(std::cout, a); }

void pprint() { std::cout << endl; }
template <class Head, class... Tail> void pprint(Head &&head, Tail &&...tail) {
    std::cout << head;
    if (sizeof...(Tail) > 0) std::cout << ' ';
    pprint(move(tail)...);
}

// dump
#define DUMPOUT cerr
void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head &&head, Tail &&...tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) DUMPOUT << ", ";
    dump_func(move(tail)...);
}

// chmax (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmax(T &xmax, const U &x, Comp comp = {}) {
    if (comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}

// chmin (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmin(T &xmin, const U &x, Comp comp = {}) {
    if (comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

// ローカル用
#ifndef ONLINE_JUDGE
#define DEBUG_
#endif

#ifndef MYLOCAL
#undef DEBUG_
#endif

#ifdef DEBUG_
#define DEB
#define dump(...)                                                                                                      \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                                                                    \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl                                        \
            << "    ",                                                                                                 \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif

#define VAR(type, ...)                                                                                                 \
    type __VA_ARGS__;                                                                                                  \
    assert((std::cin >> __VA_ARGS__));

template <typename T> istream &operator,(istream &is, T &rhs) { return is >> rhs; }
template <typename T> ostream &operator,(ostream &os, const T &rhs) { return os << ' ' << rhs; }

struct AtCoderInitialize {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;
    AtCoderInitialize() {
        ios_base::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
        std::cout << fixed << setprecision(IOS_PREC);
        if (AUTOFLUSH) std::cout << unitbuf;
    }
} ATCODER_INITIALIZE;

void Yn(bool p) { std::cout << (p ? "Yes" : "No") << endl; }
void YN(bool p) { std::cout << (p ? "YES" : "NO") << endl; }

template <typename T> constexpr void operator--(vc<T> &v, int) noexcept {
    for (int i = 0; i < ISIZE(v); ++i) v[i]--;
}
template <typename T> constexpr void operator++(vc<T> &v, int) noexcept {
    for (int i = 0; i < ISIZE(v); ++i) v[i]++;
}

/* #endregion */

// #include <atcoder/all>
// using namespace atcoder;

/* #region rand */

// [lb, ub] の値を等確率で発生させる
template <typename T = ll> class Rand {
    using dist_type = std::uniform_int_distribution<T>;

    T _lb;
    T _ub;
    // std::random_device rd; // Will be used to obtain a seed for the random number engine
    std::mt19937_64 gen; // Standard mersenne_twister_engine seeded with rd()
    dist_type dis;

  public:
    Rand(T lb, T ub, int seed) : _lb(lb), _ub(ub), gen(seed), dis(lb, ub) {}
    inline T operator()() noexcept { return dis(gen); }
    inline void set_param(T lb, T ub) noexcept {
        if (lb == _lb && ub == _ub) return;
        _lb = lb, _ub = ub;
        typename dist_type::param_type param(lb, ub);
        dis.param(param);
    }
};

// [lb, ub) の値を等確率で発生させる
template <typename T = double> class RandDouble {
    // std::random_device seed_gen;
    std::default_random_engine engine;
    std::uniform_real_distribution<T> dist;

  public:
    RandDouble(T lb, T ub, int seed) : engine(seed), dist(lb, ub) {}
    inline T operator()() noexcept { return dist(engine); }
};

/* #endregion */

/* #region Anneal */

#include <chrono>

// 誰でもできる焼きなまし法 - gasin’s blog http://gasin.hatenadiary.jp/entry/2019/09/03/162613
struct Anneal {
    using clk = chrono::system_clock;

    int64_t timespan_microsecs; // 焼きなます時間
    float start_temp;           // 開始温度 (一回の遷移で動きうるスコア幅の最大値程度)
    float end_temp;             // 終了温度 (一回の遷移で動きうるスコア幅の最小値程度)
    RandDouble<float> rd;
    clk::time_point start_time;
    int64_t microsecs_elapsed;
    ll max_trial_count;
    ll trial_count;

    // コンストラクタ
    Anneal(int64_t timespan_microsecs, float start_temp, float end_temp, int seed, ll max_trial_count = -1)
        : timespan_microsecs(timespan_microsecs), start_temp(start_temp), end_temp(end_temp), rd(0, 1, seed),
          start_time(clk::now()), microsecs_elapsed(0), max_trial_count(max_trial_count), trial_count(0) {}

    inline void restart() noexcept {
        start_time = clk::now();
        microsecs_elapsed = 0;
    }

    // スコアの差分から，遷移するかどうかを確率的に決定して返す
    inline bool transit(float dif) noexcept {
        if (max_trial_count == -1) {
            clk::time_point cur_time = clk::now();
            microsecs_elapsed = chrono::duration_cast<chrono::microseconds>(cur_time - start_time).count();
            // 温度関数
            const float temperature =
                start_temp + (end_temp - start_temp) * ((float)microsecs_elapsed / timespan_microsecs);
            // 遷移確率関数(最大化の場合)
            float prob = exp((float)dif / temperature);

            // cout << dif, prob, '\n';
            return prob > rd();
        } else {
            trial_count++;

            // 温度関数
            const float temperature = start_temp + (end_temp - start_temp) * ((float)trial_count / max_trial_count);
            // 遷移確率関数(最大化の場合)
            float prob = exp((float)dif / temperature);

            // cout << dif, prob, '\n';
            return prob > rd();
        }
    }

    // transit の山登り版
    inline bool climb(float dif) noexcept {
        clk::time_point cur_time = clk::now();
        microsecs_elapsed = chrono::duration_cast<chrono::microseconds>(cur_time - start_time).count();
        return dif > 0;
    }

    // 時間切れかどうかを返す
    inline bool runnable() noexcept { return microsecs_elapsed < timespan_microsecs; }
};

/* #endregion */

/* #region dijkstra_f_restore */

/**
 * @param N ノード数
 * @param delta 隣接行列を生成する関数．delta(Node v, fn(Node t)).
 *              fn は現在の頂点 current と隣接する頂点を探索する関数．
 * @param index 頂点→頂点インデックス，のマップ関数．（index(Node v) -> int）
 * @return 距離テーブル
 */
template <class Node, class Delta, class Index, class Weight = ll, Weight inf = INF>
pair<Weight, vc<int>> dijkstra_f_restore(int N, const Node &start, const Node &terminal, Delta delta, Index index,
                                         vc<Weight> &dist, Weight init = 0) {
    struct state {
        Weight cost;
        Node dst;
        state(Weight cost, Node dst) : cost(cost), dst(dst) {}
        bool operator<(const state &o) const { return cost > o.cost; }
        // bool operator>(const state &o) const { return cost > o.cost; }
    };

    vc<int> bs(N, -1); // 経路復元用
    // vc<Weight> dist(N, inf);   // 距離テーブル
    fill(ALL(dist), inf);
    priority_queue<state> que; // 「訪問予定」頂点リスト
    {
        int idx = index(start);
        assert(0 <= idx && idx < N);
        dist[idx] = init; // 初期条件 (頂点 start を初期頂点とする)
        que.emplace(init, start);
    }

    while (!que.empty()) {
        state cur = que.top(); // tie(d, v) = que.top();
        que.pop();
        Node current = cur.dst;
        Weight cur_dist = cur.cost;
        int ci = index(current);

        if (dist[ci] < cur_dist) continue;

        // 隣接ノードに関するループは外に出す
        delta(current, [&](Node dst, Weight weight) -> void {
            Weight nxt_dist = cur_dist + weight;

            int idx = index(dst);
            assert(0 <= idx && idx < N);
            if (chmin(dist[idx], nxt_dist)) {
                que.emplace(nxt_dist, dst);
                bs[idx] = ci;
            }
        });
    }

    // 経路復元
    vc<int> res;
    int dst = index(terminal);
    int dst_bak = dst;
    // if (bs[dst] < 0) return res;
    while (~dst) res.emplace_back(dst), dst = bs[dst];
    reverse(ALL(res));
    // return res;

    return {dist[dst_bak], res};
}

/* #endregion */

template <size_t N = 64ull> string to_bin(ll x, bool show_base = false) {
    std::stringstream ss;
    if (show_base) ss << "0b";
    ss << std::bitset<N>(x);
    std::string s = ss.str();
    return s;
}

constexpr int N = 50;
constexpr int M = 20;

// Problem
void solve() {
    VAR(ll, n, m);
    assert(n == N);
    assert(m == M);
    vc<string> A(n);
    cin >> A;
    vll c(m), l(m);
    vvll a(m), b(m);
    REP(i, 0, m) {
        cin >> c[i], l[i];
        a[i].resize(l[i]);
        b[i].resize(l[i]);
        REP(j, 0, l[i]) cin >> a[i][j], b[i][j];
    }

    // ボード準備
    array<ull, N> board;
    fill(ALL(board), 0ull);
    REP(i, 0, n) REP(j, 0, n) {
        // dump(i, j);
        if (A[i][j] != '.') {
            board[i] |= (1ull << j);
        }
        // dump(to_bin<50>(board[i]));
    }
    // const ull mask = (1ull << N) - 1ull;

    // 爆弾準備
    constexpr ll offset = 20;
    array<array<ull, 41>, M> bombs;
    REP(i, 0, m) {
        fill(ALL(bombs[i]), 0ull);
        // offset を足した位置にする
        REP(j, 0, l[i]) {
            const ll row = offset + a[i][j];
            const ll col = offset + b[i][j];
            bombs[i][row] |= (1ull << col);
        }
    }

    // 50x50 の盤面，20 種類の爆弾
    // なるべく地元の爆弾屋から仕入れたい．
    // なるべく少ない爆弾でやりくりしたい．
    // 3000ms あるので解の改善もできるか．

    // まずは，どこで何を爆破させるのが得か，調べる．
    // sum(#,@)/c[i] が大きい位置・爆弾種類を調べる．

    vc<array<ll, 3>> rcbs;
    while (true) {
        // 効果的な爆弾を探す
        ld max_score = 0;
        ll argmax_row_center = -1;
        ll argmax_col_center = -1;
        ll argmax_bomb = -1;
        REP(row_center, 0, N) REP(col_center, 0, N) {
            REP(i, 0, m) {
                ld score = 0;
                // 行 [row_center-20] が bombs[i][0] と対応する
                // 列 [col_center-20] が bombs[i][0]&1 と対応する
                REP(row, max(0LL, row_center - 20), min(n, row_center + 21)) {
                    const ll row_idx = row - (row_center - 20);
                    if (col_center > 20) {
                        const ull bit = board[row] & (bombs[i][row_idx] << (col_center - 20));
                        score += __builtin_popcountll(bit);
                    } else {
                        const ull bit = board[row] & (bombs[i][row_idx] >> (20 - col_center));
                        score += __builtin_popcountll(bit);
                    }
                }
                score /= c[i];
                if (chmax(max_score, score)) {
                    argmax_row_center = row_center;
                    argmax_col_center = col_center;
                    argmax_bomb = i;
                }
            }
        }
        // dump(max_score, argmax_row_center, argmax_col_center, argmax_bomb, max_score * c[argmax_bomb]);
        assert(argmax_bomb != -1);
        rcbs.push_back({argmax_row_center, argmax_col_center, argmax_bomb});

        // 爆弾を適用する
        {
            REP(row, max(0LL, argmax_row_center - 20), min(n, argmax_row_center + 21)) {
                const ll row_idx = row - (argmax_row_center - 20);
                if (argmax_col_center > 20) {
                    const ull bit = board[row] & (bombs[argmax_bomb][row_idx] << (argmax_col_center - 20));
                    board[row] ^= bit;
                } else {
                    const ull bit = board[row] & (bombs[argmax_bomb][row_idx] >> (20 - argmax_col_center));
                    board[row] ^= bit;
                }
            }
        }
        // 残り破壊対象を数える
        {
            ll obj_count = 0;
            REP(row, 0, n) {
                obj_count += __builtin_popcountll(board[row]); //
            }
            // dump(obj_count);
            if (obj_count == 0) break;
        }
        // break;
    }
    rcbs.insert(rcbs.begin(), array<ll, 3>{0, 0, -1});
    // dump(rcbs);
    // dump(SIZE(rcbs));

    vc<int> indices(SIZE(rcbs));
    iota(ALL(indices), 0);

    // ここは問題ごとに作る
    auto rcdist = [&](const array<ll, 3> &p0, const array<ll, 3> &p1) -> ll {
        return abs(p1[0] - p0[0]) + abs(p1[1] - p0[1]); //
    };
    auto cdist = [&](const int i0, const int i1) -> ll {
        return rcdist(rcbs[i0], rcbs[i1]); //
    };

    // TSP として解く
    const ll max_trial_count = -1;
    // const ll max_trial_count = 20'000'000;
    int64_t timespan_microsecs = 2000 * 1000; // 焼きなます時間
    double start_temp = (double)(N / 7); // 開始温度 (一回の遷移で動きうるスコア幅の最大値程度);
    double end_temp = 1;                 // 終了温度 (一回の遷移で動きうるスコア幅の最小値程度);
    Anneal anneal(timespan_microsecs, start_temp, end_temp, __LINE__, max_trial_count);

    Rand<int> rand(0, SIZE(rcbs) - 2, __LINE__);
    Rand<int> choice(0, 99, __LINE__);
    ll tsp_diff = 0;
    ll min_tsp_diff = 0;
    vc<int> argmin_indices = indices;
    // REP(_trial, 0, max_trial_count) {
    //     anneal.runnable();
    while (anneal.runnable()) {
        const int cur_choice = choice();
        if (cur_choice < 75) {
            // 2-opt 近傍
            rand.set_param(0, SIZE(rcbs) - 2);
            int r0 = rand();
            if (r0 == 0 || r0 == SIZE(rcbs) - 2) {
                rand.set_param(0, SIZE(rcbs) - 2 - 2); // r0 と，r0 の直後/直後いずれか一方を除外する
            } else {
                rand.set_param(0, SIZE(rcbs) - 2 - 3); // r0 と，r0 の直前・直後を除外する
            }
            int r1 = rand();
            if (r1 == r0 - 1) r1++;
            if (r1 == r0) r1++;
            if (r1 == r0 + 1) r1++;
            if (r0 > r1) swap(r0, r1);
            assert(r0 < r1);
            assert(r0 + 1 != r1);
            assert(r1 <= SIZE(rcbs) - 2);
            // assert: 隣接していない辺同士を swap したい

            const int from0 = indices[r0];
            const int to0 = indices[r0 + 1];
            const int from1 = indices[r1];
            const int to1 = indices[r1 + 1];
            const int dist_old = cdist(from0, to0) + cdist(from1, to1);
            const int dist_new = cdist(from0, from1) + cdist(to0, to1);
            const int dif = dist_new - dist_old;
            if (anneal.transit(-dif)) {
                reverse(indices.begin() + r0 + 1, indices.begin() + r1 + 1);
                tsp_diff += dif;
                if (chmin(min_tsp_diff, tsp_diff)) {
                    argmin_indices = indices;
                }
            }
        } else if (cur_choice < 1000) {
            // 3-opt 近傍
            // https://www.researchgate.net/figure/All-possible-3-opt-recombination-cases-3-opt-Three-edges-of-a-tour-are-removed-in-a_fig2_287692116
            rand.set_param(0, SIZE(rcbs) - 2);
            int r0 = rand();
            if (r0 == 0 || r0 == SIZE(rcbs) - 2) {
                rand.set_param(0, SIZE(rcbs) - 2 - 2); // r0 と，r0 の直後/直後いずれか一方を除外する
            } else {
                rand.set_param(0, SIZE(rcbs) - 2 - 3); // r0 と，r0 の直前・直後を除外する
            }
            int r1 = rand();
            if (r1 == r0 - 1) r1++;
            if (r1 == r0) r1++;
            if (r1 == r0 + 1) r1++;
            if (r0 > r1) swap(r0, r1);
            assert(r0 < r1);
            assert(r0 + 1 != r1);
            if (r0 + 2 == r1) {
                // r0 の直後 = r1 の直前 のとき
                if (r0 == 0) {
                    if (r1 == SIZE(rcbs) - 2) {
                        // r0 と，r0 の直後と，r1 を除外する
                        rand.set_param(0, SIZE(rcbs) - 2 - 3);
                    } else {
                        // r0 と，r0 の直後と，r1 と，r1 の直後を除外する
                        rand.set_param(0, SIZE(rcbs) - 2 - 4);
                    }
                } else {
                    if (r1 == SIZE(rcbs) - 2) {
                        // r0 と，r0 の直前・直後と，r1 を除外する
                        rand.set_param(0, SIZE(rcbs) - 2 - 4);
                    } else {
                        // r0 と，r0 の直前・直後と，r1 と，r1 の直後を除外する
                        rand.set_param(0, SIZE(rcbs) - 2 - 5);
                    }
                }
            } else {
                // r0 の直後 < r1 の直前 のとき
                // r0 と，r0 の直前・直後と，r1 と，r1 の直後を除外する
                if (r0 == 0) {
                    if (r1 == SIZE(rcbs) - 2) {
                        // r0 と，r0 の直後と，r1 と，r1 の直前を除外する
                        rand.set_param(0, SIZE(rcbs) - 2 - 4);
                    } else {
                        // r0 と，r0 の直後と，r1 と，r1 の直前・直後を除外する
                        rand.set_param(0, SIZE(rcbs) - 2 - 5);
                    }
                } else {
                    if (r1 == SIZE(rcbs) - 2) {
                        // r0 と，r0 の直前・直後と，r1 と，r1 の直前を除外する
                        rand.set_param(0, SIZE(rcbs) - 2 - 5);
                    } else {
                        // r0 と，r0 の直前・直後と，r1 と，r1 の直前・直後を除外する
                        rand.set_param(0, SIZE(rcbs) - 2 - 6);
                    }
                }
            }
            int r2 = rand();
            if (r2 == r0 - 1) r2++;
            if (r2 == r0) r2++;
            if (r2 == r0 + 1) r2++;
            if (r2 == r1 - 1) r2++;
            if (r2 == r1) r2++;
            if (r2 == r1 + 1) r2++;
            if (r0 > r2) swap(r0, r2);
            if (r1 > r2) swap(r1, r2);
            assert(r0 < r1);
            assert(r1 < r2);
            assert(r0 + 1 != r1);
            assert(r1 + 1 != r2);
            assert(r2 <= SIZE(rcbs) - 2);

            const int from0 = indices[r0];
            const int to0 = indices[r0 + 1];
            const int from1 = indices[r1];
            const int to1 = indices[r1 + 1];
            const int from2 = indices[r2];
            const int to2 = indices[r2 + 1];

            const int dist_old = cdist(from0, to0) + cdist(from1, to1) + cdist(from2, to2);
            int argmin_type = 0;
            int min_dist = dist_old;
            {
                // type 1
                const int dist_new = cdist(from0, to0) + cdist(from1, from2) + cdist(to1, to2);
                if (chmin(min_dist, dist_new)) {
                    argmin_type = 1;
                }
            }
            {
                // type 2
                const int dist_new = cdist(from0, from1) + cdist(to0, to1) + cdist(from2, to2);
                if (chmin(min_dist, dist_new)) {
                    argmin_type = 2;
                }
            }
            {
                // type 3
                const int dist_new = cdist(from0, from2) + cdist(to1, from1) + cdist(to0, to2);
                if (chmin(min_dist, dist_new)) {
                    argmin_type = 3;
                }
            }
            {
                // type 4
                const int dist_new = cdist(from0, from2) + cdist(to1, to0) + cdist(from1, to2);
                if (chmin(min_dist, dist_new)) {
                    argmin_type = 4;
                }
            }
            {
                // type 5
                const int dist_new = cdist(from0, to1) + cdist(from2, from1) + cdist(to0, to2);
                if (chmin(min_dist, dist_new)) {
                    argmin_type = 5;
                }
            }
            {
                // type 6
                const int dist_new = cdist(from0, from1) + cdist(to0, from2) + cdist(to1, to2);
                if (chmin(min_dist, dist_new)) {
                    argmin_type = 6;
                }
            }
            {
                // type 7
                const int dist_new = cdist(from0, to1) + cdist(from2, to0) + cdist(from1, to2);
                if (chmin(min_dist, dist_new)) {
                    argmin_type = 7;
                }
            }
            if (argmin_type == 0) continue;
            const int dif = min_dist - dist_old;
            if (anneal.transit(-dif)) {
                if (argmin_type == 1) {
                    reverse(indices.begin() + r1 + 1, indices.begin() + r2 + 1);
                } else if (argmin_type == 2) {
                    reverse(indices.begin() + r0 + 1, indices.begin() + r1 + 1);
                } else if (argmin_type == 3) {
                    reverse(indices.begin() + r0 + 1, indices.begin() + r2 + 1);
                } else if (argmin_type == 4) {
                    reverse(indices.begin() + r0 + 1, indices.begin() + r1 + 1);
                    reverse(indices.begin() + r0 + 1, indices.begin() + r2 + 1);
                } else if (argmin_type == 5) {
                    reverse(indices.begin() + r1 + 1, indices.begin() + r2 + 1);
                    reverse(indices.begin() + r0 + 1, indices.begin() + r2 + 1);
                } else if (argmin_type == 6) {
                    reverse(indices.begin() + r0 + 1, indices.begin() + r1 + 1);
                    reverse(indices.begin() + r1 + 1, indices.begin() + r2 + 1);
                } else {
                    assert(argmin_type == 7);
                    reverse(indices.begin() + r0 + 1, indices.begin() + r1 + 1);
                    reverse(indices.begin() + r1 + 1, indices.begin() + r2 + 1);
                    reverse(indices.begin() + r0 + 1, indices.begin() + r2 + 1);
                }
                tsp_diff += dif;
                if (chmin(min_tsp_diff, tsp_diff)) {
                    argmin_indices = indices;
                }
            }
        }
    }
    // dump(tsp_diff, min_tsp_diff);
    indices = argmin_indices;
    // indices にソート結果がある
    // dump(rcbs);
    // dump(SIZE(rcbs));

    using Node = pair<int, int>; // row, col
    const static vc<int> dx{1, 0, -1, 0};

    // 隣接行列生成関数
    auto delta = [&](const Node &current, function<void(Node, int)> transit) -> void {
        auto [r, c] = current;
        // 隣接ノードに関するループ
        for (int q = 0; q < 4; q++) {
            const int nr = r + dx[q];
            const int nc = c + dx[q ^ 1];
            // if (nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
            if (0 <= nr && nr < N && 0 <= nc && nc < N) {
                if ((board[nr] >> nc) & 1) {
                    transit(Node(nr, nc), 2); // コスト 2 で遷移
                } else {
                    transit(Node(nr, nc), 1); // コスト 1 で遷移
                }
            }
        }
    };
    // インデックス生成関数
    auto index = [&](const Node &v) -> int { return v.first * N + v.second; };
    vll dists0(N * N);
    vll dists1(N * N);

    // できるだけ直前まで残っている店で爆弾を仕入れるようにする
    array<ull, N> board_shop;
    fill(ALL(board_shop), 0ull);
    fill(ALL(board), 0ull);
    REP(i, 0, n) REP(j, 0, n) {
        // dump(i, j);
        if (A[i][j] != '.') {
            board[i] |= (1ull << j);
        }
        if (A[i][j] == '@') {
            board_shop[i] |= (1ull << j);
        }
    }
    vc<array<ll, 3>> operations;
    REP(i, 1, SIZE(rcbs)) {
        // rcbs[indices[i-1]] 〜 rcbs[indices[i]] の間で店に寄るとして，どこに寄るのが最善か？
        // 更地を通ったほうがお得！
        const Node start = {rcbs[indices[i - 1]][0], rcbs[indices[i - 1]][1]};
        const Node goal = {rcbs[indices[i]][0], rcbs[indices[i]][1]};
        auto [dist0, res0] = dijkstra_f_restore(N * N, start, goal, delta, index, dists0, 0LL);
        auto [dist1, res1] = dijkstra_f_restore(N * N, goal, start, delta, index, dists1, 0LL);

        ll min_dist = IINF;
        ll argmin_row = -1;
        ll argmin_col = -1;
        REP(row, 0, n) REP(col, 0, n) {
            if ((board_shop[row] >> col) & 1) {
                // array<ll, 3> t{row, col, -1};
                // const ll dist = cdist(rcbs[i - 1], t) + cdist(rcbs[i], t);
                // const ll dist = rcdist(rcbs[indices[i]], t);
                const ll dist0 = dists0[N * row + col];
                const ll dist1 = dists1[N * row + col];
                const ll dist = dist0 + 4 * dist1;
                if (chmin(min_dist, dist)) {
                    argmin_row = row;
                    argmin_col = col;
                }
            }
        }
        // 店が見つかったら必ず立ち寄る
        if (argmin_row != -1) {
            assert(argmin_col != -1);
            operations.push_back({argmin_row, argmin_col, -10000 - min_dist});
        }
        operations.push_back(rcbs[indices[i]]);

        // 爆弾適用
        const auto [argmax_row_center, argmax_col_center, argmax_bomb] = rcbs[indices[i]];
        REP(row, max(0LL, argmax_row_center - 20), min(n, argmax_row_center + 21)) {
            const ll row_idx = row - (argmax_row_center - 20);
            if (argmax_col_center > 20) {
                const ull bit = board[row] & (bombs[argmax_bomb][row_idx] << (argmax_col_center - 20));
                board[row] ^= bit;
                const ull bit_shop = board_shop[row] & (bombs[argmax_bomb][row_idx] << (argmax_col_center - 20));
                board_shop[row] ^= bit_shop;
            } else {
                const ull bit = board[row] & (bombs[argmax_bomb][row_idx] >> (20 - argmax_col_center));
                board[row] ^= bit;
                const ull bit_shop = board_shop[row] & (bombs[argmax_bomb][row_idx] >> (20 - argmax_col_center));
                board_shop[row] ^= bit_shop;
            }
        }
    }
    // dump(operations);
    // dump(SIZE(operations));

    // 店の訪問時に，どの操作で使う爆弾を仕入れるか調べる
    vvll op2idx(SIZE(operations));
    vll stock;
    REPR(i, SIZE(operations) - 1, 0) {
        if (operations[i][2] >= 0) { // 爆弾を使用する操作
            stock.push_back(i);
        } else { // 爆弾を購入する操作
            op2idx[i] = stock;
            stock.clear();
        }
    }
    // dump(op2idx);

    // ある店への訪問を，直前の訪問にマージしたほうがよいか？
    REPR(i, SIZE(operations) - 1, 0) {
        if (operations[i][2] < 0) {
            // 直後の店への訪問を探す
            ll nxt_shop_j = -1;
            REP(j, i + 1, SIZE(operations)) {
                if (operations[j][2] < 0) {
                    nxt_shop_j = j;
                    break;
                }
            }
            if (nxt_shop_j == -1) continue;

            // 元の移動コスト計算
            ll cur_cost = 0;
            {
                ll prev = i;
                REPR(j, SIZE(op2idx[i]) - 1, 0) {
                    // j+1 個の爆弾を持っている
                    const ll d = rcdist(operations[prev], operations[op2idx[i][j]]);
                    cur_cost += (j + 2) * (j + 2) * d;
                }
                prev = nxt_shop_j;
                REPR(j, SIZE(op2idx[nxt_shop_j]) - 1, 0) {
                    // j+1 個の爆弾を持っている
                    const ll d = rcdist(operations[prev], operations[op2idx[nxt_shop_j][j]]);
                    cur_cost += (j + 2) * (j + 2) * d;
                }
            }

            // 新しい移動コストを計算
            ll nxt_cost = 0;
            {
                ll prev = i;
                REPR(j, SIZE(op2idx[i]) - 1, 0) {
                    // j+1+SIZE(op2idx[nxt_shop_j]) 個の爆弾を持っている
                    const ll d = rcdist(operations[prev], operations[op2idx[i][j]]);
                    nxt_cost += (j + 2 + SIZE(op2idx[nxt_shop_j])) * (j + 2 + SIZE(op2idx[nxt_shop_j])) * d;
                }
                REPR(j, SIZE(op2idx[nxt_shop_j]) - 1, 0) {
                    // j+1 個の爆弾を持っている
                    const ll d = rcdist(operations[prev], operations[op2idx[nxt_shop_j][j]]);
                    nxt_cost += (j + 2) * (j + 2) * d;
                }
            }

            // マージしたほうが得ならマージする（後の店訪問は削除する）
            if (nxt_cost < cur_cost) {
                // dump(nxt_cost, cur_cost, op2idx[i], op2idx[nxt_shop_j]);
                // op2idx[i].insert(op2idx[i].end(), ALL(op2idx[nxt_shop_j])); // インデックスが 1 ずれるので駄目
                // op2idx[nxt_shop_j] 以降はインデックスを1つずつデクリメントする
                REP(j, nxt_shop_j, SIZE(op2idx)) {
                    if (SIZE(op2idx[j])) {
                        op2idx[j]--;
                    }
                }
                // for (const auto ii : op2idx[nxt_shop_j]) {
                //     op2idx[i].push_back(ii - 1);
                // }
                op2idx[i].insert(op2idx[i].end(), ALL(op2idx[nxt_shop_j]));
                // dump(nxt_cost, cur_cost, op2idx[i], op2idx[nxt_shop_j]);
                operations.erase(operations.begin() + nxt_shop_j);
                op2idx.erase(op2idx.begin() + nxt_shop_j);
            }
        }
    }

    fill(ALL(board_shop), 0ull);
    fill(ALL(board), 0ull);
    REP(i, 0, n) REP(j, 0, n) {
        // dump(i, j);
        if (A[i][j] != '.') {
            board[i] |= (1ull << j);
        }
        if (A[i][j] == '@') {
            board_shop[i] |= (1ull << j);
        }
    }

    int row = 0;
    int col = 0;
    vc<string> ans;
    int bomb_count = 0;
    ll cost_sum = 0;
    REP(i, 0, SIZE(operations)) {
        if (operations[i][2] >= 0) { // 爆弾を使用する操作

            // 移動する
            // なるべく更地を通ったほうが低コスト！
            const Node start = {row, col};
            const Node goal = {operations[i][0], operations[i][1]};
            auto [dist, res] = dijkstra_f_restore(N * N, start, goal, delta, index, dists0, 0LL);

            const ll basecost = (bomb_count + 1) * (bomb_count + 1);
            REP(j, 1, SIZE(res)) {
                const int nxt_row = res[j] / N;
                const int nxt_col = res[j] % N;
                while (row < nxt_row) {
                    row++;
                    ans.push_back("1 D");
                    cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
                }
                while (row > nxt_row) {
                    row--;
                    ans.push_back("1 U");
                    cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
                }
                while (col < nxt_col) {
                    col++;
                    ans.push_back("1 R");
                    cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
                }
                while (col > nxt_col) {
                    col--;
                    ans.push_back("1 L");
                    cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
                }
            }
            // ans.push_back("# " + to_string(row) + ", " + to_string(col));
            // 爆弾を使用する
            assert(operations[i][2] >= 0);
            assert(operations[i][2] < M);
            ans.push_back("3 " + to_string(operations[i][2] + 1));
            bomb_count--;

            // 盤面更新
            const auto [argmax_row_center, argmax_col_center, argmax_bomb] = operations[i];
            REP(row, max(0LL, argmax_row_center - 20), min(n, argmax_row_center + 21)) {
                const ll row_idx = row - (argmax_row_center - 20);
                if (argmax_col_center > 20) {
                    const ull bit = board[row] & (bombs[argmax_bomb][row_idx] << (argmax_col_center - 20));
                    board[row] ^= bit;
                    const ull bit_shop = board_shop[row] & (bombs[argmax_bomb][row_idx] << (argmax_col_center - 20));
                    board_shop[row] ^= bit_shop;
                } else {
                    const ull bit = board[row] & (bombs[argmax_bomb][row_idx] >> (20 - argmax_col_center));
                    board[row] ^= bit;
                    const ull bit_shop = board_shop[row] & (bombs[argmax_bomb][row_idx] >> (20 - argmax_col_center));
                    board_shop[row] ^= bit_shop;
                }
            }

        } else { // 爆弾を購入する操作
            if (SIZE(op2idx[i]) == 0) continue;
            // 移動する
            // なるべく更地を通ったほうが低コスト！
            const Node start = {row, col};
            const Node goal = {operations[i][0], operations[i][1]};
            auto [dist, res] = dijkstra_f_restore(N * N, start, goal, delta, index, dists0, 0LL);

            const ll basecost = (bomb_count + 1) * (bomb_count + 1);
            REP(j, 1, SIZE(res)) {
                const int nxt_row = res[j] / N;
                const int nxt_col = res[j] % N;
                while (row < nxt_row) {
                    row++;
                    ans.push_back("1 D");
                    cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
                }
                while (row > nxt_row) {
                    row--;
                    ans.push_back("1 U");
                    cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
                }
                while (col < nxt_col) {
                    col++;
                    ans.push_back("1 R");
                    cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
                }
                while (col > nxt_col) {
                    col--;
                    ans.push_back("1 L");
                    cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
                }
            }
            // ans.push_back("# " + to_string(row) + ", " + to_string(col));
            // 爆弾を購入する
            for (const ll idx : op2idx[i]) {
                if (operations[idx][2] < 0) {
                    dump(idx, operations[idx][2]);
                }
                assert(operations[idx][2] >= 0);
                assert(operations[idx][2] < M);
                ans.push_back("2 " + to_string(operations[idx][2] + 1));
                bomb_count++;
                cost_sum += c[operations[idx][2]];
            }
        }
    }
    // dump(cost_sum);
    pprint(SIZE(ans));
    for (const string &line : ans) {
        pprint(line); //
    }
}

// entry point
int main() {
    solve();
    return 0;
}