#nullable enable

#region
var (_input, _iter) = (Array.Empty<string>(), 0);
T I<T>() where T : IParsable<T>
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Trim().Split(' '), 0);
    return T.Parse(_input[_iter++], null);
}
#endregion

static T[] Range<T>(int n, Func<T> F) => Enumerable.Range(0, n).Select(_ => F()).ToArray();

const int Mod = 998244353;

var n = I<int>();
var q = I<int>();
var az = Range(n, I<int>);
var qz = Range(q, () => (I<int>(), I<int>() - 1, I<int>()));

if (n > 3000 || q > 3000) throw new Exception();

az = az.Order().Distinct().ToArray();
long min = az[0];
n = az.Length;
var bz = new LinkedList<long>();
{
    var last = long.MinValue;
    var len = 1;
    foreach (var a in az)
    {
        if (a == last + 1)
        {
            len++;
            last = a;
            continue;
        }
        if (last >= 0)
        {
            bz.AddLast(len);
            bz.AddLast(a - last - 1);
        }
        len = 1;
        last = a;
    }
    bz.AddLast(len);
}

var (l0, l1) = (0L, 0L);
{
    var f = true;
    foreach (var l in bz)
    {
        if (f) l0 += l;
        else l1 += l;
        f = !f;
    }
}

long At(long j)
{
    var res = min;
    var f = true;
    foreach (var l in bz)
    {
        if (f)
        {
            if (j < l) break;
            j -= l;
        }
        res += l;
        f = !f;
    }
    return (res + j) % Mod;
}

void O(long m)
{
    var b0 = bz.First!.Value;
    min = (min + b0) % Mod;
    l0 -= b0;
    bz.RemoveFirst();
    (l0, l1) = (l1, l0);
    if (l0 == m) return;
    if (l0 < m)
    {
        bz.AddLast(m - l0);
        l0 = m;
        return;
    }
    var f = false;
    for (var i = bz.Count - 1; i >= 0; i--)
    {
        var l = bz.Last!.Value;
        bz.RemoveLast();
        if (f)
        {
            l0 -= l;
            if (l0 <= m) break;
        }
        else l1 -= l;
        f = !f;
    }
    if (l0 < m) bz.AddLast(m - l0);
    l0 = m;
}

void OR(int k, int m)
{
    while (k > 0)
    {
        var u = bz.Count + 1;
        var t = k / u;
        if (t == 0 || l0 != m || l1 > m)
        {
            O(m);
            k--;
            continue;
        }
        min = (min + (long)t * m * 2) % Mod;
        k -= t * u;
    }
}

var ans = new List<long>();
foreach (var (k, j, m) in qz)
{
    OR(k, m);
    ans.Add(At(j));
}
Console.WriteLine(string.Join(Environment.NewLine, ans));