#ifndef LOCAL
#include "paint.h"
#endif
#include <vector>
template <class T>
using Vec = std::vector<T>;
int rem_euclid(int x, const int y) {
x %= y;
return x < 0 ? x + y : x;
}
int minimumInstructions(int N, int M, int K, Vec<int> C, Vec<int>, Vec<Vec<int>> B) {
Vec<Vec<int>> store(K);
for (int i = 0; i < M; ++i) {
for (const auto c: B[i]) {
store[c].push_back(i);
}
}
Vec<Vec<int>> appear(M);
for (int i = 0; i < N; ++i) {
for (const auto j: store[C[i]]) {
appear[rem_euclid(j - i, M)].push_back(i);
}
}
Vec<int> max_right(N);
for (const auto &vec: appear) {
int last = N + 1;
int to_right = 0;
for (int i = (int) vec.size() - 1; i >= 0; --i) {
const auto k = vec[i];
if (k + 1 != last) {
to_right = 0;
}
to_right += 1;
max_right[k] = to_right;
last = k;
}
}
Vec<int> paint;
for (int i = 0; i < N; ++i) {
if (max_right[i] >= M) {
paint.push_back(i);
}
}
int ret = 0;
int right = 0;
int idx = 0;
while (right < N) {
while (idx < (int) paint.size() && paint[idx] <= right) {
idx += 1;
}
if (idx == 0) {
return -1;
}
const auto left = paint[idx - 1];
if (left + M <= right) {
return -1;
}
ret += 1;
right = left + M;
}
return ret;
}
#ifdef LOCAL
int main() {
return 0;
}
#endif
