#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vc vector
typedef vc<ll> vcll;
typedef vc<bool> vcb;
#define pr pair
typedef pr<ll,ll> prll;
#define fi first
#define se second
#define sz size
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define all(x) ((x).begin()), ((x).end())
#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)
inline void maxa (ll &a, ll b) { if (a<b) a=b; }
inline void mina (ll &a, ll b) { if (a>b) a=b; }
#define mxN (100'010ll)
#define mxM (50'010ll)
#define mxK (100'010ll)
#define INF (LLONG_MAX>>3ll)
ll n, m, k;
vcll ar(mxN);
vc<vc<int>> B;
vc<vcll> cl_needs(mxN);
vc<vcll> pl_needs(mxN);
vcll temp_fr(mxK,0);
inline ll modit (ll x) { return ((x%m)+m)%m; }
vcll fr(mxK,0);
ll good_cnt;
inline void push (ll i)
{
for (ll r:pl_needs[i])
if (++fr[r]==m) good_cnt++;
}
inline void pull (ll i)
{
for (ll r:pl_needs[i])
if (fr[r]--==m) good_cnt--;
}
vcb can_paint(mxN);
vcll dp(mxN,INF);
struct MINQ
{
ll push_time, pop_time;
deque<prll> q;
inline MINQ()
{
push_time=0;
pop_time=0;
while (q.sz()) q.ppb();
q.pb({INF,0});
}
inline void push (ll x)
{
while (q.sz() and x<q.back().fi) q.ppb();
q.pb({x,++push_time});
// printf("pushed {%lli, %lli}\n", x, push_time);
}
inline void pop () { if (q.sz() and q.front().se == ++pop_time)
{
// printf("popping {%lli, %lli}\n", q.front().fi, q.front().se);
q.ppf();
}
}
inline ll min() { return q.front().fi; }
} minq;
inline void do_dp()
{
dp[0]=0;
ll i;
f0r(i,0,m-1) minq.push(dp[i]);
// printf("dp[1]: %lli\n", dp[1]);
f0r(i,m,n)
{
/*
printf("i: %lli\n", i);
if (can_paint[i])
{
printf("%lli is good, minq.min(): %lli\n", i, minq.min());
}
*/
dp[i] = can_paint[i] ? minq.min()+1 : INF;
minq.push(dp[i]);
// printf("pushinggggggggggggggg\n");
minq.pop();
// printf("poppinnnnnnnnnnnnnnn\n");
}
// f0r(i,1,n) printf("dp[%lli]: %lli\n", i, dp[i]);
}
inline bool isin (ll x, vc<int> &a)
{
// printf("a.sz(): %lli\n", (ll)a.sz());
for (ll v:a) if (x==v) return 1;
return 0;
}
inline bool colaei (ll i, ll r)
{
// printf("kollaei to %lli, %lli?\n", i, r);
ll j=i;
f0r(i,j-m+1,j)
{
// printf("i: %lli, i-j+m: %lli\n", i, i-j+m);
// printf("B[%lli].sz(): %lli\n", i-j+m, (ll)B[i-j+m-1].sz());
if (!isin(ar[i],B[modit(i-j+m-1+r)])) return 0;
// printf("saw if its in\n");
}
return 1;
}
inline bool bd_can_paint (ll i)
{
// printf("trying to paint %lli\n", i);
ll r;
f0r(r,0,m-1) if (colaei(i,r)) return 1;
return 0;
}
int minimumInstructions( int N, int M, int K, vc<int> C, vc<int> A, vc<vc<int>> bar)
{
n=N; m=M; k=K;
swap(B,bar);
ll i, j;
f0r(i,1,n) ar[i]=C[i-1];
// printf("pre paint\n");
f0r(i,m,n) can_paint[i]=bd_can_paint(i);
// printf("after paint\n");
// f0r(i,1,n) printf("can_paint[%lli]: %lli\n", i, (ll)can_paint[i]);
do_dp();
// printf("done\n");
// printf("n: %lli, dp[n]: %lli\n", n, dp[n]);
return dp[n]==INF ? -1 : dp[n];
}
