/*
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);
}
}
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 (i+M > N) continue;
bool can = false;
for (int j : color_contractor[C[i]]) {
int c = ((j-i)%M+M)%M;
can |= (upper_bound(cell[c].begin(), cell[c].end(), i+M) - upper_bound(cell[c].begin(), cell[c].end(), i) == M);
}
if (can) {
while (!dt.empty() && dt.back().second >= dp[i]) dt.pop_back();
dt.emplace_back(i, dp[i]);
}
}
return (dp[N] == INF ? -1 : dp[N]);
}
