#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
long long a[n],left[n],right[n];
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<m;i++){
int l,r,k;
cin>>l>>r>>k;
left[0]=0;
for(int i=1;i<n;i++)
{
if(a[i]==a[i-1])
left[i]=left[i-1]; // bug was here....
else
left[i]=i;
}
right[n-1]=n-1;
for(int i=n-2;i>=0;i--)
{
if(a[i]==a[i+1])
right[i]=right[i+1]; // bug was here
else
right[i]=i;
}
for(int i=0;i<n;i++)
cout<<left[i]<<" "; //left array
cout<<endl;
for(int i=0;i<n;i++)
cout<<right[i]<<" "; //right array
int mid=(l+r)/2;
// Your code is incomplete... You must include some condition to check if right[mid]>R or left[mid]<L or not.
if((right[mid]-left[mid]+1)>=k) // you must include the middle number. that's why add 1 to count
cout<<a[mid]<<endl;
else
cout<<-1<<endl;
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBtYWluKCkgewppbnQgbixtOwpjaW4+Pm4+Pm07CmxvbmcgbG9uZyBhW25dLGxlZnRbbl0scmlnaHRbbl07CmZvcihpbnQgaT0wO2k8bjtpKyspCmNpbj4+YVtpXTsKZm9yKGludCBpPTA7aTxtO2krKyl7CiAgICBpbnQgbCxyLGs7CiAgICBjaW4+Pmw+PnI+Pms7CgogICAgbGVmdFswXT0wOwogICAgZm9yKGludCBpPTE7aTxuO2krKykKICAgIHsKICAgICAgICBpZihhW2ldPT1hW2ktMV0pCiAgICAgICAgbGVmdFtpXT1sZWZ0W2ktMV07IC8vIGJ1ZyB3YXMgaGVyZS4uLi4KICAgICAgICBlbHNlCiAgICAgICAgbGVmdFtpXT1pOwogICAgfQogICAgcmlnaHRbbi0xXT1uLTE7CiAgICBmb3IoaW50IGk9bi0yO2k+PTA7aS0tKQogICAgewogICAgICAgIGlmKGFbaV09PWFbaSsxXSkKICAgICAgICByaWdodFtpXT1yaWdodFtpKzFdOyAvLyBidWcgd2FzIGhlcmUKICAgICAgICBlbHNlCiAgICAgICAgcmlnaHRbaV09aTsKICAgIH0KICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiAgICBjb3V0PDxsZWZ0W2ldPDwiICI7ICAgIC8vbGVmdCBhcnJheQogICAgY291dDw8ZW5kbDsKICAgICBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgY291dDw8cmlnaHRbaV08PCIgIjsgICAvL3JpZ2h0IGFycmF5CiAgICBpbnQgIG1pZD0obCtyKS8yOwogICAgLy8gWW91ciBjb2RlIGlzIGluY29tcGxldGUuLi4gWW91IG11c3QgaW5jbHVkZSBzb21lIGNvbmRpdGlvbiB0byBjaGVjayBpZiByaWdodFttaWRdPlIgb3IgbGVmdFttaWRdPEwgb3Igbm90LgogICBpZigocmlnaHRbbWlkXS1sZWZ0W21pZF0rMSk+PWspICAgIC8vIHlvdSBtdXN0IGluY2x1ZGUgdGhlIG1pZGRsZSBudW1iZXIuIHRoYXQncyB3aHkgYWRkIDEgdG8gY291bnQKICAgIGNvdXQ8PGFbbWlkXTw8ZW5kbDsKICAgZWxzZQogICBjb3V0PDwtMTw8ZW5kbDsKfQp9Cg==