Code: Equal Multisets (Hard Version)

/**
 *    author:  tourist
 *    created: 28.03.2026 07:59:42
 **/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--)
        [&]() -> void {
            int n, k;
            cin >> n >> k;
            vector<int> a(n);
            for (int i = 0; i < n; i++) {
                cin >> a[i];
                --a[i];
            }
            vector<int> b(n);
            for (int i = 0; i < n; i++) {
                cin >> b[i];
                --b[i];
            }
            for (int r = 0; r < k; r++) {
                bool diff = false;
                for (int i = r; i < n; i += k) {
                    if (a[i] != a[r]) {
                        diff = true;
                        break;
                    }
                }
                if (diff) {
                    for (int i = r; i < n; i += k) {
                        if (b[i] < 0) {
                            b[i] = a[i];
                        } else {
                            if (b[i] != a[i]) {
                                cout << "NO" << '\n';
                                return;
                            }
                        }
                    }
                    continue;
                }
                int any = -1;
                for (int i = r; i < n; i += k) {
                    if (b[i] >= 0) {
                        any = b[i];
                        break;
                    }
                }
                if (any != -1) {
                    for (int i = r; i < n; i += k) {
                        if (b[i] < 0) {
                            b[i] = any;
                        } else {
                            if (b[i] != any) {
                                cout << "NO" << '\n';
                                return;
                            }
                        }
                    }
                    continue;
                }
            }
            vector<int> cnt(n);
            for (int i = 0; i < k; i++) {
                cnt[a[i]] += 1;
            }
            for (int i = 0; i < k; i++) {
                if (b[i] < 0) {
                    continue;
                }
                if (cnt[b[i]] == 0) {
                    cout << "NO" << '\n';
                    return;
                }
                cnt[b[i]] -= 1;
            }
            cout << "YES" << '\n';
        }();
    return 0;
}