#include <bits/stdc++.h>
//#include "paint.h"
using namespace std;
const int INF = INT_MAX / 2;
mt19937 rng(time(0));
int rngSeg (int l, int len)
{
return l + rng() % len;
}
int minimumInstructions(int N, int M, int K, vector <int> C, vector <int> A, vector <vector <int>> B)
{
vector <int> liker (K, -1);
for(int i = 0; i < M; i++)
for(int j = 0; j < A[i]; j++)
liker[B[i][j]] = i;
for(int i = 0; i < N; i++)
if(liker[C[i]] == -1)
return -1;
for(int i = 0; i < N; i++)
C[i] = liker[C[i]];
vector <int> magic (N - 1);
for(int i = 0; i < N - 1; i++)
{
int diff = C[i + 1] - C[i];
magic[i] = (diff == 1 || diff == 1 - M);
}
for(int i = 1; i < N - 1; i++)
magic[i] += magic[i - 1];
vector <bool> possible (N - M + 1);
for(int l = 0; l + M - 1 < N; l++)
{
int seg = magic[l + M - 2];
if(l > 0)
seg -= magic[l - 1];
possible[l] = (seg == M - 1);
}
vector <int> minPref (N, INF);
deque <int> dq;
minPref[M - 1] = INF;
if(possible[0] == true)
minPref[M - 1] = 1;
for(int i = M; i < N; i++)
{
if(dq.empty() == false && dq.front() < i - M)
dq.pop_front();
while(dq.empty() == false && minPref[i - 1] <= minPref[dq.back()])
dq.pop_back();
dq.push_back(i - 1);
if(possible[i - M + 1] == true)
{
if(minPref[dq.front()] != INF)
minPref[i] = minPref[dq.front()] + 1;
}
}
if(minPref[N - 1] == INF)
return -1;
return minPref[N - 1];
}
