#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 69;
int seg[4 * N];
void upd(int l, int r, int pos, int qp, int v){
if (l == r){
seg[pos] = v;
return;
}
int mid = (l + r)/2;
if (qp <= mid) upd(l, mid, pos*2, qp, v);
else upd(mid + 1, r, pos*2 + 1, qp, v);
seg[pos] = min(seg[pos * 2], seg[pos * 2 + 1]);
}
int query(int l, int r, int pos, int ql, int qr){
if (l >= ql && r <= qr) return seg[pos];
else if (l > qr || r < ql) return 1e8;
int mid = (l + r)/2;
return min(query(l, mid, pos*2, ql, qr), query(mid + 1, r, pos*2 + 1, ql, qr));
}
int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
vector<vector<int>> adj(k);
for (int i = 0; i < m; i++){
for (auto x : b[i]){
adj[x].push_back(i);
}
}
//adj[x] size is atmost sqrt(4e5) = 650
vector<bool> can(n + 1, false);
map <int, int> mp;
for (int i = 0; i < n; i++){
//if painter x can do y, then increase frequency of x - y mod m ofc
//then a thing can be done if and only if frequency = m
int y = c[i];
if (i >= m){
for (auto x : adj[c[i - m]]){
int lol = (x - i) % m;
lol = (lol + m) % m;
// cout << "SUB " << i - m << " " << " COLOUR " << c[i - m] << " PAINTER " << x << " DIFF " << lol << "\n";
mp[lol]--;
}
}
for (auto x : adj[y]){
int lol = (x - i) % m;
lol = (lol + m) % m;
// cout << "ADD " << i << " " << " COLOUR " << y << " PAINTER " << x << " DIFF " << lol << "\n";
mp[lol]++;
if (mp[lol] == m) {
// cout << "NOOOO\n";
can[i + 1] = true;
}
}
}
vector <int> dp(n + 1, 1e8);
dp[0] = 0;
for (int i = 0; i <= n; i++) upd(0, n, 1, i, dp[i]);
for (int i = 1; i <= n; i++){
if (can[i]){
dp[i] = min(dp[i], 1 + query(0, n, 1, i - m, i - 1));
}
upd(0, n, 1, i, dp[i]);
}
if (dp[n] > n) return -1;
else return dp[n];
}
