#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B)
{
vector<int> idx[K];
for (int i = 0; i < M; i++)
{
for (int &j : B[i]) idx[j].push_back(i);
}
vector<int> cnt(M, 0);
int cM = 0;
vector<int> ok(N, 0);
for (int i = N - 1; i >= 0; i--)
{
for (int &j : idx[C[i]])
{
cM -= (cnt[(i - j + M) % M]++ == M);
cM += (cnt[(i - j + M) % M] == M);
}
if (i + M < N) for (int &j : idx[C[i + M]])
{
cM -= (cnt[(i - j + M) % M]-- == M);
cM += (cnt[(i - j + M) % M] == M);
}
if (cM) ok[i] = 1;
}
int res = 0;
for (int l = 0, last = -1, mx = -M; l < N; l++)
{
while (last < l)
{
last++;
if (ok[last]) mx = max(mx, last);
}
if (mx + M <= l) return -1;
l = mx + M;
res++;
}
return res;
}
