#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int n;
vector<pair<int, int>> G;
vector<int> f[5000], g[5000], c[5000], rev[5000];
bool used[5000];

int dfs (int v, int C, int d) {
    used[v] = true;
    if (v == n - 1)
        return C;
    for (int i = 0; i < g[v].size(); i++)
        if ( !used[g[v][i]] && c[v][i] - f[v][i] >= d) {
            int k = dfs (g[v][i], min(C, c[v][i] - f[v][i]), d);
            if (k) {
                f[v][i] += k;
                f[g[v][i]][rev[v][i]] -= k;
                return k;
            }
        }
    return 0;
}
int valents (char el) {
    switch (el) {
        case 'H':
            return 1;
        case 'O':
            return 2;
        case 'N':
            return 3;
        case 'C':
            return 4;
    }
    return 0;
}

void add_edge (int u, int v, int w) {
    G.emplace_back(u, v);
    f[u].push_back(0);
    c[u].push_back(w);
    g[u].push_back(v);
    rev[u].push_back(g[v].size());
    f[v].push_back(0);
    c[v].push_back(0);
    g[v].push_back(u);
    rev[v].push_back(g[u].size() - 1);
}

bool checkEquals(string st[8888], int h, int w){
    bool bw = true;
    long long valB = 0;
    long long valW = 0;
    for (int i{0}; i < h; i++) {
        for (int j{0}; j < w; j++){
            if(bw)
                valB += valents(st[i][j]);
            else
                valW += valents(st[i][j]);
            bw = !bw;
        }
    }
    return valB == valW;
}
bool cheack(int val, int h, int w, int i , int j, string st[8888]){
    for (int k{i-1}; k < i + 2; k++) {
        for (int m{j-1}; m < j + 2; m++){
            if(k > -1 && k < h && m > -1 && m < w && !(m==j && k==i)){
                if(st[k][m]!='.'){
                    val--;
                }
            }
        }
    }
    return val > 1;
}
bool checkNeib(string st[8888], int h, int w){
    int val;
    for (int i{0}; i < h; i++) {
        for (int j{0}; j < w; j++){
            val = valents(st[i][j]);
            if(cheack(val, h, w, i, j, st)){
                return false;
            }
        }
    }
    return true;
}
int main () {
    int h, w;
    cin >> h >> w;
    n = 1;
    string st[8888];
    bool flag = true;
    int num[51][51];
    for (int i{0}; i < h; i++) {
        cin >> st[i];
        for (int j = 0; j < w; j++) {
            num[i][j] = i * w + j + 1;
            if (st[i][j] != '.')
                flag = false;
        }
    }
    if(h ==1 || w == 1){
        cout << "Valid";
        return 0;
    }
    if (flag) {
        cout << "Invalid";
        return 0;
    }
    long long potok = 0;
    n = h*w + 2;
    for (int i{0}; i < h; i++)
        for (int j{0}; j < w; j++) {
            if ( ((i & 1) && (j & 1)) || (!(i&1) && !(j&1)) ) {
                add_edge (0, num[i][j], valents(st[i][j]));
                potok += valents(st[i][j]);
                if (i + 1 < h)
                    add_edge (num[i][j], num[i+1][j], 1);
                if (j + 1 < w)
                    add_edge (num[i][j], num[i][j+1], 1);
                if (i - 1 >= 0)
                    add_edge (num[i][j], num[i-1][j], 1);
                if (j - 1 >= 0)
                    add_edge (num[i][j], num[i][j-1], 1);
            } else
                add_edge (num[i][j], n - 1, valents(st[i][j]));
        }

    long long s = 0;
    for (int i = (1 << 30); i >= 1; i >>= 1) {
        while (true) {
            memset(used, false, sizeof used);
            int k = dfs(0, 1 << 30, i);
            if (!k)
                break;
            s += k;
        }
    }
    if(!checkEquals(st, h, w)){
        cout << "Invalid";
        return 0;
    }
    cout <<  ((s == potok) ? "Valid" : "Invalid");
    return 0;
}