#include "paint.h"
//<TEMP>
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define F first
#define S second
using namespace std;
//</TEMP>
//OP
struct commands {
const int inf = 1e9;
int n;
int m;
int k;
int cur;
vector<int> C;
vector<int> A;
vector<int> mn;
vector<int> ans;
vector<vector<int>> B;
vector<pair<int, int>> v;
vector<pair<int, int>> go[200005];
void set(int _N, int _M, int _K, vector<int> _C, vector<int> _A, vector<vector<int>> _B) {
n = _N; m = _M; k = _K; C = _C; A = _A; B = _B;
mn.resize(200005); ans.resize(200005);
for (int i = 0; i < m; i++) for (auto j: B[i]) go[j].pb({i, 0});
}
int get(int x) {
while (v.size() >= 2 && v[v.size()-2].F >= x) v.pop_back();
return (v.back().F >= x ? v.back().S : inf);
}
int answer() {
cur = 0; v.pb({-1, 0}); ans[0] = -1;
for (int i = 0; i < n; i++) {
for (auto &j: go[C[i]]) {
j.S = (mn[j.F] != inf ? mn[j.F] : i);
if (i - j.S + 1 >= m) {
int x = get(i - m); if (x == inf) continue;
ans[x + 1] = i; v.pb({i, x + 1}); cur = x + 1;
}
}
if (i) for (auto j: go[C[i-1]]) mn[(j.F + 1) % m] = inf;
for (auto j: go[C[i]]) mn[(j.F + 1) % m] = min(mn[(j.F + 1) % m], j.S);
}
return (ans[cur] < n - 1 ? -1 : cur);
}
} cmd;
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
cmd.set(N, M, K, C, A, B);
return cmd.answer();
}
//ED
