#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../../debug.hpp"
#else
#define debug(...) 42
#endif
int minimumInstructions(
int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
vector<vector<int>> g(K);
for (int i = 0; i < M; i++) {
for (int j : B[i]) {
g[j].push_back(i);
}
}
int cnt_m = 0;
vector<int> cnt(M);
for (int i = 0; i < M; i++) {
for (int j : g[C[i]]) {
int id = (j - i + M) % M;
cnt[id]++;
if (cnt[id] == M) {
cnt_m++;
}
}
}
if (!cnt_m) {
return -1;
}
int ans = 1;
int lst = M - 1;
int best = M - 1;
for (int i = 1; i + M - 1 < N; i++) {
for (int j : g[C[i - 1]]) {
int id = ((j - (i - 1)) % M + M) % M;
if (cnt[id] == M) {
cnt_m--;
}
cnt[id]--;
}
for (int j : g[C[i + M - 1]]) {
int id = (j - (i + M - 1) % M + M) % M;
cnt[id]++;
if (cnt[id] == M) {
cnt_m++;
}
}
if (cnt_m) {
best = i + M - 1;
}
if (i == lst + 1) {
if (best < i) {
return -1;
}
ans++;
lst = best;
}
}
if (best < N - 1) {
return -1;
}
if (lst < best) {
ans++;
}
return ans;
}
