#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
int segment_tree[800020];
vector<int> color[100002],possible1;
int Total[100002]={0};
int possible_place[100002]={0};
int query(int L,int R,int qL,int qR,int id){
if(qL==L && qR==R) return segment_tree[id];
int M=(L+R)/2;
if(qL>M) return query(M+1,R,qL,qR,2*id+1);
else if(qR<=M) return query(L,M,qL,qR,2*id);
else return max(query(L,M,qL,M,2*id),query(M+1,R,M+1,qR,2*id+1));
}
void modify(int L,int R,int place,int new_num,int id){
//cout<<L<<" "<<R<<endl;
if(L==R){
segment_tree[id]=new_num;
return;
}
int M=(L+R)/2;
if(place>M) modify(M+1,R,place,new_num,2*id+1);
else if(place<=M) modify(L,M,place,new_num,2*id);
segment_tree[id]=max(segment_tree[2*id],segment_tree[2*id+1]);
}
int cal_answer(int M,vector<int> possible){
if(!possible[M-1]) return -1;
int bound = M-1;
int answer = 1;
while(bound<(int)possible.size()-1){
//cout << bound << " ";
int flag = 0;
for(int i=bound+M;i>bound;i--){
if(possible[i]){
bound = i;
answer +=1;
flag = 1;
break;
}
}
if(!flag){
answer = -1;
break;
}
}
return answer;
}
int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) {
for(int i=1;i<800020;i++){
segment_tree[i]=0;
}
for(int i=0;i<(int)B.size();i++){
for(int j=0;j<(int)B[i].size();j++){
color[B[i][j]].push_back(i);
}
}
for(int i=0;i<N;i++){
for(int j:color[C[i]]){
if(color[C[i]].size()>=1000) return -100000;
// j worker
int active = (j + M - (i%M))%M;
Total[active]++;
modify(1,200002,active+1,Total[active],1);
}
if(i>=M){
for(int j:color[C[i-M]]){
int active = (j + M - (i%M))%M;
Total[active]--;
modify(1,200002,active+1,Total[active],1);
}
}
if(query(1,200002,1,200002,1)==M) possible_place[i]=1;
//for(int j=0;j<3;j++) cout << Total[j] << " ";
//cout << "\n";
}
for(int i=0;i<N;i++) possible1.push_back(possible_place[i]);
//possible1 = {0,0,1,1,0,0,1,0,1};
//for(int i=0;i<8;i++) cout << possible_place[i] << " ";
return cal_answer(M,possible1);
}
