#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
bool can[100005];
int m, cc[50005], freq[50005];
vector<int> c, in[100005];
void add(int i){
for (auto a:in[c[i]])--freq[cc[(i-a%m+m)%m]], ++cc[(i-a%m+m)%m], ++freq[cc[(i-a%m+m)%m]];
}
void del(int i){
for (auto a:in[c[i]])--freq[cc[(i-a%m+m)%m]], --cc[(i-a%m+m)%m], ++freq[cc[(i-a%m+m)%m]];
}
int minimumInstructions(int n, int M, int k, vector<int> C, vector<int> a, vector<vector<int> > b){
m=M;
c=C;
for (int i=0; i<m; ++i)for (auto num:b[i])in[num].pb(i);
freq[0]=m;
for (int i=0; i<m; ++i)add(i);
can[0]=!!freq[m];
for (int i=m; i<n; ++i)del(i-m), add(i), can[i-m+1]=!!freq[m];
int ans=0, p=-1, i=0;
while (1){
int mx=-1;
while (p<i)if (can[++p])mx=p+m;
++ans;
if (mx>=n)return ans;
if (mx==-1)return -1;
i=mx;
}
}
