#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
int dd,ee,x,y,z,pre[100005],suf[100005];
vector<int> a,b;
vector<vector<int>>c;
deque<pair<int,int>>q;
bool cheq(int aa){
if(pre[aa]>=y) return 1;
for(int i=1;i<y;i++){
if(pre[aa+i]>=y-i and suf[aa+i-1]>=i) {
// cout<<aa+i<<endl;
return 1;
}
}
return 0;
}
void add(int aa,int bb){
while(!q.empty() and q.back().second>aa){
q.pop_back();
}
q.push_back({bb,aa});
}
int to(int aa){
while(!q.empty() and q.front().first+1<aa) {
q.pop_front();
}
if(q.empty()) return -1;
else return q.front().second;
}
int minimumInstructions(int xx,int yy,int zz, vector<int>aa,vector<int>bb,vector<vector<int>>cc){
x=xx;
y=yy;
z=zz;
for(int i=0;i<x;i++) a.push_back(aa[i]);
for(int i=0;i<y;i++){
b.push_back(bb[i]);
c.push_back(cc[i]);
}
int dp[100005];
bool cado=0;
for(int i=0;i<x;i++){
bool b1=0,b2=0;
pre[i]=0;
suf[i]=0;
for(int h=0;h<y;h++){
if(i+h<x and b1==0){
auto it=lower_bound(c[h].begin(),c[h].end(),a[i+h]);
if(*it==a[i+h])pre[i]++;
else {
// cout<<*it<<' '<<a[i+h]<<endl;
b1=1;
}
}
if(i-h>=0 and b2==0){
auto it=lower_bound(c[y-h-1].begin(),c[y-h-1].end(),a[i-h]);
if(*it==a[i-h])suf[i]++;
else b2=1;
}
if(b1 and b2) break;
}
// cout<<suf[i]<<' ';
}
// for(int i=0;i<x;i++) cout<<pre[i]<<' ';
// cout<<endl;
// for(int i=0;i<x;i++) cout<<suf[i]<<' ';
// cout<<endl;
if(cheq(0)==0){
return -1;
}
else{
add(1,y-1);
}
// cout<<endl;
// for(int i=0;i<=x-y;i++){
// cout<<cheq(i);
// }
// cout<<endl;
for(int i=1;i<=x-y;i++){
// cout<<i<<' ';
if(cheq(i)==1){
// cout<<i<<' '<<pre[i]<<' '<<suf[i-1]<<endl;
int ad=to(i);
if(ad==-1) return -1;
add(ad+1,i+y-1);
}
}
while(!q.empty()){
if(q.front().first!=x-1) q.pop_front();
else break;
}
if(q.empty()) return -1;
return q.front().second;
}
