#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 <vector <int>> likers (K);
for(int i = 0; i < M; i++)
for(int j = 0; j < A[i]; j++)
likers[B[i][j]].push_back(i);
function <bool (int, int)> likes = [&] (int worker, int color)
{
int l = 0, r = A[worker];
while(l < r)
{
int mid = (l + r) / 2;
if(B[worker][mid] < color)
l = mid + 1;
else
r = mid;
}
return (l < A[worker] && B[worker][l] == color);
};
vector <bool> possible (N - M + 1);
for(int l = 0; l + M - 1 < N; l++)
{
int t = rngSeg(l, M);
for(int it = 1; it <= 100; it++)
{
int cand = rngSeg(l, M);
if((int) likers[C[cand]].size() < (int) likers[C[t]].size())
t = cand;
}
possible[l] = false;
for(int x : likers[C[t]])
{
int p = x - (t - l);
if(p < 0)
p += M;
if(p >= M)
continue;
bool match = true;
for(int i = 0; i < M; i++)
if(likes((i + p) % M, C[l + i]) == false)
match = false;
if(match == true)
{
possible[l] = true;
break;
}
}
}
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];
}
