Summing Variances Over Subsequences

You are given a sequence \(v_1,v_2,\dots,v_n\) of length \(n\) initially filled with zeros.

You need to process \(m\) operations. There are two types of operations:

• Operation 1: Given three integers \(l, r, a\), add \(a\) to each \(v_l,v_{l+1},\dots,v_r\). That is, for every \(i\) with \(l\le i\le r\), perform \(v_i:=v_i+a\).
• Operation 2: Given two integers \(l,r\), consider the segment \(v_l,v_{l+1},\dots,v_r\) of length \(L=r-l+1\). For every nonempty subsequence (i.e. any subset of these elements in order) of this segment, compute its variance and then output the sum of these variances modulo \(998244353\).

The variance of a sequence \(a_1,a_2,\dots,a_k\) is defined as follows. Let \(\bar{a}=\frac{1}{k}\sum_{i=1}^k a_i\). Then the variance is

\[ \frac{1}{k}\sum_{i=1}^k (a_i-\bar{a})^2. \]

Note that each operation is processed online. It is guaranteed that the input size is small so that a brute force enumeration over all subsequences in each query is possible.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(m\) denoting the length of the sequence and the number of operations.

The next \(m\) lines each represent an operation. An operation is given in one of the following forms:

• 1 l r a: Perform an update operation (Operation 1) by adding \(a\) to every \(v_i\) for \(l \le i \le r\).
• 2 l r: Perform a query (Operation 2) on the subarray \(v_l,v_{l+1},\dots,v_r\) and output the sum of variances for every nonempty subsequence modulo \(998244353\).

outputFormat

For each Operation 2, output a line with a single integer: the sum of variances of all nonempty subsequences of the queried segment modulo \(998244353\).

sample

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

0
499122283

</p>