#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int r[100005], l[100005];
int pos[100005];
vector<int> col[100005];
int la[100005];
int minimumInstructions(
int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
for(int i = 0; i < M; ++i)
for(int& j : B[i])
col[j].push_back(i);
for(int i = 1; i <= N; ++i){
for(int& x : col[C[i - 1]]){
if(i > x && i - x + r[i - x] == i){
++r[i - x];
}
}
}
for(int i = N; i >= 1; --i){
for(int& x : col[C[i - 1]]){
if(i + M - 1 - x <= N && i + M - 1- x - l[i + M - 1 - x] == i){
++l[i + M - 1 - x];
}
}
}
for(int i = 1; i <= N; ++i){
int L = i - l[i - 1];
int R = i + r[i] - M;
if(L <= R){
++pos[L];
--pos[R + 1];
}
}
int ans = 0, ri = 0;
for(int i = 1; i <= N; ++i){
pos[i] += pos[i - 1];
}
for(int i = 1; i <= N; ++i){
if(pos[i]) la[i] = i;
else la[i] = la[i - 1];
}
while(ri != N){
if(la[ri + 1] == 0 || la[ri + 1] + M - 1 == ri) return -1;
ri = la[ri + 1] + M - 1;
ans++;
}
return ans;
}
