#include "paint.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b)
{
vector <ll> cnt(m, 0), to(n, -1);
vector <vector <ll>> ok(k);
for (ll i=0; i<m; i++)
for (ll c:b[i]) ok[c].pb(i);
ll cntall=0;
auto upd=[&](ll id, ll v)
{
id=(id%m+m)%m, cnt[id]+=v;
if (cnt[id]==m && v==1) cntall++;
if (cnt[id]==m-1 && v==-1) cntall--;
};
for (ll i=0; i<m; i++)
for (ll p:ok[c[i]]) upd(p-i, 1);
if (cntall) to[0]=m;
for (ll i=1; i+m<=n; i++)
{
for (ll p:ok[c[i-1]]) upd(p-i+1, -1);
for (ll p:ok[c[i+m-1]]) upd(p-i+1, 1);
if (cntall) to[i]=i+m;
}
for (ll i=0; i+1<n; i++)
to[i+1]=max(to[i+1], to[i]);
ll cr=0, ans=0;
while (cr<n)
{
if (to[cr]<=cr) return -1;
cr=to[cr], ans++;
}
return ans;
}
