#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
using ll = long long;
const int N1 = 20200;
const int M1 = 2020;
int n, m;
int g[N1][M1];
int f[N1][M1];
void precalc() {
for (int j = 0; j < m; j++) {
int x = n - 1, y = j;
while (g[x][y] && f[n - 1][j] < m) {
f[n - 1][j]++;
x = (x + 1) % n;
y = (y + 1) % m;
}
}
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j < m; j++) {
if (g[i][j]) f[i][j] = 1 + f[i + 1][(j + 1) % m];
else f[i][j] = 0;
}
}
}
const int N = 100100;
int to[N][18];
int dt[N][18];
int minimumInstructions(
int N, int M, int K, vector<int> C,
vector<int> A, vector<vector<int>> B) {
n = N,
m = M;
bool able[n] = {};
if (n < N1 && m < M1) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int x = lower_bound(B[j].begin(), B[j].end(), C[i]) - B[j].begin();
g[i][j] = (x != A[j] && B[j][x] == C[i]);
}
}
precalc();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
able[i] |= (f[i][j] >= m);
}
} else {
bool used[K + 1] = {};
for (int i = 0; i < m; i++) {
for (int j = 0; j < A[i]; j++) {
used[B[i][j]] = true;
}
}
int cnt = 0;
map<int, int> mp;
for (int i = 0; i < m; i++) {
mp[C[i]]++;
cnt += used[i];
}
for (int i = 0; i < n; i++) {
able[i] = ((int)mp.size() == m && cnt == m);
cnt -= used[C[i]];
cnt += used[C[(i + m) % n]];
mp[C[i]]--;
mp[C[(i + m) % n]]++;
if (!mp[C[i]]) mp.erase(C[i]);
}
}
{
int st = 0;
while (st < n && !able[st]) st++;
if (st == n) return -1;
if (m == n)
return 1;
int nxt = 0, w = 0;
for (int i = 0; i < n; i++) {
if (able[(i + st) % n]) {
nxt = (i + st + m) % n;
w = 0;
}
if (w >= m) nxt = (st + i) % n;
to[(i + st) % n][0] = nxt;
dt[(i + st) % n][0] = (nxt - st - i + 2 * n) % n;
w++;
}
}
for (int k = 1; k < 18; k++) {
for (int i = 0; i < n; i++) {
to[i][k] = to[to[i][k - 1]][k - 1];
dt[i][k] = dt[i][k - 1] + dt[to[i][k - 1]][k - 1];
}
}
int res = 1e9;
for (int i = 0; i < n; i++) {
int x = i;
int ans = 0;
int dist = 0;
for (int k = 17; k >= 0; k--) {
if (dist + dt[x][k] < n) {
ans += (1 << k);
dist += dt[x][k];
x = to[x][k];
}
}
if (dist + dt[x][0] >= n)
res = min(res, ans + 1);
}
if (res == 1e9) return -1;
return res;
}
