#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
int minimumInstructions(int n, int m, int k, vi c, vi a, vector<vi> b) {
int ans = 1;
vi num(m);
vector<vi> con(k);
FOR(i, 0, m){
FOR(j, 0, a[i]){
con[b[i][j]].push_back(i);
}
}
FOR(i, 0, m){
for (int k : con[c[i]]){
num[(k-i+m)%m]++;
}
}
int cnt = 0;
FOR(i, 0, m){
if (num[i] == m) cnt++;
}
vi check(n);
if (cnt > 0) check[0] = 1;
FOR(i, 0, n-m){
for (int k : con[c[i]]){
k = (k - i + m) % m;
if (num[k] == m) cnt--;
num[k]--;
}
for (int k : con[c[i+m]]){
k = (k - i + m) % m;
if (num[k] == m-1) cnt++;
num[k]++;
}
if (cnt > 0) check[i+1] = 1;
}
bool sol = true;
int cur = 0;
while (cur < n-m){
if (check[cur] != 1){
sol = false; break;
}
ans++;
int r = -1;
ROF(i, cur + m, cur+1){
if (check[i] == 1){
r = i;
break;
}
}
if (r == -1){
sol = false; break;
}
cur = r;
}
if (!sol) return -1;
return ans;
}
