import sys
input = sys.stdin.readline

def nec(X,k):
    ko=k
    Y=[]
    for i in range(len(X)):
        a,b=X[i]

        if i+1<len(X):
            c,d=X[i+1]
        else:
            c,d=1<<63,1<<63

        minus=c-(a+b)

        MIN=min(ko,minus)
        ko-=MIN

        Y.append([a+b,MIN])

        if ko==0:
            break
    return Y

def what(X,x):
    for i in range(len(X)):
        a,b=X[i]
        if b>=x:
            return a+(x-1)
        else:
            x-=b
    

mod=998244353

N,Q=list(map(int,input().split()))
A=list(map(int,input().split()))
A=sorted(set(A))

X=[]
for a in A:
    if X==[] or X[-1][0]+X[-1][1]!=a:
        X.append([a,1])
    else:
        X[-1][1]+=1

#print(X)

plus=0
for tests in range(Q):
    k,x,m=list(map(int,input().split()))

    if k<=5:

        for tt in range(k):
            X=nec(X,m)

        print((what(X,x)+plus)%mod)
    else:
        #print("!",X)
        Y=nec(X,m)
        Z=nec(Y,m)
        k-=1

        while len(Y)!=len(Z):
            Y=Z
            Z=nec(Y,m)
            k-=1
            

        #print(Y)
        #print(Z)

        LEN=len(Y)+len(Z)

        a,b=Z[-1]
        necfirst=a+b
        first=Y[0][0]

        shuuki=necfirst-first


        rep=k//(LEN)
        k%=(LEN)
        plus=(plus+shuuki*rep)%mod

        for tt in range(k):
            Y=nec(Y,m)

        X=Y
        if X[0][0]>=mod:
            k=X[0][0]//mod

            for i in range(len(X)):
                X[i][0]-=k*mod
        print((what(X,x)+plus)%mod)