#include"paint.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int INF=1e9;
int cnt[MAXN],cc[MAXN],dp[MAXN],pref[MAXN];
vector<int> vi[MAXN];
pair<unsigned short,bool> op[MAXN*677];
bool ck[MAXN];
void update(int i,int val)
{
cc[cnt[i]]--;
cc[cnt[i]+=val]++;
}
int minimumInstructions(int N,int M,int K,vector<int> C,vector<int> A,vector< vector<int> > B)
{
for(int i=0;i<M;i++) for(auto v:B[i]) vi[v].push_back(i);
for(int i=0;i<N;i++) for(auto v:vi[C[i]])
{
int pos=((v-i)%M+M)%M;
pref[max(0,i-M+1)]++,pref[i+1]++;
}
for(int i=1;i<=N+1;i++) pref[i]+=pref[i-1];
for(int i=0;i<N;i++) for(auto v:vi[C[i]])
{
int pos=((v-i)%M+M)%M;
op[--pref[max(0,i-M+1)]]={pos,1};
op[--pref[i+1]]={pos,0};
}
for(int i=0;i<=N-M;i++)
{
for(int j=pref[i];j<pref[i+1];j++) if(op[j].second) update(op[j].first,1);
else update(op[j].first,-1);
if(cc[M]) ck[i+M]=true;
}
deque<int> dq;
dq.push_back(0);
for(int i=1;i<=N;i++)
{
if(ck[i])
{
if(!dq.empty()) dp[i]=dp[dq.front()]+1;
else dp[i]=INF;
}
else dp[i]=INF;
while(!dq.empty()&&dp[dq.back()]>=dp[i]) dq.pop_back();
dq.push_back(i);
if(dq.front()==i-M) dq.pop_front();
}
if(dp[N]>N) return -1;
return dp[N];
}
