// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int INF = 1'000'000'007;
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
int jmp_back[100005];
vi colors[100005];
vector<bool> possible, added;
possible.assign(N, 0);
added.resize(2 * M);
const int n = N, m = M;
rep(i, 0, m) trav(color, B[i]) colors[color].pb(i);
rep(i,0,K)colors[i].pb(INF);
for (int pos = m - 1; pos < n; pos += m) {
int cur_color = C[pos];
trav(person, colors[cur_color]) {
int first_person = (person + 1) % m, num_match = 0;
int start_pos = pos - m + 1;
rep(i, 0, m - 1) {
added[i] = *lower_bound(all(colors[C[start_pos + i]]), (first_person + i) % m) == (first_person + i) % m;
num_match += added[i];
}
rep(i, m - 1, m - 1 + min(m, (n - pos))) {
added[i] = *lower_bound(all(colors[C[start_pos + m - 1]]), (first_person - 1 + m) % m)==(first_person - 1 + m) % m;
num_match += added[i];
if (num_match == m) possible[start_pos] = 1;
num_match -= added[i - m + 1];
first_person = (first_person + 1) % m;
++start_pos;
}
}
}
int val = -INF;
rep(i, 0, n) {
if (possible[i]) val = i;
jmp_back[i] = val;
}
int pos = 0, ans = 0;
while (pos < n) {
int nxt_pos = jmp_back[pos];
if (nxt_pos + m > pos) {
pos = nxt_pos + m;
++ans;
} else
return -1;
}
return ans;
}
/*
int main() {
int N, M, K;
assert(3 == scanf("%d %d %d", &N, &M, &K));
std::vector<int> C(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &C[i]));
}
std::vector<int> A(M);
std::vector<std::vector<int>> B(M);
for (int i = 0; i < M; ++i) {
assert(1 == scanf("%d", &A[i]));
B[i].resize(A[i]);
for (int j = 0; j < A[i]; ++j) {
assert(1 == scanf("%d", &B[i][j]));
}
}
int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
printf("%d\n", minimum_instructions);
return 0;
}*/
