1982D - Beauty of the mountains ~~~~~

include <bits/stdc++.h>

include <ext/pb_ds/assoc_container.hpp>

include <ext/pb_ds/tree_policy.hpp>

// #include <atcoder/all>

define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>

// #define int long long

const int mod = 1e9 + 7; const int N = 1e5 + 9; const int inf = 1e9;

using namespace __gnu_pbds; using namespace std; // using namespace atcoder;

void solve() { int n, m, k; cin >> n >> m >> k;

vector<vector<int>> mountain(n, vector<int>(m));
vector<string> mountain_type(n);

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        cin >> mountain[i][j];
    }
}

for (int i = 0; i < n; i++) {
    cin >> mountain_type[i];
}

int snowy = 0, not_snowy = 0;

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (mountain_type[i][j] == '0') {
            not_snowy += mountain[i][j];
        } else {
            snowy += mountain[i][j];
        }
    }
}

int diff = abs(snowy - not_snowy);


vector<vector<int>> prefix(n + 1, vector<int>(m + 1, 0));

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        prefix[i][j] = (mountain_type[i - 1][j - 1] - '0') + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
    }
}

set<int> factors;


for (int i = k; i <= n; i++) {
    for (int j = k; j <= m; j++) {
        int total_snowy = prefix[i][j] - prefix[i - k][j] - prefix[i][j - k] + prefix[i - k][j - k];
        factors.insert(abs(k * k - 2 * total_snowy));
    }
}

int tot_gcd = (factors.size()==0) ? 0 : *factors.begin();
if(factors.size()==0) {
    if(diff == 0) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
        return;
}
for (auto x : factors) {
 if (x == 0) {
        continue;
    }
    tot_gcd = __gcd(tot_gcd, x);
}

if (diff % tot_gcd == 0) {
    cout << "YES" << endl;
} else {
    cout << "NO" << endl;
}

}

signed main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; cin >> t; while (t--) { solve(); } return 0; } ~~~~~