#include "paint.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int min(int x, int y){
if (x < y) return x;
return y;
}
struct Segtree{
vector<int> tree;
int N;
Segtree(int n){
while (__builtin_popcount(n) != 1) n++;
this->N = n;
tree.resize(2*N+10, 1e9);
}
void update(int v, int tl, int tr, int pos, int x){
// if (pos < tl || pos > tr) return;
if (tl == tr && tl == pos){
tree[v] = x;
return;
}
int mid = (tl+tr)/2;
if (pos <= mid) update(2*v, tl, mid, pos, x);
else update(2*v+1, mid+1, tr, pos, x);
tree[v] = min(tree[v*2], tree[v*2+1]);
}
int query(int v, int tl, int tr, int l, int r){
if (l > tr || r < tl) return 1e9;
if (l <= tl && r >= tr) return tree[v];
int mid = (tl+tr)/2;
return min(query(v*2, tl, mid, l, r), query(v*2+1, mid+1, tr, l, r));
}
void u(int pos, int x){
update(1, 0, N-1, pos, x);
}
int q(int l, int r){
return query(1, 0, N-1, l, r);
}
};
void printVector(vector<int> a){
for (auto x: a) cout << x << " ";
cout << endl;
}
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>> colour(K+5);
for (int i = 0; i < N; ++i){
colour[C[i]].pb(i);
}
vector<vector<int>> o(N);
vector<int> f(K+5);
for (int i = 0; i < M; i++){
for (auto x: B[i]){
f[x]++;
for (auto item: colour[x]){
o[item].pb(i);
}
}
}
vector<int> dp1(M, -1), dp2(M, -1);
for (auto x: o[N-1]) dp2[x] = N-1;
vector<int> P(N+5);
if (M == 1){
if (f[C[N-1]] > 0) P[N-1] = 1;
}
// vector<int> there(M);
// for (auto x: o[N-1]) there[]
for (int i = N-2; i >= 0; i--){
for (auto x: o[i]){
if (dp2[(x+1)%M] >= 0) dp1[x] = dp2[(x+1)%M];
else dp1[x] = i;
if (dp1[x] - i >= M-1) P[i] = 1;
}
swap(dp1, dp2);
for (auto x: o[i+1]) dp1[x] = -1;
}
int ans = 0;
vector<int> dp(N+5, 1e9);
Segtree seg(N+1);
seg.u(N, 0);
for (int i = N-1; i >= 0; i--){
if (N-i >= M){
// cout << i << endl;
if (P[i] == 1){
int o = 1e9;
dp[i] = 1+seg.q(i+1, i+M);
seg.u(i, dp[i]);
}
}
}
// printVector(P);
// printVector(dp);
if (dp[0] < 1e9) return dp[0];
return -1;
}
