#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define vt vector
#define F first
#define S second
#define pii pair<ll,ll>
#define pb push_back
int subtask1(int n, int m, vt<int> &C, vt<ll> &pos){
for (int i=1;i<n;i++){
int a = pos[C[i-1]];
int b = pos[C[i]];
if (a == m-1) {
if (b != 0) return -1;
} else {
if (b != a+1) return -1;
}
}
return (n+m-1)/m;
}
bool valid(int i, int j, int m){
return (i+1)%m == j;
}
// returns if there is i,j in L,R such that valid(i,j) = true
// aka, can we go from C[i] to C[j]
// O(|L| log (|R|))
bool ok(set<ll> &L, set<ll> &R, ll m){
for (auto x: L){
int y = (x+1)%m;
if (R.count(y)) return true;
}
return false;
}
vt<pii> runlen(vt<bool> a){
vt<pii> res;
ll cnt=1, last = a[0];
for (int i=1;i<a.size();i++){
if (a[i] == last) cnt++;
else {
res.pb({last, cnt});
cnt = 1;
last = a[i];
}
}
res.pb({last, cnt});
return res;
}
int minimumInstructions(int n, int m, int k, vt<int> C, vt<int> A, vt<vt<int>> B){
bool s1=true;
vt<ll> fpos(k, -1);
vt<set<ll>> pos(k);
for (int i=0;i<m;i++){
for (auto x: B[i]){
if (fpos[x] != -1) s1 = false;
fpos[x] = i;
pos[x].insert(i);
}
}
if (s1) return subtask1(n, m, C, fpos);
// window movement
vt<bool> V;
for (ll i=0;i+1<n;i++){
auto sa = pos[C[i]];
auto sb = pos[C[i+1]];
bool flag = ok(sa, sb, m);
V.pb(flag);
}
vt<pii> r = runlen(V);
if (r.back().F == r[0].F && sz(r) > 1){
r[0].S += r.back().S;
r.pop_back();
}
ll cnt=0;
for (auto [x,c]: r){
// cout << x << " " << c << endl;
int cc = c+1;
if (x == 0 && cc>= m) return -1;
if (x==1) cnt += (cc+m-1)/m;
}
return cnt;
}
