#include "paint.h"
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define all(x) x.begin(),x.end();
using ll=long long;
inline int safe_mod(int x,int y){
int ret=x%y;
if(ret<0){
ret+=y;
}
return ret;
}
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>> cols(K);
rep(i,M){
for(int j:B[i]){
cols[j].emplace_back(i);
}
}
vector<int> seg(M);
vector<int> can(N,-1);
int cnt=0;
rep(i,N){
for(int j:cols[C[i]]){
seg[safe_mod(j-i,M)]++;
if(seg[safe_mod(j-i,M)]==M)cnt++;
}
if(cnt){
can[i-M+1]=i-M+1;
}
if(i-M+1>=0){
for(int j:cols[C[i-M+1]]){
if(seg[safe_mod(j-(i-M+1),M)]==M)cnt--;
seg[safe_mod(j-(i-M+1),M)]--;
}
}
}
rep(i,N){
if(i<N-1)can[i+1]=max(can[i],can[i+1]);
}
int pos=0;
int ans=0;
while(pos<N){
if(can[pos]==-1)return -1;
if(can[pos]+M<=pos)return -1;
pos=can[pos]+M;
ans++;
}
return ans;
}
