Contest 23

contest

A 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define fi first
#define se seconde
#define pb push_back()
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
ll k,n,ans;
int main(){
    cin>>n>>k;
    if(!k){
        cout<<n*n<<endl;
        return 0;
    }
    rep(i,k+1,n){
        ans+=(n/(ll)i*((ll)i-k));
        if(n%i){
            ans+=max(0ll,n%i-k+1);
        }
    }
    cout<<ans<<endl;
    return 0;
}

B b756256

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
bool vis[N];
int main() {
    string s;
    cin >> s;
    stack<int>st;
    int ls=s.size();
    for(int i=0;i<ls;i++) {
        if(s[i]=='(') st.push(i);
        else 
        if(!st.empty()) {
            vis[i] = true;
            vis[st.top()] = true;
            st.pop();
        }
    }
    int cnt = 0,ans = 0,sum = 0;
    for(int i=0;i<ls;i++) {
        if(vis[i]) cnt++;
        else cnt = 0;
        if(cnt == ans && ans) sum++;
        else if(cnt > ans) sum = 1,ans = cnt;
    }
    if(ans) printf("%d %d\n",ans,sum);
    else cout << "0 1" << endl; 
}

C djddskkekk

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 10;
int n , z , a [ maxn ] , sum;
int main ( void )
{
    cin >> n >> z;
    for ( int i = 0 ; i < n ; i++ ) cin >> a [ i ];
    sort ( a , a + n );
    int i = 0 , j = n / 2;
    while ( i < n / 2 && j < n ) {
        if ( abs ( a [ i ] - a [ j ] ) >= z ) {
            sum++; i++; j++;
        } else {
            j++;
        }
    }
    cout << sum << endl;
    return 0;
}

D djddskkekk

#include <iostream>
#include <vector>
using namespace std;
#define int long long
int a , b;
vector < int > s;
signed main ( void )
{
    cin >> a >> b;
    while ( a != b ) {
        while ( a % 2 == 0 ) {
            s.push_back ( 1 );
            a /= 2;
        }
        while ( b % 2 == 0 ) {
            s.push_back ( 2 );
            b /= 2;
        }
        if ( a == b ) break;
        if ( a < b ) {
            b += a;
            s.push_back ( 3 );
        } else {
            a += b;
            s.push_back ( 4 );
        }
    }
    cout << s.size ( ) << endl;
    for ( int i = 0 ; i < s.size ( ) ; i++ ) {
        if ( s [ i ] == 1 ) {
            cout << "B+=B" << endl;
        } else if ( s [ i ] == 2 ) {
            cout << "A+=A" << endl;
        } else if ( s [ i ] == 3 ) {
            cout << "B+=A" << endl;
        } else {
            cout << "A+=B" << endl;
        }
    }
    return 0;
}

E yingyingying777

import java.util.Scanner;
public class Main
{
    public static int n,m,x1,y1,x2,y2;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        x1=sc.nextInt();
        y1=sc.nextInt();
        x2=sc.nextInt();
        y2=sc.nextInt();
        int d_x=Math.abs(x1-x2);
        int d_y=Math.abs(y1-y2);
        if(d_x<=3&&d_y<=3)
            System.out.println("First");
        else if(d_x<=4&&d_y<=4)
        {
            if(d_x+d_y<=6)
                System.out.println("First");
            else
                System.out.println("Second");
        }
        else
            System.out.println("Second");
        sc.close();
    }
}

F djddskkekk

#include <iostream>
#include <vector>
using namespace std;
int n , ret;
vector < int > a;
int main ( void )
{
    cin >> n;
    a.push_back ( 1 );
    while ( 1 ) {
        ret = 0;
        for ( int i = a.size ( ) - 1 ; i >= 0 ; i-- ) {
            ret = ( ret * 10 + a [ i ] ) % n;
        }
        if ( ret == 0 ) {
            break;
        } else {
            int number = 0;
            a [ number ]++;
            while ( 1 ) {
                if ( a [ number ] > 1 ) {
                    if ( number + 1 >= a.size ( ) ) {
                        a.push_back ( 1 );
                        a [ number ] = 0;
                        break;
                    } else {
                        a [ number ] = 0;
                        a [ number + 1 ]++;
                        number++;
                    }
                } else {
                    break;
                }
            } 
        }
    }
    for ( int i = a.size ( ) - 1 ; i >= 0 ; i-- ) {
        cout << a [ i ]; 
    }
    cout << endl;
    return 0;
}

G likailin

#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define il inline
#define int long long
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define pi 3.14159265358979323
#define debug(x)              cout <<#x<<": "<<x<<endl;
#define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl;
#define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
const ll INF (0x3f3f3f3f3f3f3f3fll);
const int inf (0x3f3f3f3f);
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;}
ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;}
ll mult(ll a,ll b,ll p){a%=p;b%=p;ll r=0,v=a;while(b){if(b&1){r+=v;if(r>p)r-=p;}v<<=1;if(v>p)v-=p;b>>=1;}return r;}
ll quick_pow(ll a,ll b,ll p){ll r=1,v=a%p;while(b){if(b&1)r=mult(r,v,p);v=mult(v,v,p);b>>=1;}return r;}
bool CH(ll a,ll n,ll x,ll t)
{ll r=quick_pow(a,x,n);ll z=r;for(ll i=1;i<=t;i++){r=mult(r,r,n);if(r==1&&z!=1&&z!=n-1)return true;z=r;}return r!=1;}
bool Miller_Rabin(ll n)
{if(n<2)return false;if(n==2)return true;if(!(n&1))return false;ll x=n-1,t=0;while(!(x&1)){x>>=1;t++;}srand(time(NULL));
ll o=8;for(ll i=0;i<o;i++){ll a=rand()%(n-1)+1;if(CH(a,n,x,t))return false;}return true;}
void exgcd(ll a,ll b ,ll &x,ll &y){if(!b){x=1,y=0;return;}exgcd(b,a%b,x,y);ll t=x;x=y,y=t-(a/b)*y;}
ll inv(ll a,ll b){ll x,y;return exgcd(a,b,x,y),(x%b+b)%b;}
ll crt(ll x,ll p,ll mod){return inv(p/mod,mod)*(p/mod)*x;}
ll fac(ll x,ll a,ll b)
{if(!x)return 1;ll ans=1;for(ll i=1;i<=b;i++)if(i%a)ans*=i,ans%=b;
ans=pow_mod(ans,x/b,b);for(ll i=1;i<=x%b;i++)if(i%a)ans*=i,ans%=b;return ans*fac(x/a,a,b)%b;}
ll C(ll n,ll m,ll a,ll b)
{ll N=fac(n,a,b),M=fac(m,a,b),Z=fac(n-m,a,b),sum=0,i;for(i=n;i;i=i/a)sum+=i/a;
for(i=m;i;i=i/a)sum-=i/a;for(i=n-m;i;i=i/a)sum-=i/a;return N*pow_mod(a,sum,b)%b*inv(M,b)%b*inv(Z,b)%b;}
ll exlucas(ll n,ll m,ll p)
{ll t=p,ans=0,i;for(i=2;i*i<=p;i++){ll k=1;while(t%i==0){k*=i,t/=i;}
ans+=crt(C(n,m,i,k),p,k),ans%=p;}if(t>1)ans+=crt(C(n,m,t,t),p,t),ans%=p;return ans % p;}
/*
int prime[100000],minprime[100000];
void euler(int n)
{int c=0,i,j;for(i=2;i<=n;i++){if(!minprime[i])prime[++c]=i,minprime[i]=i;for(j=1;j<=c&&i*prime[j]<=n;j++)
{minprime[i*prime[j]]=prime[j];if(i%prime[j]==0)break;}}}
struct Tree{ll l,r,sum,lazy,maxn,minn;}tree[100000];
il void push_up(ll rt)
{tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
tree[rt].maxn=max(tree[rt<<1].maxn,tree[rt<<1|1].maxn);
tree[rt].minn=min(tree[rt<<1].minn,tree[rt<<1|1].minn);}
il void push_down(ll rt , ll length)
{if(tree[rt].lazy){tree[rt<<1].lazy+=tree[rt].lazy;tree[rt<<1|1].lazy+=tree[rt].lazy;
tree[rt<<1].sum+=(length-(length>>1))*tree[rt].lazy;tree[rt<<1|1].sum+=(length>>1)*tree[rt].lazy;
tree[rt<<1].minn+=tree[rt].lazy;tree[rt<<1|1].minn+=tree[rt].lazy;
tree[rt<<1].maxn+=tree[rt].lazy;tree[rt<<1|1].maxn+=tree[rt].lazy;tree[rt].lazy=0;}}
il void build(ll l , ll r , ll rt , ll *aa)
{tree[rt].lazy=0;tree[rt].l=l;tree[rt].r=r;if(l==r)
{tree[rt].sum=aa[l];tree[rt].minn=tree[rt].sum;tree[rt].maxn=tree[rt].sum;return;}
ll mid=(l+r)>>1;build(l,mid,rt<<1,aa);build(mid+1,r,rt<<1|1,aa);push_up(rt);}
il void update_range(ll L , ll R , ll key , ll rt)
{if(tree[rt].r<L||tree[rt].l>R)return;if(L<=tree[rt].l&&R>=tree[rt].r){tree[rt].sum+=(tree[rt].r-tree[rt].l+1)*key;
tree[rt].minn+=key;tree[rt].maxn+=key;tree[rt].lazy+=key;return;}push_down(rt,tree[rt].r-tree[rt].l+1);
ll mid=(tree[rt].r+tree[rt].l)>>1;if(L<=mid)update_range(L,R,key,rt << 1);
if(R>mid)update_range(L,R,key,rt << 1 | 1);push_up(rt);}
il ll query_range(ll L, ll R, ll rt)
{if(L<=tree[rt].l&&R>=tree[rt].r){return tree[rt].sum;}push_down(rt,tree[rt].r-tree[rt].l+1);
ll mid=(tree[rt].r+tree[rt].l)>>1;ll ans=0;if(L<=mid)ans+=query_range(L,R,rt << 1);
if(R>mid)ans+=query_range(L,R,rt << 1 | 1);return ans;}
il ll query_min(ll L,ll R,ll rt)
{if(L<=tree[rt].l&&R>=tree[rt].r){return tree[rt].minn;}push_down(rt,tree[rt].r-tree[rt].l+1);
ll mid=(tree[rt].r+tree[rt].l)>>1;ll ans=(0x3f3f3f3f3f3f3f3fll);if(L<=mid)ans=min(ans,query_min(L,R,rt << 1));
if(R>mid)ans=min(ans,query_min(L,R,rt << 1 | 1));return ans;}
il ll query_max(ll L, ll R, ll rt)
{if(L<=tree[rt].l&&R>=tree[rt].r){return tree[rt].maxn;}push_down(rt,tree[rt].r-tree[rt].l+1);
ll mid=(tree[rt].r+tree[rt].l)>>1;ll ans=-(0x3f3f3f3f3f3f3f3fll);if(L<=mid)ans=max(ans,query_max(L,R,rt << 1));
if(R>mid)ans=max(ans,query_max(L,R,rt << 1 | 1));return ans;}
*/
const int N = 2e5 + 10;
int dp[N];
signed main()
{
    ios;
    int n; cin>>n;
    int ans = 0;
    rep(i, 1, n){
        int x; cin >> x;
        int m = sqrt(x), ma = 0;
        vector<int> cur;
        rep(j, 2, m){
            while(x % j==0){
                ma = max(ma, dp[j]);
                cur.push_back(j);
                x /= j;
            }
        } 
        if(x > 1) ma = max(ma, dp[x]), cur.push_back(x);
        ma++;
        ans = max(ans, ma);
        for(auto c : cur) dp[c] = ma;
    }
    cout << ans << endl;
    return 0;
}

H 194115062039

#include<stdio.h>
#include<string.h>
int min(int a,int b){return a<b?a:b;}
int main()
{
    int pos[28],dis;
    int n;
    long long tot=0,dp[105][105],k;
    char ch[105];
    scanf("%d%lld",&n,&k);
    getchar();
    scanf("%s",ch+1);
    for(int i=0;i<105;i++)
    {
        for(int j=0;j<105;j++)dp[i][j]=0;
        dp[i][0]=1;
    }
    for(int i=0;i<28;i++)pos[i]=-1;
    /*
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=i+1;j++)
        {
            if(i>0)dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
            else dp[i][j]=1;
        }
    }*/
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            /*if(i>0&&j>0)dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
            else if(i==0)dp[i][j]=1;
            else if(j==0)dp[i][j]=1+dp[i-1][j];*/
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
            if(pos[ch[i]-'a']==-1)continue;
            //int cc=pos[ch[i]-'a'-1];
            dis=i-pos[ch[i]-'a'];
            if(dis<=j)dp[i][j]-=dp[pos[ch[i]-'a']-1][j-dis];
        }
        pos[ch[i]-'a']=i;
    }
    for(long long i=0;i<=n;i++)
    {
        if(k<=dp[n][i])
        {
            tot+=k*i;
            k=0;
            break;
        }
        tot+=dp[n][i]*i;
        k-=dp[n][i];
        if(k<=0)break;
    }
    if(k<=0)printf("%lld\n",tot);
    else printf("-1\n");
}

I djddskkekk

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 4e5 + 10;
int trie [ maxn << 5 ] [ 2 ] , cnt;
struct {
    void insert ( int n )
    {
        int m = 0;
        for ( int i = 30 ; i >= 0 ; i-- ) {
            int v = ( n >> i ) & 1;
            if ( trie [ m ] [ v ] == 0 ) {
                trie [ m ] [ v ] = ++cnt;
            }
            m = trie [ m ] [ v ];
        }
    }
    int dis ( int n )
    {
        int m = 0 , sum = 0;
        for ( int i = 30 ; i >= 0 ; i-- ) {
            int v = ( n >> i ) & 1;
            if ( trie [ m ] [ v ^ 1 ] == 0 ) sum <<= 1 , m = trie [ m ] [ v ];
            else sum = ( sum << 1 | 1 ) , m = trie [ m ] [ v ^ 1 ]; 
        }
        return sum;
    }
    void init ( ) 
    {
        memset ( trie , 0 , sizeof ( trie [ 0 ] ) * ( cnt + 1 ) );
        cnt = 0;
    }
} Tree;
int a [ maxn ] , number [ maxn ] , number_2 [ maxn ] , sum_1 [ maxn ] , sum_2 [ maxn ] , k;
int main ( void )
{
    ios::sync_with_stdio ( false ); cin.tie ( 0 ); cout.tie ( 0 );
    cin >> k; cnt = 0;
    for ( int i = 1 ; i <= k ; i++ ) {
        cin >> a [ i ];
        number [ i ] = number [ i - 1 ] ^ a [ i ];
    }
    for ( int i = k ; i >= 0 ; i-- ) {
        number_2 [ i ] = number_2 [ i + 1 ] ^ a [ i ];
    }
    Tree.init ( );
    for ( int i = k ; i >= 0 ; i-- ) {
        sum_1 [ i ] = max ( Tree.dis ( number [ i ] ) , sum_1 [ i + 1 ] );
        Tree.insert ( number [ i ] );
    }
    Tree.init ( );
    for ( int i = 1 ; i <= k + 1 ; i++ ) {
        sum_2 [ i ] = max ( Tree.dis ( number_2 [ i ] ) , sum_2 [ i - 1 ] );
        Tree.insert ( number_2 [ i ] );
    }
    long long ans = 0;
    for ( int i = 0 ; i <= k ; i++ ) {
        ans = max ( ans , ( long long ) sum_1 [ i ] + sum_2 [ i + 1 ] );
    }
    cout << ans << endl;
    return 0;
}

J 194115062039

#include<stdio.h>
int alphafs(int as,int bs);
int betafs(int as,int bs);
bool line[18];
int linecheck(int i)
{
    int total=0;
    if(i==0){line[0]=true;if(line[1]==true&&line[2]==true)total++;return total;}
    if(i==1){line[1]=true;if(line[0]==true&&line[2]==true)total++;return total;}
    if(i==2){line[2]=true;if(line[0]==true&&line[1]==true)total++;if(line[4]==true&&line[6]==true)total++;return total;}
    if(i==3){line[3]=true;if(line[4]==true&&line[5]==true)total++;return total;}
    if(i==4){line[4]=true;if(line[3]==true&&line[5]==true)total++;if(line[2]==true&&line[6]==true)total++;return total;}
    if(i==5){line[5]=true;if(line[3]==true&&line[4]==true)total++;if(line[10]==true&&line[12]==true)total++;return total;}
    if(i==6){line[6]=true;if(line[7]==true&&line[8]==true)total++;if(line[2]==true&&line[4]==true)total++;return total;}
    if(i==7){line[7]=true;if(line[6]==true&&line[8]==true)total++;return total;}
    if(i==8){line[8]=true;if(line[6]==true&&line[7]==true)total++;if(line[13]==true&&line[15]==true)total++;return total;}
    if(i==9){line[9]=true;if(line[10]==true&&line[11]==true)total++;return total;}
    if(i==10){line[10]=true;if(line[9]==true&&line[11]==true)total++;if(line[5]==true&&line[12]==true)total++;return total;}
    if(i==11){line[11]=true;if(line[9]==true&&line[10]==true)total++;return total;}
    if(i==12){line[12]=true;if(line[13]==true&&line[14]==true)total++;if(line[5]==true&&line[10]==true)total++;return total;}
    if(i==13){line[13]=true;if(line[12]==true&&line[14]==true)total++;if(line[8]==true&&line[15]==true)total++;return total;}
    if(i==14){line[14]=true;if(line[12]==true&&line[13]==true)total++;return total;}
    if(i==15){line[15]=true;if(line[16]==true&&line[17]==true)total++;if(line[8]==true&&line[13]==true)total++;return total;}
    if(i==16){line[16]=true;if(line[15]==true&&line[17]==true)total++;return total;}
    if(i==17){line[17]=true;if(line[15]==true&&line[16]==true)total++;return total;}
}
int transform(int a,int b)
{
    if(a==1&&b==2)return linecheck(0);
    if(a==1&&b==3)return linecheck(1);
    if(a==2&&b==3)return linecheck(2);
    if(a==2&&b==4)return linecheck(3);
    if(a==2&&b==5)return linecheck(4);
    if(a==4&&b==5)return linecheck(5);
    if(a==3&&b==5)return linecheck(6);
    if(a==3&&b==6)return linecheck(7);
    if(a==5&&b==6)return linecheck(8);
    if(a==4&&b==7)return linecheck(9);
    if(a==4&&b==8)return linecheck(10);
    if(a==7&&b==8)return linecheck(11);
    if(a==5&&b==8)return linecheck(12);
    if(a==5&&b==9)return linecheck(13);
    if(a==8&&b==9)return linecheck(14);
    if(a==6&&b==9)return linecheck(15);
    if(a==6&&b==10)return linecheck(16);
    if(a==9&&b==10)return linecheck(17);
}
int alphafs(int as,int bs)
{
    int score=0,v=0,flag=0;
    if(as>=5)return -1;
    if(bs>=5)return 1;
    for(int i=0;i<18;i++)
    {
        score=0;
        if(line[i]==false)score=linecheck(i);
        else continue;
        flag=1;
        if(score==0)v=betafs(as,bs);
        else v=alphafs(as+score,bs);
        line[i]=false;
        if(v<0)return -1;
    }
    if(flag==0&&bs>as)return 1;
    if(flag==0&&bs<as)return -1;
    return 1;
}
int betafs(int as,int bs)
{
    int score=0,v=0,flag=0;
    if(as>=5)return -1;
    if(bs>=5)return 1;
    for(int i=0;i<18;i++)
    {
        score=0;
        if(line[i]==false)score=linecheck(i);
        else continue;
        flag=1;
        if(score==0)v=alphafs(as,bs);
        else v=betafs(as,bs+score);
        line[i]=false;
        if(v>0)return 1;
    }
    if(flag==0&&bs>as)return 1;
    if(flag==0&&bs<as)return -1;
    return -1;
}
int main()
{
    int m,n,a,b,term=0,scorea=0,scoreb=0,score;
    scanf("%d",&m);
    for(int k=0;k<m;k++)
    {
        scorea=0;
        scoreb=0;
        term=0;
        for(int i=0;i<18;i++)line[i]=false;
        scanf("%d",&n);
        while(n--)
        {
            scanf("%d%d",&a,&b);
            score=transform(a,b);
            if(score==0)term=term^1;
            else
            {
                if(term==0)scorea+=score;
                else scoreb+=score;
            }
        }
        if(term==0)printf("Game %d: %c wins.\n",k+1,alphafs(scorea,scoreb)<0?'A':'B');
        else printf("Game %d: %c wins.\n",k+1,betafs(scorea,scoreb)<0?'A':'B');
    }
}

K djddskkekk

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 3e5 + 10;
int a [ maxn ] , b [ maxn ] , sum [ maxn << 5 ] , lc [ maxn << 5 ] , rc [ maxn << 5 ] , sz , p , n , m , q , rt [ maxn ] , w;
inline int read ( )
{
    register int s = 0 , t = 1; register char ch = getchar ( );
    while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) t = -1; ch = getchar ( ); }
    while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ( ); }
    return s * t;
}
void build ( int &rt , int l , int r )
{
    rt = ++sz; sum [ rt ] = 0;
    if ( l == r ) return;
    int mid = ( l + r ) >> 1;
    build ( lc [ rt ] , l , mid );
    build ( rc [ rt ] , mid + 1 , r );
}
int update ( int o , int l , int r )
{
    int oo = ++sz;
    lc [ oo ] = lc [ o ] , rc [ oo ] = rc [ o ] , sum [ oo ] = sum [ o ] + 1;
    if ( l == r ) return oo;
    int mid = ( l + r ) >> 1;
    if ( p <= mid ) lc [ oo ] = update ( lc [ o ] , l , mid ); 
    else rc [ oo ] = update ( rc [ o ] , mid + 1 , r );
    return oo;
}
int query ( int u , int v , int l , int r , int k )
{
    int mid = ( l + r ) >> 1;
    if ( l == r ) return b [ l ];
    int ans = 0;
    if ( sum [ lc [ v ] ] - sum [ lc [ u ] ] > k ) ans = query ( lc [ u ] , lc [ v ] , l , mid , k );
    if ( ans ) return ans;
    if ( sum [ rc [ v ] ] - sum [ rc [ u ] ] > k ) ans = query ( rc [ u ] , rc [ v ] , mid + 1 , r , k );
    return ans;
}
int main ( void )
{
    n = read ( ); m = read ( );
    for ( int i = 1 ; i <= n ; i++ ) a [ i ] = read ( ) , b [ i ] = a [ i ];
    sort ( b + 1 , b + 1 + n );
    q = unique ( b + 1 , b + 1 + n ) - b - 1;
    build ( rt [ 0 ] , 1 , q );
    for ( int i = 1 ; i <= n ; i++ ) {
        p = lower_bound ( b + 1 , b + 1 + q , a [ i ] ) - b;
        rt [ i ] = update ( rt [ i - 1 ] , 1 , q );
    }
    while ( m-- ) {
        int l = read ( ) , r = read ( ) , w = read ( );
        if ( query ( rt [ l - 1 ] , rt [ r ] , 1 , q , ( r - l + 1 ) / w ) ) {
            cout << query ( rt [ l - 1 ] , rt [ r ] , 1 , q , ( r - l + 1 ) / w ) << endl;
        } else {
            puts ( "-1" );
        }
    }
    return 0;
}