#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e5 + 5;
vector<int> good[Nmax];
int nr = 0, n, m;
int shift[Nmax];
bool ok[Nmax];
int dp[Nmax];
void upd(int pos, int add)
{
nr -= (shift[pos] == m);
shift[pos] += add;
nr += (shift[pos] == m);
}
int minimumInstructions(int N, int M, int k, vector<int> c, vector<int> A, vector<vector<int>> B)
{
n = N; m = M;
int i, j;
for(i=0; i<m; ++i)
for(auto it : B[i])
good[it].push_back(i);
for(i=0; i<m; ++i)
for(auto it : good[c[i]])
upd((it - i%m + m) % m, +1);
if(nr) ok[m-1] = 1;
for(i=m; i<n; ++i)
{
for(auto it : good[c[i]])
upd((it - i%m + m) % m, +1);
for(auto it : good[c[i-m]])
upd((it - i%m + m) % m, -1);
if(nr) ok[i] = 1;
}
if(!ok[m-1] || !ok[n-1]) return -1;
dp[m-1] = 1;
for(i=m; i<n; ++i)
{
for(j=i-m; j<i; ++j)
if(ok[j])
{
dp[i] = dp[j] + 1;
break;
}
if(!dp[i]) return -1;
}
return dp[n-1];
}
