题目描述

在一个星际贸易市场中,有 \(n\) 个摊位排成一排,每个摊位的库存量为 \(a_i\) 市场管理者会进行以下操作 \(q\) 次（每次选择一个）：

• 补货:对第 \(l\) 到第 \(r\) 个摊位每个补充 \(d\) 件商品。
• 评估市场热度:计算第 \(l\) 到第 \(r\) 个摊位之间所有可能交易的“潜在交易量”。 任意两个不同摊位 \(i\) 和 \(j\) （ \(i\) 在 \(j\) 左侧）可以产生交易，交易量等于两个摊位库存的乘积（\(a_i \times a_j\)），因为每个摊位的商品可以互相搭配销售。 总潜在交易量就是所有这些两两乘积之和，需要对 \(998244353\) 取模（因为宇宙贸易法规要求）。

输入格式

第一行输入一个 \(t\) 代表 \(t\) 组数据: 每组数据第1行包含两个整数 \(n\) 和 \(q\) （\(1 \le n, q \le 10^5)\),分别代表摊位的数量和操作的数量。 第二行包含 \(n\) 个整数 \(a_1, a_2, \dots, a_n\),代表每个摊位的初始库存量。（\(0 \le a_i \le 10^7\)） 接下来 q 行,每行描述一个操作,格式如下：

• \(1 \: l \: r \: d\):表示一次补货操作，将区间 \([l, r]\) 内的每个摊位库存增加 \(d\) （\(0 \le d \le 10^7\)）。
• \(2 \: l \: r\)：表示一次评估操作，需要输出区间 \([l, r]\) 内所有摊位的潜在交易量对 \(998244353\) 取模的结果。

保证 \(1 \le l \le r \le n\)

题目保证 \(\sum n, \sum q \le 2 \times 10^6\)

输出格式

对于每次评估操作,输出区间内潜在交易量对 \(998244353\) 取模的结果。

样例输入

1
5 5
1 2 3 4 5
2 1 3
1 2 4 1
2 1 3
2 2 5
1 1 5 2

样例输出

11
19
107