#include "paint.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
const int Log = 20;
vector<int> Lov[N];
int R[N], L[N], ps[N];
int minimumInstructions(int n, int m, int k, vector<int> C, vector<int> A, vector<vector<int>> B){
memset(R, 0, sizeof R);
memset(L, 0, sizeof L);
memset(ps, 0, sizeof ps);
for(int i = 0; i < m; i++){
assert(A[i] == (int) B[i].size());
for(auto x : B[i]){
Lov[x].pb(i);
}
}
int col;
for(int i = 0; i < n; i++){
col = C[i];
assert(col < k);
for(auto &x : Lov[col]){
if(x <= i && R[i - x] == x) R[i - x] ++;
}
}
for(int i = n - 1; i >= 0; i--){
col = C[i];
for(auto &x : Lov[col]){
if((m - 1 - x) <= n - 1 - i && L[i + (m - 1 - x) + 1] == (m - 1 - x)) L[i + (m - 1 - x) + 1] ++;
}
}
/*
map<pii, int> mp;
for(int i = 0; i < m; i++){
assert(A[i] == (int) B[i].size());
for(auto x : B[i]){
Lov[x].pb(i);
}
}
*/
int ls, rs;
for(int i = 0; i <= n; i++){
if(L[i] + R[i] < m) continue;
ls = i - L[i];
rs = ls + ((R[i] + L[i]) - m);
rs = min(rs, n);
ls = max(ls, 0);
ps[ls] ++;
ps[rs + 1] --;
}
for(int i = 1; i <= n; i++) ps[i] += ps[i - 1];
/*
vector<int> pos;
for(int i = 0; i < n; i++){
if(i + m <= n && ps[i] > 0)
pos.pb(i);
}
*/
int laa = -1, la = 0, ans = 0;
while(la < n){
bool flg = false;
for(int i = la; i > laa; i--){
if(i + m <= n && ps[i] > 0){
laa = la;
la = i + m;
flg = true;
break;
}
}
if(flg) ans ++;
else return -1;
}
return ans;
}
/*
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4
5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3
*/
