#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
template<class T, class S>
ostream& operator << (ostream &o, const pair<T, S> &p) { return o<<'('<<p.first<<", "<<p.second<<')'; }
template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t){
    while(*sdbg != ',') { cerr<<*sdbg++; } cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}
#ifdef DEBUG
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr<<#x<<": "; for(auto i:x) cerr<<i<<" "; cerr<<endl;}}
#define debugr(l,r,x) {{cerr<<#x<<": "; for(int i=l;i<=r;i++) cerr<<x<<" "; cerr<<endl;}}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define debugr(l,r,x)
#define cerr while(0) cerr
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define int long long
typedef __int128 INT;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define priority_queue std::priority_queue
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(x,l,r) for(auto x=l; x<r; x++)
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

vi adj[300];
vi nadj[300];
int idx(int x, int y){
    return (x << 4) + y;
}

pii unidx(int x){
    return pii(x >> 4, x & 15);
}

/**
 * Author: Dion Ong
 * Description: Standard sudoku solver for an N by N grid (1-indexed rows/cols).
 * Need to fill with entries from 1 to N; no repeats in columns, rows, and K by L boxes.
 * Time: Problem specific. Has worked on N ~ 9.
 * Status: Tested on GNY 2019, SPOJ EASUDOKU
 */

template <typename T>
struct sudoku{
    int N=9, K=3, L=3; T blnk=0;
    vector<vector<T>> a;
    set<pair<pii, int>> available;
    vector<pii> val[300];
    inline pair<pii, int> get_elt(int x, int y) {
        return {{score(x, y), -adj[idx(x, y)].size()}, idx(x, y)};
    }
    inline void remove(int x, int y) {
        if(a[x][y]) return;
        available.erase(get_elt(x, y));
    }
    inline void add(int x, int y) {
        if(a[x][y]) return;
        available.insert(get_elt(x, y));
    }
    sudoku(int N, int K, int L, vector<vector<T>> &a): N(N), K(K), L(L), a(a){
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                add(i, j);
            }
        }
    }
    bool find(int &x, int &y){
        if(available.empty())
            return false;
        auto [a, b] = unidx(available.begin()->S);
        x = a;
        y = b;
        return true;
    }
    bool in_col(int x, T v){
        for(int i=1;i<=N;i++)
            if(a[i][x]==v) return true;
        return false;
    }
    bool in_row(int x, T v){
        for(int i=1;i<=N;i++)
            if(a[x][i]==v) return true;
        return false;
    }
    bool neighbor(int x, int y, T v) {
        for (auto cell : adj[idx(x, y)]) {
            auto [x1, y1] = unidx(cell);
            if (a[x1][y1] && abs(a[x1][y1] - v) != 1)
                return false;
        }
        for (auto cell : nadj[idx(x, y)]) {
            auto [x1, y1] = unidx(cell);
            if (a[x1][y1] && abs(a[x1][y1] - v) == 1)
                return false;
        }
        return true;
    }
    bool good(int x, int y, T v){
        if(in_row(x, v) || in_col(y, v)) return false;
        if(!neighbor(x, y, v)) return false;
        return true;
    }
    int score(int x, int y){
        int ret = 0;
        vi done(N+1, 0);
        for (int i=1; i<=N; i++) {
            done[a[x][i]] = true;
            done[a[i][y]] = true;
        }
        for(int i=1; i<=N; i++){
            if (done[i]) continue;
            ret += neighbor(x, y, i);
        }
        return ret;
    }
    bool solve(){
        int x, y;
        if(!find(x, y)) return true;
        for(T i=1;i<=N;i++){
            if(good(x, y, i)){
                for (int i=1; i<=N; i++) {
                    remove(x, i);
                    remove(i, y);
                }
                a[x][y]=i;
                for (int i=1; i<=N; i++) {
                    add(x, i);
                    add(i, y);
                }
                available.erase(get_elt(x, y));
                if(solve()) return true;
                for (int i=1; i<=N; i++) {
                    remove(x, i);
                    remove(i, y);
                }
                a[x][y]=blnk;
                for (int i=1; i<=N; i++) {
                    add(x, i);
                    add(i, y);
                }
            }
        }
        return false;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector v(n+1, vector(n+1, 0));
    for (int i = 1; i < 2*n; i++){
        int iv = (i+1)/2;
        if (i % 2){
            for (int j = 1; j < n; j++) {
                char c;
                cin >> c;
                if (c == '1'){
                    adj[idx(iv, j)].push_back(idx(iv, j+1));
                    adj[idx(iv, j+1)].push_back(idx(iv, j));
                }
            }
        }
        else {
            for (int j = 1; j <= n; j++) {
                char c;
                cin >> c;
                if (c == '1') {
                    adj[idx(iv, j)].push_back(idx(iv+1, j));
                    adj[idx(iv+1, j)].push_back(idx(iv, j));
                }
            }
        }
    }
    auto inside = [&](int x, int y){
        return 0 < x && 0 < y && x <= n && y <= n;
    };
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            vector<pii> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            for (auto [dx, dy] : dirs){
                int cx = i+dx, cy = j+dy;
                if (inside(cx, cy) && find(all(adj[idx(i, j)]), idx(cx, cy)) == adj[idx(i, j)].end()){
                    nadj[idx(i, j)].push_back(idx(cx, cy));
                }
            }
        }
    }
    while(k--){
        int x, y, s;
        cin >> x >> y >> s;
        v[x][y] = s;
    }
    sudoku solver(n, 1, 1, v);
    solver.solve();
    for (int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cout << solver.a[i][j] << " ";
        }
        cout << "\n";
    }
}