/*
We just need to check for each length K segment whether there exist a way to color them or not.
*/
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2")
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = (int)1e9;
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
vector<int> color_contractor[K];
for (int i = 0; i < M; i++) {
for (int j : B[i]) {
color_contractor[j].push_back(i);
}
}
vector<int> cell[M];
for (int i = 0; i < N; i++) {
for (int j : color_contractor[C[i]]) {
cell[((j-i)%M+M)%M].push_back(i+1);
}
}
bool can[N+1];
fill(can, can+N+1, false);
for (int j = 0; j < M; j++) {
if (cell[j].empty()) continue;
int l = 0, r = 0;
for (int i = 0; i+M <= N; i++) {
while (l < cell[j].size() && cell[j][l] <= i) l++;
while (r < cell[j].size() && cell[j][r] <= i+M) r++;
if (r-l == M) can[i] = true;
}
}
int dp[N+1];
fill(dp, dp+N+1, INF);
dp[0] = 0;
deque<pair<int, int>> dt;
for (int i = 0; i <= N; i++) {
while (!dt.empty() && i-dt.front().first > M) dt.pop_front();
if (!dt.empty()) dp[i] = dt.front().second+1;
if (can[i]) {
while (!dt.empty() && dt.back().second >= dp[i]) dt.pop_back();
dt.emplace_back(i, dp[i]);
}
}
return (dp[N] >= INF ? -1 : dp[N]);
}
